Codeforces Round #757 (Div. 2) Editorial
source link: http://codeforces.com/blog/entry/97283
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By 4qqqq, 8 hours ago,
5 hours ago, # |
Why is the runtime for D2 log(log(n))? Does does the average number between 1 and n have about log(log(n)) unique prime factors or something? Why is that?
-
I think it's related to https://en.m.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
And prime seive where inner loop is only over primes has this many iterations:
n/2 + n/3 + n/5 + n/7...
(Factor out n)
4 hours ago, # |
Imagine statements were this short
4 hours ago, # |
Here's an solution for E (with query time). For a given sequence of temperatures, let be the answer for the query . Then we have for different values of , and for all other values of . (I won't prove this, but you can try it out for yourself.) We solely have a data structure that stores the values of for which . On receiving , we add and to the data structure, where .
Answering a query reduces to determining how many stored values are below . I used a PBDS and binary searched to handle insertions which means the complexity is actually but in principle this can be made into .
Implementation: https://codeforces.com/contest/1614/submission/137071970
24 minutes ago, # |
For the second question, my approach seems to be
20 minutes ago, # |
That feeling when you wasted 4 attempts on problem C because of wrong modulo :’)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK