Educational Codeforces Round 59 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

Hello Codeforces!

On Jan/26/2019 18:35 (Moscow time) Educational Codeforces Round 59 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

UPD: You can discuss the problems after the contest on a local Discord server.

Our friends at Harbour.Space also have a message for you:

Hello Codeforces!

A quick reminder to check out the Hello Muscat Programming Bootcamp!

Every day, both the Hello Programming Bootcamp and the Moscow ICPC Workshop will be competing simultaneously, 4,000 kilometers from each other — our camp will take place in Oman, from March 9th to March 15th, 2019 — registration is still open for this unique opportunity, so be sure to give it a look, we would love to see you there with us!

REGISTER FOR THE BOOTCAMP

And, don’t forget that Harbour.Space University’s opportunity for a fully funded Master’s in Robotics programme scholarship is still open! Head over to their website to see the details, and apply before the registration date closes.

APPLY HERE

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 vintage_Vlad_Makeev 7 198
2 Radewoosh 7 358
3 Rzepa 7 396
4 eddy1021 6 170
5 spacewanker 6 175

Congratulations to the best hackers:

Rank Competitor Hack Count
1 _bacali 39:-44
2 Kiri8128 8
3 tymo 5:-1
4 Osamaa 4
5 sevlll777 5:-4
121 successful hacks and 527 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A vintage_Vlad_Makeev 0:01
B neal 0:02
C neal 0:05
D vintage_Vlad_Makeev 0:10
E Fake.Puppet 0:10
F vintage_Vlad_Makeev 0:44
G Kalam 0:17

UPD2: The editorial is out

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

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

Clashes with Topcoder SRM. Please prepone it by 30 minutes.

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

    Also clashes with CodeChef Lunchtime.

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

      It's surprising that two contests promoting the same bootcamp are clashing.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

Null

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

Clashes with indian entertainments

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

Clashes with Educational 59

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

中国玩家修仙场：）

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

Clashes with CodeChef lunchtime. Please reschedule.

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

Happy Republic Day Indian Coders!

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

Please make contests at more diverse time frames -- times like 18:35 MSK are really unfriendly for students living around UTC +8.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Picture
Hope every one become candidate master one day.
→ Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Hope that will be a lot of hack today xD

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

    I try to hack the problem B&&D , but I failed

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

Nice picture though~ :D Is that the campus?

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

Give me a purple name plz...

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

Want to Be a Candidate Master... So everyone Good Luck && Higher rating... RP++

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

Clashes with clans

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

oh my the name hints it will have pointless math again. god, can't you keep these two things sepparate? is it so hard to understand that math has nothing to do with programming? it doesn't help you get better, it's just useless.
only people who want to feel better for themselves thinking they've actually accomplished something like math in programming.
so with this said let's hope for a math-free problem set.
if it doesn't have any math i will surely get out of expert. can't wait.

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

    last minute smart move: i'm not going to take part in this contest because i know from experience it's going to be a lot of math. not worth taking the risk.

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

CodeForces OR CodeChef???

Both.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -30 Vote: I do not like it

Fuck problem statements. I'm done.

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

    I don't know why, but at last contests problems are easy or hard, there is no medium ones.

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

      they are math problems which are useless. it makes them pointlessly harder, that's the reason why. don't bother...

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

For the question D, if i=1 and x=4 then [i/x] gives 0. This index does not belong to the matrix B What is to be done then ?

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

nice problems ^^ , how to solve E ?

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

    https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1500

    Almost the same logic XD

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

      What's the DP state though?

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

      What is the solution for this one? The constraints here suggest that n3 is possible.

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

        For the UVa problem in the link: Let's calculate dp[l][r][len] — the most points we can gain if we do operations on s[l] to s[r] with the same len characters as s[r] attached at the back of the string. Let p be the leftmost index satisfing s[p] = s[p + 1] = ... = s[r] and q be some indicies satisfing s[q] = s[r] and s[q] ≠ s[q + 1].

        Then we can list the dp equations:

        • dp[l][r][len] = dp[l][p - 1][0] + (r - p + 1 + len)2 — if we clean all blocks from p to r ;

        • dp[l][r][len] = dp[q + 1][p - 1][0] + dp[l][q][r - p + len + 1] — if we decide to clean blocks from q + 1 to p - 1 first and the others at last.

        For today's E problem just substitute (r - p + 1 + len)2 with the most points we can gain from the string with same characters of length r - p + 1 + len. This can be done by another simple dp.

        I know the constraints suggest a O(n3) solution, but maybe many states cannot be approached? I desire the proof too ><

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

contest was so easy :D

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

