Sereja's blog

Codeforces Round #182 tutorial
By Sereja, 12 years ago, translation, In English

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.

  • Vote: I like it
  • +31
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will English tutorial public?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No English tutorial for the round?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We really need a tutorial in English.

→ Reply
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    this tutorial is just about 'what we should write as code' !!! I think it's better to discuss about 'why'

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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://mirror.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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Actually, authors of Codeforces contests do get paid well enough ;-)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it
          if CF didn't have the money, we wouldn't have problemsets

          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.

          → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain Eretosphen algorithm ,which i cannot find on Google. Thanks

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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).

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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. -_-

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone want to boast with his implementation of the idea presented here of the problem "301A — Yaroslav and Sequence"?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain Div1 A solution in a clearer way please?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/301/submission/38010389

Thus, for Div 1 A, the constraint of n could be up to 10^8.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Time limit per test needs to be updated to 2 secs for 302A — Eugeny and Array.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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);
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

div1 B can be solved without using the binary search 57610787.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

    → Reply