Kostroma's blog

Codeforces Round 389 (Div.2) Editorial
By Kostroma, 8 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +66
  • Vote: I do not like it

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

Is hash possible to solve the D Problem? I don't know whether a conflict happened in the hash process or there is a bug in my code. Here is my code: http://codeforces.me/contest/752/submission/23309803

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

    I haven't read the rest of your code but I think if your hash mods are (1007, 5009) then it doesn't look very safe (as in collision is likely to occur). However it might also be the rest of your code that is causing the WA. Just pointing out that the hash modulos aren't big enough.

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

    Good day to you...

    I totally agree with zscoder — as you have possibility to hash, you have almost "unlimited" possibilities of hash size (obv best modulo is somewhere near boundary of int so you can do all operations easily) [unless you need direct array access — but here you can use map]

    What I wanted to add is, that you can make it "double — hash" so the collision probability will be MINIMAL:

    Here, see the "rh" function. [but it might be slightly an overkill]

    Good Luck & Have Nice Day

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

      I've got it.Thanks a lot!

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

      Hi. I used double hash but got wrong answer. After just changing method from using hash to just putting string into map, I got accepted.

      http://codeforces.me/contest/752/submission/24697497 http://codeforces.me/contest/752/submission/24699032

      Above is with hash, and below is just using map. Without it, everything is same. When I used hash, I used (100001, 100003), which are big enough I thought. To solve this problem by using hash, what should I do more?? Or, did I use hash method improperly??

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

        Good day to you,

        as you might see, after adding MODULUS, it got accepted (if I copied right solution)

        This — imho — means, that test 47 was anti-natural modulo (i.e. ~2^64)

        Good Luck & Have Nice Day

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

    26998325 27005624 Ive used the same logic as most of the accepted codes. I even tried changing from hash to map. Still im getting WA on test case 8. Can you identify where the logic is going wrong?

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

      Got it. Logical error in else part for palindromes.

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

        I am also getting WA on TC 8. Can u tell me what is the error? I am getting the same output as your's.

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

          Yes, the error was that if at any point you get something like abc -10 and cba 5, its not necessary that you couple these both. You discard the negative one and consider cba 5 as a standalone string that is available. Similarly if it were aba instead of abc, then you actually discard the negative one and consider 1 more already palindromic string in the pool that should be taken into consideration.

          → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

There's also a soltuion for E using binary search. My mistake was writing recurrent DP instead of iterative to count in how many parts of size greater or equal to mid we can divide a number. The latter passes TL, the former does not.

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

    I had the same solution and also got TLE at system tests. However it still works if you sort the array first to break the loop asap

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

Hi I wanted to know will binary search work for problem E.If no can you provide a countercase.

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

    Actually many people solved it by binary search
    see my code

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

      Can you help me please to find a mistake in my code for problem E which using a binary search: 23347431

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

        consider you have only one tangerine, with size 15. how many parts you can get with size 5?

        in your code = 15/5 = 3 parts but by the procedure, 15 -> 7, 8 7 -> cannot divide 8 -> cannt divide therefore, the answer should be 2, instead of 3.

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

          You are not right because I add to answer a cnt[a[i]/m] where m is a minimum amount of parts of tangerine which every pupil should get. In cnt[i] I store a max power of 2 which is not great than i. In your example a[i] = 15, m = 5, a[i] / m = 3, cnt[3] = 2. But I found a mistake in my solution. I considered that we can't get more than cnt[a[i]/m] things with at least m parts of tangerine. But there is a counter test: a[i] = 7, m = 2. So cnt[a[i]/m] = 2. But let's divide 7: 7 -> [4, 3] -> [2, 2, 2, 1]. As we can see, there are 3 things with at least 2 parts of tangerine and so my solution is incorrect.

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

      Dp[a[i]] shows how many children will have more or equal count of mandarins. Am I right ?

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

        Yes, and dp[i] = dp[i / 2] + dp[i / 2 + (i % 2)];

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

      Yet again I notice that your codestyle and logic very beautiful and clear for me.

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

It seems the solution about E is not O(n+A) solution.. I implemented the algorithm written in this article and got counterexample(which makes TLE).

I think the main reason is that we can divide a tangerine multiple times(divide the divided part again), so division can happen more than n times.

here is my code : http://codeforces.me/contest/752/submission/23353597

or did I get something wrong?

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

    You should divide all the tangerines of the same size at once. It can be easily seen that there is no profit in dividing only some part of them.

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

for the problem F it is up to us to divide the teams into pairs. so why can't there exist a pair which is solely in the sub-tree of this chosen vertex v. such pair may give smaller distance than the pairs chosen above. is there any proof available for this statement.

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

    In this problem we want to divide teams into pairs in such a way that the number of cities in which the teams live is minimized. In the editorial we show that one city is always enough.

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

problem C , you can just iterate and count how many times you get a non-logical shortest path.

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

Did problem D: Santa Claus and Palindrome using DP(slightly easier approach compared to editorial), have a look at my code.

→ Reply