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
We will build the needed arrays sequentially adding numbers. Let's look at what states we need. First, it is obvious that you need to keep the number of ways to build an array of already added numbers, secondly you need to know the total amount of added numbers. Now let's look at what happens when we add a new number (that is greater than all of the previous in a certain amount). It is clear that the added numbers should stand between the numbers 1 to less. In this case, if we put two new numbers in a row, between them should stand more (since we already have placed less). It is obvious that you need to cover all the previous numbers (among which must stand newly added). Thus, we have another state: the number of integers between which we should put the new ones. Thus we have the dynamics of the four parameters: dp [all] [ways] [lastnumber] [counttoadd]. Transfer. It is clear that you need to add at least counttoadd numbers, but how will this affect the number of ways to arrange the numbers? It's simple. Suppose we added number x, then the number of ways to be multiplied by the value of Q (x-counttoadd, counttoadd), where Q (x, y) — the number of ways to assign the same x balls in y different boxes. Q (x, y) = C (x + y-1, y-1) where C (x, y) — binomial coefficient.
Will English tutorial public?
they need a translator
No English tutorial for the round?
We really need a tutorial in English.
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?
this tutorial is just about 'what we should write as code' !!! I think it's better to discuss about 'why'
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.
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.net/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.
Actually, authors of Codeforces contests do get paid well enough ;-)
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 :)
I 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.
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 :)
You could use Floyd–Warshall algorithm: http://codeforces.net/contest/301/submission/3695726
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
Could anyone explain Eretosphen algorithm ,which i cannot find on Google. Thanks
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Thanks.It's very useful
You don't need eratosthenes sieve actually.
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
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).
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. -_-
Does anyone want to boast with his implementation of the idea presented here of the problem "301A — Yaroslav and Sequence"?
Can someone explain Div1 A solution in a clearer way please?
Problem Div1 A, using dfs is overkill, an observation is if
n
is odd, we can reach any states; and withn
is even, we can reach any states with the number of flipped position is even. An O(n) solution can be obtained: http://codeforces.net/contest/301/submission/38010389Thus, for Div 1 A, the constraint of
n
could be up to 10^8.Hey Time limit per test needs to be updated to 2 secs for 302A — Eugeny and Array.
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:
div1 B can be solved without using the binary search 57610787.
I ran your submission on Ideone with the input
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!