### Sereja's blog

By Sereja, 9 years ago, translation,

302A - Eugeny and Array
If the length of the given segment is even and count of 1 in input is not lower then half of the length of the segment and count of -1 in the input is not lower then half of the length of the segment so we have answer 1, otherwise 0.

302B - Eugeny and Play List
For each song we will count moment of time, when it will be over (some sums on the prefixes, for example). Further, we will use binary search of two itaratos method to solve the problem.

301A - Yaroslav and Sequence
Using dfs we will find number of numbers that we can set as positive. Note that we can either set all of the numbers as positive or leave one number(any) as negative. If we can obtain all numbers as positive, we just return sum of modules of the numbers, but if we cannot we will count the same sum and will subtract minimal modular value multiple 2 from sum.

301B - Yaroslav and Time
We will use binary search to find the answer. Further we will use Ford-Bellman algorithm. On each step we will have an array of maximum values on timer, when we stand in some point. On in transfer we will check: will our player stay alive after travelling beetwen points. If we can make transfer, we will update value of the final destination point. Becouse of a_i<=d and integer coordinates we haven't optimal cycles, and solution exists.

301C - Yaroslav and Algorithm
We will use ? as iterator. In the begin we will set ? before the number. Then we will move it to the end of the string. Then we will change ? to ?? and we will move it to the begin, while we have 9 before ??. If we have another digit, we just increase it, and finish the algorithm. If we have ?? at the begin, we change it to 1, and end the algorithm.

Look for accepted solutions for better understanding.

301D - Yaroslav and Divisors
Lets add all pair: (x,y) ((d[x]%d[y]==0) || (d[y]%d[x]==0)) to some lest. We can count such pairs using Eretosphen algorithm. Here will be O(n*log(n)) sych pairs using fact, that we have permutation. We will sort all this paairs using counting-sort. Also we will sort given in input intervals. For each given interval we should count number of pairs that countained in given them . Such problem we can solve using Fenvik tree. On each step we will add segments(that are sorted by right side). On each step we will update Fenfick-tree that count number of added pairs on some suffix. Using such tree if it easy to count the answer. So we have O(n*log^2(n)) solution.

301E - Yaroslav and Arrangements

• +31

 » 9 years ago, # |   +5 Will English tutorial public?
•  » » 9 years ago, # ^ |   0 they need a translator
 » 9 years ago, # |   0 No English tutorial for the round?
 » 9 years ago, # |   0 We really need a tutorial in English.
 » 9 years ago, # |   +18 Sorry to say but I really dislike tutorials on Codeforces in general, as usual they are very short and all you can see is a brief idea. Is it too hard to write a full solution like people on topcoder do?
•  » » 9 years ago, # ^ | ← Rev. 2 →   +4 this tutorial is just about 'what we should write as code' !!! I think it's better to discuss about 'why'
•  » » 9 years ago, # ^ |   +18 Maybe this very tutorial is a bit hard to understand, but in general I like these brief tutorials. If these several words are not enough for somebody, it probably means that the given problem is too hard for them.Reading TopCoder tutorial is like a lecture, you don't need to know anything to understand it. Here you have to put an effort to understand the solution. And writing longer tutorials is definitely harder and requires more time from the author. Who's gonna pay him? Codeforces don't make money like TopCoder does (AFAIK), so we must be happy with cheaper solutions.Instead of minusing your opinion, I say the opposite thing.
•  » » » 9 years ago, # ^ |   +5 I agree some of what you said. Sometimes the tutorials are fine, I mean in most cases they seem to be like this. I understand that you need more effort to write longer solutions but some authors do this effort (For example I can show you this: http://codeforces.com/blog/gojira). It will be nice if it will be improved. 3 line explanation for Div1 C (also considering that only a little amount of people solved it, compared to other rounds) seems to be very very far from enough.
•  » » » 9 years ago, # ^ |   +6 Actually, authors of Codeforces contests do get paid well enough ;-)
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   +6 Yes, that's amazing, because I see no evident source of money, except VK sponsorship. And sad from the other side, that if CF didn't have the money, we wouldn't have problemsets. It scares me a bit when I read about VK owner situation. But maybe this miracle is something special to Russia. I don't need to know all the details. Having CodeForces running makes me sufficiently happy :)
•  » » » » » 9 years ago, # ^ |   +17 if CF didn't have the money, we wouldn't have problemsetsI will take the liberty to say that many authors prepare contests not for the money, but because it's interesting, fun and gives you a unique experience.
 » 9 years ago, # |   0 I am new to programming contests please someone can explain what we had to do in DiV1-problem B in proper english and why ? would be high. greatful :)