How to solve D ?

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

    Mine's using sliding window. Keep extend our window when the string in the next row is equal to the string in the current row. Keep track all size of the windows and find the GCD of all windows' size

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

      Nice idea, but I think you should do the same thing on columns too.

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

    Basically we need to check over all x such that x is factor of n,for a given x we need to check all the [n/x]*[n/x] sub-matrix whether they contains equal element or not, if a submatrix contain equals elements either all of them equal to 0 or 1 i.e sum is either 0 or x*x,we can easily check sum of a submarix with the help of 2d-prefix sum.

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

      Thats O(n^2*sqrt(n)) in worst case?

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

        Nope, a number can have max of n^1/3 factors.and for each factor we are doing only n^2/x^2 work so actual complexity would be near to n^2 with some constant.

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

        if you just check from all the numbers from 1 to sqrt(n) for a divisor of n, then this is the complexity in the worst case.

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

    Don't know if this is the indended solution, but I did this:

    Convert hex to binary and store it into a matrix. Then you try each divisor of N as x in O(N*N). At most, N has 60 divisors (N = 5040). I've executed this solution with the worst case in codeforces custom test and it seems to pass, but who knows...

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

      What is worst case in your opinion?

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

        You are trying to hack me haha. Find it out yourself

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

          I think that 5040 and whole plane in F will hack you, however im not doing it. If im not mistaken you gonna do ~25kk*60 operations.

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

            I've tested that case during contest, nothing happened, no TLE. Was thinking in solving it with binary search but that failed so i resorted to this.

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

              How is it not giving TLE when doing > 1.5*10^9 operations + big input?

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

                You forgot that checking big x is not O(N*N). It is O(N*N/(X*X)). So the solutuon is way faster.

                Upd: I'm sorry I haven't checked your submission. Yes, your solution runs in O(N*N*Number of divisors)

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

                  My code checks every x in O(n*n)

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

                  So how is it doing 1.5*10^9 operations in time limit?

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

                  I've seen an O(n) simple loop when N = 10^9 and it executed in 0.7s. It seems I do a ton of operations but most of them are just comparisons

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

            For that to work, the time limit of the problem should have been 1 sec. The solution having complexity O(N*N*60) gives 1578ms and the one with prefix sums (optimised) gives 400ms.

            The problem setter could have given it some thought and made it a better problem.

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

How to solve D?

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

    Find all divisors of n. Then for each divisor, divide the matrix into the dXd submatrices and check all the submatrix has similar elements (1 or 0). Find the maximum divisor that satisfies this.

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

      I have used binary search to find maximum divisor which satisfies x-compression,but it fails on test 4,can u explain why?
      if linear search is used to find maximum divisor then it gives AC.

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

        Binary search wouldn't work as it is not a monotonous sequence.
        Eg: 

         12
         E00
         E00
         E00
         E00
         E00
         E00
         E00
         E00
         E00
         E00
         E00
         E00
        The answer to this is 3, and both 2 and 4 don't satisfy as an answer.
        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I also did the same, but here our assumption for binary search to work is that if the current_divisor is not answer then the answer is less than the current_divisor but this is false answer can be greater than current_divisor.

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

      if this is the case then the case 1 given should give ans "2"..2 x 2 matrix is having all equal elemts and 2 divides 8 too...so why the ans is 1?CAN U EXPLAIN THIS??

      1. 11100111 E7
      2. 11100111 E7
      3. 11100111 E7
      4. 00000000 00
      5. 00000000 00
      6. 11100111 E7
      7. 11100111 E7
      8. 11100111 E7
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Consider first two submatrices starting from the first row:

        11

        11

        and

        10

        10

        Here the second submatrix doesn't have similar elements (combination of 0 and 1). So 2- compression isn't possible

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

          means we have to check all possible sequencely (n/x)*(n/x) matrix ??..i thought the first one accrdng to ur ans...i am confuse in submatrices...which sub matrices we have to take??

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

            Yes, you have to check all sequential submatrices.

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

what was the state for the DP in problem E?

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

    I think, (sum_of_current_length, left_index, right_index), but I'm little scary about time limit of my solution

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

