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

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

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

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]"

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 (

a_{1}+a_{2}+sum,a_{2}+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

a_{1}anda_{2}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.

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?

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

Thanks a lot!

Thank you, finally with that example i understanded the solution :D

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

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

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.dp solution for problem C with comments...

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

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

My Bad, sorry

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

You can find it here

Thanks!

Accepted aa gaya tera fir?

Yaa, just use

`Integer`

in place of`int`

as the datatype of input array.In problem C, why does the function start erasing from the second character? why not first?

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

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

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:

25890955

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 arrayaas int array instead of long long, and int division is also faster than long long division.thanks, got accepted immediately after replace the rounding up division expression. So nice the replace is!

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

25878153

thanks :)

You're welcome)

Hi! Can anyone help? Are there full texts of tests available?

but if a1:kwhat does this mean in problem Ea1%k==0

I am humbled by question-E. so simple yet so beautiful.

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$$$

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

I don't understand E, can someone elaborate? My initial idea was to use gcd of all the numbers. then pairs would be gcd, gcd + 1, or gcd — 1, gcd sizes.

A gets TLE with a sort in Java now on test 42

"Note that if the answer for given string exists, then this function will erase no more than 2 digits"

why no more than 2? 1003 = needs 3 removing

Great Tricky Questions & Great Editorials.Keep it up guys!!