•  » » 9 years ago, # ^ |   0 You could use Floyd–Warshall algorithm: http://codeforces.ru/contest/301/submission/3695726
•  » » 9 years ago, # ^ |   0 Because d>=ai,so we can't go through a station twice.So we can use an algorithm to find a shortest path.We can use "SPFA" "Dijkstra" or "Floyd". And I use "Floyd" because it is too easy
 » 9 years ago, # |   0 Could anyone explain Eretosphen algorithm ,which i cannot find on Google. Thanks
•  » » 9 years ago, # ^ |   +8
•  » » » 9 years ago, # ^ |   0 Thanks.It's very useful
•  » » 9 years ago, # ^ | ← Rev. 5 →   0 You don't need eratosthenes sieve actually. for (int a = 1; a <= n; a++) for (int b = a; b <= n; b += a) remember_pair(a, b);// b % a == 0 there will be about O(log(n)) pairs (a, b) for n = 200000 there will be about 2 * 10^6 pairs UPD: O(N log N) pairs of course, thanks Zlobober
•  » » » 9 years ago, # ^ |   +5 You meant O(N log N), I think.It's quite interesting fact that number of pairs (a, b) such that a divides b has such asymptotic. I really love the way of proving it.We can see that number of factors of 1 is integer part of N/1, number of factors of 2 is integer part of N/2, number of factors of 3 is integer part of N/3 and so on. Let's remove integer parts away (total sum will increase by no more than N) and take N off the brackets. We obtain N * (1/1 + 1/2 + 1/3 + ... + 1/N). Sum in the brackets is the prefix of the sum of harmonic series — it's well known that it's asymptotic is theta(log N). So we obtain the asymptotic for the original construction: O(N log N).
•  » » 6 months ago, # ^ |   0 I know this is necroposting but someone either fix the English editorial or pin the above comment to the top somehow. Wasted a lot of time searching even research papers for Eretosphen algorithm. -_-
 » 9 years ago, # |   0 Does anyone want to boast with his implementation of the idea presented here of the problem "301A — Yaroslav and Sequence"?
 » 9 years ago, # |   0 How can we apply dfs to solve 301A as mentioned in Editorial ?
 » 5 years ago, # |   0 Can someone explain Div1 A solution in a clearer way please?
 » 4 years ago, # | ← Rev. 2 →   0 Problem Div1 A, using dfs is overkill, an observation is if n is odd, we can reach any states; and with n is even, we can reach any states with the number of flipped position is even. An O(n) solution can be obtained: http://codeforces.com/contest/301/submission/38010389Thus, for Div 1 A, the constraint of n could be up to 10^8.
 » 3 years ago, # |   0 Hey Time limit per test needs to be updated to 2 secs for 302A — Eugeny and Array.
•  » » 3 years ago, # ^ |   0 No, the limit is 1 second and my normal O(n+m) solution needs 156 ms. 49375836 I've checked your code and it gets accepted with the result 748 ms if you use fast input/output. Just put this at the beginning of the main function:  ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); 
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I have literally used the exact same code #66477315 as you, yet i keep getting TLE verdict. No clue as to why....
 » 3 years ago, # |   0 div1 B can be solved without using the binary search 57610787.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I ran your submission on Ideone with the input 3 1 1000 0 0 0 100 0 101 and it gives -899 as the output. I think the answer to this case should be 100.I think this is the case of weak test cases. You're only optimizing the total cost of the path. It could be the case that your player runs out of time while travelling between two stations.Update: Sorry! The input is invalid since d should be greater than 1000. My bad!
 » 3 years ago, # |   0 has Anyone solved problem D using MO-Algorithm?If yes, Give me the hints please.
 » 8 months ago, # | ← Rev. 2 →   0 Dfs isn't necessary in Div-1 A, one can just check X (count of negative numbers mod n) mod 2 and (( X mod 2)+n) mod 2 to do the trick, here is my submission :https://codeforces.com/contest/301/submission/129985122
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}