Is D solved in O(no.of divisors*n*(n/4))

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

    It's

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

      My algorithm solves it in O(n^2). Idea: count the prefix sums on the matrix in O(n^2). Then, for all divisors (div) split the matrix in small squares of length div and check if it each of them has sum div**2 or 0. Each iteration works in (n / div) ** 2, but we should take into consideration that however many divisors of n there are, the resulting number of iterations must converge at appr. 1.5 * n^2 (n^2/1 + n^2/4 + n^2/9 + ...), therefore the time complexity is O(n^2). Correct me if I am wrong.

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

    mine is O(n*n*sqrt(n))

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

    I have a much neater solution.

    • Find all lengths of consecutive segments with same character. (like 0001111110 then you count 3,6,1)

    • Do this for both vertical and horizontal.

    • Answer is the gcd of all the lengths.

    O(N^2), because you can just determine whether a segment of this length exists, and so gcd would be called N times at most.

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

      Sorry, I'm dumb, and you're smart, so I don't know why this works. Could you explain? orz

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

To me, G seemed like a divide-and-conquer after assigning profit to each element as a-c[i]. However, I got WA on test case 7. E seemed like some kind of dp-transitions — can someone provide a hint?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -26 Vote: I do not like it

Deleted

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

I think it's a very bad contests experience. The description is long and difficult to understand. Boring problems and difficulties of code. Some data area is not reasonable enough.

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

    lengthy code? for which problem?

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

      For me D was very long (though my implementation was sub-par).

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

        See my implementation if you want short and easy to understand code.

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

    I don't actually understand why are people so angry about the statements. There are two main mistakes in our statements, one is not telling about 1-indexation in D and another one is writing that paragraph about skipping hits in C too ambiguous. Can you point out any other mistakes in the statements?

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

      for B. k"th was too ambiguous. i misunderstood that kth root of x instead of kth number which is kth number of set.

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

        root of all numbers in set are equal to x

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

        Sorry, but I don't understand why did it cause so much abmiguity. There is no definition of some k-th root in the statement, only digital root of x, which, obviously, does not depend on any number k. Hence the phrase "k-th root" is something absolutely undefined.

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

Did anyone solve D using Python? Pretty sure I had the right idea but I got TLE on test 4 and I'm wondering if it is because of python's I/O slowness

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    from sys import stdin
    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    The trick is to use PyPy and read the input with sys.stdin.read(), this will read the entire input as a string. From my testing all other ways of reading input is significantly slower.

    Here is my solution running in 1123 ms. The main thing slowing the code down is that I'm calling a function to calculate gcd. By inlining the gcd call my solution runs in 826 ms.

    EDIT: If I additionally add a check for if the gcd hits 1, and then print 1 and exit, it runs in 390 ms.

    EDIT2: Played around with it a bit more, was able to get it down to 343 ms by pretty much removing the gcd calls.

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

      @pajenegod you are the saviour of all (slow) Python user! I salute you

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

      Thanks a lot man, will try asap :)

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

      You're the boss! (with nearly the same code as in my last python3 submission of the contest)

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

        I looked at the input reading in your code. You are currently using sys.stdin.readlines(). I've been a much bigger fan of sys.stdin.read().splitlines(). It might be quicker, but more importantly removes all '\n'. So I pretty much never use sys.stdin.readlines().

        Switching to sys.stdin.read().splitlines() makes one of your solutions go from 1699 ms to 1434 ms. Then I tried to switch from PyPy3 to PyPy2. It went from 1434 ms to 1075 ms. So there's still a lot of things you can do to speed up your solution without modifying anything in the algorithmic part. Don't know how used you are to python 2 but it is usually noticeable faster than python 3.

        Python2 is pretty similar to python3 code wise with some exceptions. A small tip is to start out your python 2 code with 

        from __future__ import print_function
range = xrange
input = raw_input

        and most things will be like how it is in python3.

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

          At my job we use Python2 but I've personally taken the habit to use Python3 because of the fact python2 won't be maintained anymore in 2020. So yeah I know the basic differences between the two languages but I didn't know python2 was that much faster under these circumstances. Also thanks a lot for the advice man! I'll use these tips from now on on codeforces :)

          EDIT: I was also using python3 to be able to use math.gcd in this case, but I did a bit of google search and found out gcd was in the fractions module of python2. Then I read your submission based on my code and I saw you used xrange, I know the trick but did not even think about it... So you're right, there's definitely more I can do to grind some more precious milliseconds!

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

In D, I got WA on test 4, my idea is in each column and each row, I find optimal result (array ln[5204] and ld[5204]). after that, i general all to get answer of this problem, here is my code https://mirror.codeforces.com/contest/1107/submission/49020250 sbd help me,pls

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

    You can try to input 12 rows of 0FC(000011111100). The answer is 2 but your output is 1.

    I think it's safer to calculate the GCD of lengths of those substrings.

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

      got it! i don't know how to do till see your test, thank you so much.

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -12 Vote: I do not like it

Deleted

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -29 Vote: I do not like it

D was a nice problem.

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

Problem B marks the saddest Google search I have ever done.

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

