BledDest's blog

Educational Codeforces Round 18 — Editorial
By BledDest, 8 years ago, translation, In English

We want to apologize for the issue with problem C. We hope this didn't totally ruin the contest to those who got Judgement Failed on their submissions.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +34
  • Vote: I do not like it

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

Let me mention the beautiful x&(-x) which is equal to highest power of two that divides x.

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

    Also we have x&(x-1) which is equal 0 only when x is a power of two(except x == 0).

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

Can someone explain to me the solution of problem C, especially this part: "Then you can easily see that its enough to check only three function outputs: on substrings [a1..n], [a2..n] и [a3..n]"

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

    The only flaw in the function is that it can't erase first digit of number. So we should feed it with numbers of different sums modulo 3. So sums of these strings are (a1 + a2 + sum, a2 + sum, sum).

    Let's notice that if the first digit is 0 modulo 3, then it won't be erased anyway and thus won't affect further number (if we can't make beautiful number of this string, then we won't be able to make it out of any further ones).

    So now we only care if a1 and a2 are either 1 or 2.
    1) If one of them is 1 modulo 3 and the other is 2 modulo 3, then by deleting both of them you will get sum of original number modulo 3.
    2) If both of them are the same modulo 3, then check every possible reminder of original sum. If it was 0 modulo 3, then the answer existed anyway. If it was either 1 or 2, then by deleting one or both of this digits you can make sum 0 modulo 3, so the answer will exists, if it existed for original number.

    I hope that this I made myself more clear.

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

      I still did not understand.I want to ask a few questions. How do we write the function which erases the minimum number of digits from the string?

      I having a problem with this because we have to take care of the leading zeros.So there maybe a case where removing only one non-zero digit may cause a number of zeros also to be removed.

      Ex-; 2000111 if we remove 2 we'll get 111 ,and we will have to remove the zeros also.So this will not be the minimum case. However if we remove 2 1s we'll get 20001 which is the optimal answer. So how do we take care of this?

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

        Solution that I described in editorial doesn't have separate function that erases minimal number of digits from all the string. It has the function which erases minimal number of digits from string but doesn't touch the first digit.

        In your testcase we will try running this function on strings "2000111" (returns "20001"), "111" (returns "111") and "11" (returns "-1"). Obviously, max of these is "20001".

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

The problem C reminded me that i am a primary competitor. sorry for my poor English

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

Hi can anyone explain me the dynamic programming approach of Problem C ? Thanks

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

    Let dp(i,j) denotes the maximum number of digits we will keep from 1 to i, including i and the number they form modulo 3 = j (or you can say the length of longest subtring ends at i and modulo 3 = j).

    I will show you how to compute dp(i,0), you can do the same thing with j=1,2 and the special case when s[i]='0'. Let x=s[i] % 3, then dp(i,0) = max(dp(k,y)) + 1 with k = 0..i-1, y + x = 0. To be more detailed, there are 3 cases:

    • x=1: dp(i,0) = max(dp(k,2)) + 1 , however if there is no k that dp(k,2) > 0, which means there is no substring before i that modulo 3 = 2, dp(i,0) should equal to 0.

    • x=2: dp(i,0) = max(dp(k,1)) + 1 , same as above, if there is no k that dp(k,1) > 0, dp(i,0) should equal to 0.

    • x=0: dp(i,0) = max(dp(k,0)) + 1 , this always holds true because if there is no k that dp(k,0) > 0, we can make a new substring starts and also ends at i which has length 1 and modulo 3 = 0.

    It's a little bit confusing when explain so you can look at my code here: 25856552

    In my code, I add f[i] denotes the length of longest substring which modulo 3 = i and update it continuously. It replaces max(dp(k,y)) above to reduce complexity to O(length(S)). Since this problem required the number after erasing, we have to trace it after dynamic programming.

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

    dp solution for problem C with comments...

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

Sir, in New Bus Route i.e Question A, What if the minimum difference is zero, in that case counting only adjacent pairs won't work for eg. for input case 6 2 2 2 3 5 5 as per your method ans will be 3, but the actual answer is 4 — the 3 pairs of all the 2s and the one pair formed by 5,5

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

    One tip in competitive programming is to carefully read the problem statement.

    "The first line contains one integer number n (2 ≤ n ≤ 2·105).

    The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). All numbers ai are pairwise distinct."

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

Can anybody tell me why am I getting a TLE on this submissions of 792A - New Bus Route problem my submission is this 25882029. The complexity is O(nlogn).

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

In problem C, why does the function start erasing from the second character? why not first?

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

    It's done to avoid handling any leading zeros problems.

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

      I'm confused why this works. Suppose n = 133. Then starting from the second digit would ignore the optimal case where we take out the first digit right?

      Please correct me if I'm misinterpreting..

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

Time exceeded on test 30 of problem E, as far as I'm struggling, the complexity is correct but maybe the constant is too large, can someone help me with a more efficient algorithm for calculating the sum of sets?

current algorithm:

for (int i = 0; i < n; i++)
        {
            if (a[i] / size >= a[i] % size)
            {
                cnt += min(a[i] / size, (a[i] / (size + 1) + (a[i] % (size + 1) ? 1 : 0)));
            }
            else
            {
                cnt = 3e18;
                break;
            }
        }

25890955

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

    Well, integer division (as well as modulus) are complex operations, and it's better to get rid of them, if possible. For example, when you write something like (a / b + (a % b ? 1 : 0)), which means a divided by b rounded up, you can replace it with ((a + b — 1) / b), which uses only one division operation and works faster.

    UPD: And as for more, you can store the array a as int array instead of long long, and int division is also faster than long long division.

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

      thanks, got accepted immediately after replace the rounding up division expression. So nice the replace is!

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

Can someone please paste the Problem C accepted solution???

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

but if a1:k what does this mean in problem E

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

For anyone wondering about the proof of problem D:

the key idea is that the value at any non-leaf node is the number of nodes in the left subtree of the node $$$+$$$ the least valued leaf. This is obvious by the recursive algorithm. Then one can prove that $$$val(parent)-val(leftchild)=2^t$$$, where $$$t=k-1$$$

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

Hey BledDest, awoo

Can you explain the first line in the editorial of problem E ? I am not able to understand why k<=sqrt(a[i]) or x<=sqrt(a[i]) ?

Thanks

→ Reply