By PikMike, history, 3 weeks 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 V--gLaSsH0ldEr593--V 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 CoodeForces 4
5 Sevlll 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 V--gLaSsH0ldEr593--V 0:01
B neal 0:02
C neal 0:05
D V--gLaSsH0ldEr593--V 0:10
E DankShadow 0:10
F V--gLaSsH0ldEr593--V 0:44
G Kalam 0:17

UPD2: The editorial is out

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

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

clashing with codechef lunchtime please delay it.

»
3 weeks ago, # |
  Vote: I like it -84 Vote: I do not like it

Clashes with indian entertainments

»
3 weeks ago, # |
  Vote: I like it +89 Vote: I do not like it

Clashes with Educational 59

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

中国玩家修仙场:)

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Clashes with CodeChef lunchtime. Please reschedule.

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Happy Republic Day Indian Coders!

»
3 weeks 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.

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

Hope that will be a lot of hack today xD

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice picture though~ :D Is that the campus?

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Give me a purple name plz...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It shows the possibility of being a good hack :D, hope every one of us succeed!

»
3 weeks 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++

»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

Clashes with clans

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

CodeForces OR CodeChef???

Both.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -30 Vote: I do not like it

Fuck problem statements. I'm done.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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...

»
3 weeks 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 ?

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

nice problems ^^ , how to solve E ?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What's the DP state though?

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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 ><

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

contest was so easy :D

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

  • »
    »
    3 weeks 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...

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      What is worst case in your opinion?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.
      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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
      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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??

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

what was the state for the DP in problem E?

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    It's

    • »
      »
      »
      3 weeks 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.

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

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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

»
3 weeks 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?

»
3 weeks ago, # |
Rev. 3   Vote: I like it -26 Vote: I do not like it

Deleted

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    lengthy code? for which problem?

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

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

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

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

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        root of all numbers in set are equal to x

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    from sys import stdin
    
  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

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

      Thanks a lot man, will try asap :)

    • »
      »
      »
      3 weeks 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)

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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!

»
3 weeks 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://codeforces.com/contest/1107/submission/49020250 sbd help me,pls

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

Deleted

»
3 weeks ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

D was a nice problem.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve G with binary search?

  • »
    »
    3 weeks 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)

»
3 weeks 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.

»
3 weeks 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://codeforces.com/contest/1107/submission/49007458

  • »
    »
    3 weeks 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.

»
3 weeks 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 ?

»
3 weeks 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 ?

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks 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

»
3 weeks 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://codeforces.com/contest/1107/submission/49004601

  • »
    »
    3 weeks 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.

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

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

cpp not greedy only where algorthims, cf'think is totally wrong contest greedy from a to d, why?!

»
3 weeks 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])
»
3 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

How to solve E problems pls?

  • »
    »
    3 weeks 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

»
3 weeks 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)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    This is Educational round who cares about get successful hacks?

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yeah but there is a separate leaderboard for hacking

        • »
          »
          »
          »
          »
          3 weeks 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

»
3 weeks 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

»
3 weeks 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

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't I see my rating change?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the logic to solve E?

»
3 weeks 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://codeforces.com/contest/1107/submission/49044759

»
3 weeks 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?

»
3 weeks 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 ?

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

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

The predictor does not work well with me

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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?

  • »
    »
    3 weeks 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.

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

      Aha I got it. Thank you very much!

»
3 weeks 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:(

»
2 weeks 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://codeforces.com/contest/1107/submission/49348206