how to solve G with binary search?

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

    You can see that each problem worths a — c.

    Let's fix gap value. That is, for each i from 1 to n — 1, binary search to find l and r satisfying l <= i <= r, and all x and y satisfying l <= x <= i <= y <= r the subsegment from x to y have the gap value equal to (di — di+1)^2. Now the only thing you have to do is find the maximum subsegment containing i in l...r. It's can be done with a segment tree storing maximum prefix and maximum suffix (very similar technique to GSS1 spoj)

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

Can anyone please tell me what is wrong with this solution for problem D.

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

this is my code. i don't understand output is why like that https://mirror.codeforces.com/contest/1107/submission/49007458

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

    AFAIK you must not mix cin/cout and scanf/printf if you use fast I/O. Your solution passes if the corresponding command is removed.

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

Can anyone solve Problem E Vasya and Binary String explain his/her approach ?

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

whats the ans for C for this test case? 6 3 14 18 9 19 2 15 cccccc

ans how ?

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

    Just make a vector and push_back values as long as it's the same letter then sort the vector and get the largest possible values

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

    i think you also misunderstand the problem.. your ans for test 5 = 68, same with me, check again the problem page, they add explanation and example, the consecutive count will not reset after skip character,

    for example: 4 2 1 1 1 1 aaaa

    you cant pick 1,2,4 because you press 3 button 'a' in a row

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

i assumed for problem C, that if i skip some button, the "consecutive count" for current character will reset.. checking test 5 and re-read problem statement, they add this

Note that if you skip the hit then the counter of consecutive presses the button won't reset.

but its ok i just solved the different problem with dp, i think :D

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

My initial submissions on problem C were giving wrong answer on sample test 1, eventhough on local, hackerrank and hackerearth compilers I was getting answer as 54 for that. Eventhough that solution was wrong but can someone explain why this happened? https://mirror.codeforces.com/contest/1107/submission/49004601

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

    When you do k1 = se.size() — k, it gives you error. Since s.size() is an unsigned value, k gets typecasted to unsigned and gives error.

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

      Why does it run on online compilers like hackerrank and hackerearth ide

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

Can anyone explain why this code(in Problem C) is accepted without runtime error?49024911

The core section is:

string in;
cin >> in;
int len = in.length();
if(in[len-1] != in[len])
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    String in C++ has a null character on the end of it.

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

How to solve E problems pls?

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

    Tried to make a nice solution of E which should be pretty readable and self-explanatory.

    (Instead of using DP-states involving triple indices I just play around with strings and do recursion).

    EDIT: fixed the link

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

49025933 49025845 49026055 49026124

If you look at this submissions you can see there

if (n == 38)
{
    if (arr[23] == 53)
        return 0;
}

this submissions were hacked, and I think this should be considered as cheating.

UPD: Now all of his submissions are hacked (also the submissions for problems A and B)

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

    I was about to comment the exact same thing. Fake account

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

    This is Educational round who cares about get successful hacks?

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

      I know it can't increase your rating, but it can help you to be in hacking leaders table

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

        So an hack in an Educational can't increase your position in standings?

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

          Yeah but there is a separate leaderboard for hacking

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

          Technically if you hack someone rank higher than you, your rank might go up

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

It was a great contest,so what about D statement, I didnot understand it, help me pls

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

I didn't receive an Email to remind me of this round this time, weird

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

Seems like most people who solved problem E 1107E - Vasya and Binary String did it in . Does anyone know if a faster algorithm is possible?

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

Why can't I see my rating change?

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

    Because system testing is not over. After three hours you can see the change.

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

Can anyone please explain the logic to solve E?

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

anyone knows why this outputs 1 in testcase 4 in problem D

https://mirror.codeforces.com/contest/1107/submission/49044759

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

Is system Testing done?? If not why is taking so much time? If yes why is there no rating change still?

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

Ideally, How long does it take for the ratings to update in contests like these ?

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

    Get a good night sleep and wakeup, It will be updated.

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

The predictor does not work well with me

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

I still can't see the difference between the normal round and the educational round... My guess is the difference in problem style. Am I right?

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

    The rank list mechanism is different. The educational round is more focused on concepts and logic whereas normal round is more focused on the right/optimal way of implementation of your logic.

    The hacking mechanism is also different.

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

      Aha I got it. Thank you very much!

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

It is really not a good time for programmers in China, you have to drink a lot of coffee to keep yourself from sleeping:(

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

In question 'D' I am getting "Denial of judgement" "crashed" at test case 59. can anyone explain why does this happen .

Here is my solution-https://mirror.codeforces.com/contest/1107/submission/49348206

→ Reply