Supermagzzz's blog

By Supermagzzz, history, 12 days ago, In English,

Hello Codeforces!

We, Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, are ITMO students, who want to contribute to Codeforces community, went to MikeMirzayanov and offered him to help with rounds testing. But MikeMirzayanov invited us to create our own round with his help. And now...

We're glad to invite you to Codeforces Round #603 (Div. 2), which will be held on Nov/29/2019 17:35 (Moscow time). It will be rated for all participants with a rating below 2100. You will be given six problems and two hours to solve them.

The problems were invented and prepared by Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.

Special thanks to:

  • MikeMirzayanov for great systems Codeforces and Polygon and coordinating round preparation.

UPD: Scoring: 500 — 1250 — 1250 — 1750 — 2500 — 3000

We hope you will enjoy the problems. Good luck, wish you a high rating!

UPD1.5: Thanks for participating! Congratulations to the winners!

Top 5 Div. 2:

  1. Lazyeval
  2. twitch.tv_wookje
  3. Byzantium
  4. rainboy
  5. fuyuki

Top 5 Div. 2 + unoffical:

  1. Lazyeval
  2. twitch.tv_wookje
  3. socketnaut
  4. KrK
  5. Byzantium

UPD2: Editorial is out!

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

»
12 days ago, # |
  Vote: I like it +30 Vote: I do not like it

Are there any subtasks?

»
12 days ago, # |
  Vote: I like it -41 Vote: I do not like it

Please share the score distribution.

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

    Why do you have negative contribution?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -30 Vote: I do not like it

      I am trying to get the feel and nature coders. Right now, I am not aware of it so this may be a reason. Hope for positive contribution soon :)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It will be shared about an hour before the contest . Does it make any difference though?

»
12 days ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

I hope tomorrow I will be able to reach 2100 :)

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Maybe the dislikes for your comments are because your avatar...

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      Or because it's spam

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 2   Vote: I like it -11 Vote: I do not like it

      Or maybe he just posts comments wich are not usefull at all and reading them is not a good way of spending time

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Me too!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I am not able to reach 2100 because I have missed a +1 in my code..:(

»
12 days ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

This time no copy-pasted part ! ;)

»
11 days ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Good luck and high rating!

»
11 days ago, # |
  Vote: I like it -31 Vote: I do not like it

hope to become specialist in this contest.

»
11 days ago, # |
  Vote: I like it -53 Vote: I do not like it

Is it rated?

»
11 days ago, # |
  Vote: I like it -30 Vote: I do not like it

I hope to become specialist in this contest. :)

»
11 days ago, # |
  Vote: I like it -27 Vote: I do not like it

Hope it's not mathforces like last time! GLHF!

»
11 days ago, # |
  Vote: I like it -14 Vote: I do not like it

good luck for all

»
11 days ago, # |
  Vote: I like it -15 Vote: I do not like it

Scoring Distribution?

»
11 days ago, # |
  Vote: I like it -18 Vote: I do not like it

Score distribution?

»
11 days ago, # |
  Vote: I like it +9 Vote: I do not like it

There is a bug. I see some yellow coders in the official standings!

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve A?Am not sure of my solution :(

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

    Sort by magnitude. It is optimal to pair the smallest with the largest until the largest and the middle are equal (or as close as you can), then pair the smallest with largest once and smallest once until you run out of smallest.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice solution!Thought so too, but tried different approach....:( Thanks BTW!

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got timeout using this :? Python3.6

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can't simulate the optimal solution directly, it's too slow (you could take up to hundreds of billions of steps across all $$$1000$$$ test cases). You need to find a way to calculate the steps mathematically.

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did not actually do the simulation directly — it's just a description of how to go about this optimally. To simulate the simulation, I found difference between highest and middle, and checked whether it is higher than lowest or not. If so, then answer = lowest + middle.

        Otherwise, set lowest = lowest — diff and set highest to middle. Now remove lowest/2 from highest and mid, add answer = (lowest%2==0? lowest : lowest — 1) + min(mid, high)

        Not a very good solution (some repeated code) but you can see 65992022 to get the idea

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found A very similar to this problem: https://codeforces.com/contest/1260/problem/B

»
11 days ago, # |
  Vote: I like it +59 Vote: I do not like it

Non-dp solution for F:

Solution
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Your solution is so overcomplicated, but still very cool.

    Linear solution to F
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi! That's a nice solution. I just tried your approach. But, I believe that the case of deleting all edges from one of the trees is also covered as a special case in the minimum cut algorithm. Instead of outputting $$$max(a-1, b-1, a+b-maxflow)$$$, I just outputted $$$(a+b-maxflow)$$$, and it got AC.

»
11 days ago, # |
  Vote: I like it +38 Vote: I do not like it

A-E all classical problems

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have solved similar problems like A-E ? If so , would you please give the links of some of those problems ?

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

      They indeed looked familiar.

      E.G. as far as I remember the solution of A was also needed to solve DeleteArrays from SRM770

»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

The problems were great! Who can tell me how to solve C?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I found that if I just iterate for divisors till sqrt(A), then all quotients I get for higher values lie in a single continuous range.

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

    You could refer to this post.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think i am right,but the answer is TLE.how to solve C?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lol, your solution uses t both as the count for tests and n / i so it runs forever.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Imagine we iterate through k

    n/k — n/(k+1) = n/(k(k+1))

    this means that if k > sqrt(n) then at each step you will be decreasing less than 1

    so, after that you will pass for all non negative integers

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

    start diving from i=1 and keep increasing unless u don't get same value when doing floor(x/i) after that it's a continuous decrease like for x=1000 at i=37 u will get floor(1000/37)==27 which is repeat for i=36. This means after 27 all are included like 2, 25...2,1,0. but i still got timeout. ;? but i see rohit_goyal has more optimal solution

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can also start from 1 and do binary search every time that until what number n /j == i. and then move the pointer to that number .

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, for fixed n f(k) = n/k is a monotonous function. Binary search is a solution in O(Ans*log(n)).

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm sad I didn't see D solution is it graphs or something

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

    I think it was related to Union — Find algorithm...

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes ; one can connect strings who have a common character ( As these two strings are equivalent ) ; and finally answer is number of connected components !

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

    It can be solved greedily as well.

    Start with the string having the most number of distinct characters and simultaneously mark the characters you have gone through. If we come across a string in which all it's characters are already marked, we need not count that string in our final answer.

    PS: The DSU Approach is great.

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 6   Vote: I like it 0 Vote: I do not like it

      The greedy approach fails at test case 68. i tried it! when the strings of have same length have same number of unique elements and all are different it fails.

      for example

      abcd efgh fa

      expected — 1 output — 2

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Is pD really that easy ?? I tried to do it with a bitmask-things but I couldn't. Can somebody help?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For each letter find a word that contains it and build a graph by connecting every other word that contains it with that word. The answer is the number of connected components of that graph.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    it's dsu. But only there are only 26 arrays, so I think bruteforce may be accepted too.

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

    A node is a char

    for each pair of letters x,y in a string add an edge x->y

    The answer is the number of connected components

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

    It is fairly simple dsu, just build groups by contained characters.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For every password you could build a set of letter. then if 2 letters are in 2 passwords — just join the sets. after count how many sets left

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow I just realized that I totally misunderstood the Task. Rating goes down again!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use simple approach such as brute force :))) 65990114

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Your solution gives wrong answer on test case 67, though its accepted. Quite strange

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it didn't have test case 67, bro!!

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

          It does have test case 67. Check my 2nd last submission, I just pasted your code and it gives WA kn test 67

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Wow, this is my first time seeing something like that.

            Is that a hack test case?

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            New test case after contest ??

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes ; for each string ; you may store a bitmask corresponding to it ; and then the strings with common character could be joined ; and at last answer will be number of connected components !

    A code which does bitmask + DSU : https://codeforces.com/contest/1263/submission/65980587

»
11 days ago, # |
  Vote: I like it -8 Vote: I do not like it

In F, wires between nodes do not intersect. shouldn't it be bolded?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Hmmm, my bad. I didn't see the condition It is guaranteed that each grid is a tree, which has exactly n leaves and each leaf is connected with one device. Also, it is guaranteed, that for each tree exists a depth-first search from the node 1, that visits leaves in order of connection to devices.

»
11 days ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

I don't understand why such a tight time limit was put in E. It cost me multiple TLEs when writing output using cout, however with printf it passed.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same issue — little bit annoying lol

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

      VERY annoying actually.

      I used Java, and with Java lazy SegTree doesn't pass at all :(

      • »
        »
        »
        »
        11 days ago, # ^ |
        Rev. 14   Vote: I like it 0 Vote: I do not like it

        you can solve it without lazy just normal segTree my submission (that was after contest because I forgot ind = max(ind,0) xD )

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too was getting TLE, but it was a coding error in my case though, I was calculating values again and again, instead of just referencing already stored values... :(

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +42 Vote: I do not like it

    Jury has a simple linear solution with stacks in this problem.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Ah, that's cool, but imho segment tree with lazy propagation isn't really a bad solution to this problem.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Its a little sad though when you correctly implement everything, but still get TLE because of using Java :(

      I think the time limit should be 3 seconds, or N should have been less than 200,000.

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

        After the contest I optimized a tiny bit and got it to pass. I changed all the longs to ints first (I'm not sure if this actually did anything meaningful). Most importantly, you're querying three times over the segment tree per change, which can be reduced to one (Query max and min at the same time because they're over the same range and manually store the prefix sum over the entire array). However I see that you fail on TC 4, which means that you might have to optimize your seg tree implementation.

        Edit: Some other simple optimizations, I found .toCharArray() to be faster than charAt(i). Also when you build your segment tree you can initialize your tree as zeros to save some time

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think cout endl cause TLE. Pls read this https://codeforces.com/blog/entry/43780 for more information.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do first if there are n piles.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its very similar:
    min(sum of n-1 smallest piles, sum of all piles / 2 floor)

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that if you want you could derive the condition considering finally piles are of the form : { 0 0 0 0 0 0 A 0 0 0 ...... 0} So you could apply constraint between A, sum of all piles and largest pile's value and find minimum A, and hence maximize the value of answer!

»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Is intended solution for E Segment Trees w/ Range Propagation and then leveraging min/max/sum?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution on that passed in 202ms so I guess yes.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it wasn't intended to be seg-tree in any way, although many solutions passed... It can be solved with 2 stacks storing brackets, one from left and other right, with 2 arrays(although i used sets 66013420) to check the max and min on both sides

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the same but got runtime eror, can you check my solution?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's seems like STL stack overflow error, your stack couldn't allocate 5*10^5 size... although my STL vector could.

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

In Problem E.

How to update number of different color need to use if text is correct

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I found that we can use the maximum prefix value(by assigning openings as 1 and closings at -1) that one can get as answer, because answer is longest opening sequence(it may have some complete brackets within) and any closing would just decrease the answer

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm so confused where do I wrong on E. I was so close to an AK.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone got the wrong answer on pretest 2 of A and then got correct?

Or any possible testcase where this could get wrong?

Thanks in advance :)

My solution — https://codeforces.com/contest/1263/submission/65990422 (I stresstyped every possible case because I was getting the wrong answer :( )

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

    I believe yours fails on the input 3 4 5 since then it returns 5 whereas 6 is the answer.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On the case 10 15 20 your code returns 20 while the answer is 22.

»
11 days ago, # |
  Vote: I like it +51 Vote: I do not like it

strange round. D is just — "oh my, write DSU". E is just "oh my, write segtree with mass updates".

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

    No DSU was needed in D. Create N+26 nodes (N nodes for each string, 26 nodes for each character). Connect node of string and character, if the string contains this character. Answer = number of connected components among nodes corresponding to strings.

»
11 days ago, # |
  Vote: I like it +32 Vote: I do not like it

I think ideas of CD are quite standard. E is just a boring version of this.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Very easy div2 contest.

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For probB ,My solution passed pretest 2 . But failed on test 2 , is'nt it amazing .

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

So, I tried to solve E using a Segment Tree with lazy propagation. I wrote the bracket series as a prefix sum, for example like [1,2,3,2,1,0,-1,0,1]. Then, to process 'L' and 'R' moves I just shifted an index variable. To process '(' and ')' updates I simply lazily updated all the numbers in the prefix after the index i. Then, to find if it was valid or not, I simply used Segment Tree range min and range max query.

In total, my algorithm was Nlog(N). And yet it TLED. Any reason why? (I used Java)

»
11 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

A is quite beautiful if you prove things by construction and the triangle inequaltiy.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B..?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For repeating pins, replace their first digit with the digit that is not present in other pins first digit. Since maximum value of n is 10, we can be sure that all digits will be distinct after the process.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the pin is $$$Pi$$$, Check from $$$Pi-100$$$ to $$$Pi+100$$$, get the one which is unused and gives min difference with original

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought it like this : Say I iterate over the input values(as strings) and if I have more than 2 strings of current type, I can change it to a whole other string just by changing 1 character because if I just change a single character, I can get 40 strings or nearabout that number of strings, so I just find such a string by brute force, trying changing each character so 4*10 combinations are there, and changing string value to the one which is not present in my set of strings, and incrementing the count of moves by 1.Finally I print all the new strings(or old ones in case of unchanged....)!

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, my algorithm was exactly what you said. I just realized that my implementation was wrong..TT

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The problemset is nice although i performed badly this time :(

»
11 days ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it

"L — move the cursor one character to the left (remains in place if it already points to the first character);"

"It is guaranteed that all characters in a string are valid commands."

Somehow I thought the second line meant that there can't be an input where you go left from the first position...... (and it doesn't seem to even be in the pretests?)

(Also trying to fail $$$O(n\log n)$$$ segtree solutions with $$$n \le 10^{6}$$$ and 1s TL is not really cool as many such implementations actually would pass. I think this has been said by many people in different contests, but either give up on failing these solutions or increase the constraints so that it would clearly fail all (or at least those without extremely heavy constant optimizations attempts) "bad solutions" (in this case it's hard to increase because of I/O size though, so maybe some input/output compression would work))

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

    I think this might have been in pretest 5. Luckily, I had an assert that checked L was valid... But I agree this is confusingly worded

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

      Welp my solution failed system tests because of that so I thought it might not be in the pretests.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think it is in the pretests either, as I failed on the same thing.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I failed on pretest 5 due to my pointer going out of bounds i.e. -1, so it was in the pretests, although it didn't affected ur solution.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't deal with this situation in my program,pretest passed,but system test failed.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i got timeout for 1st question :/ My approach: subtract difference of 2nd_max and 3rd_max from 1st_max and 2nd_max. count changes to count+difference(2nd_max-3rd_max) Now find 1st_max and 2nd_max and decrease them by 1 and count changes to count+1. Output is optimal but not able to pass the time limit. Please share ur algo if u passed

»
11 days ago, # |
  Vote: I like it +19 Vote: I do not like it

MikeMirzayanov Did you just banned Ashishgup only because he wrote "A-E are classical".

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +110 Vote: I do not like it

    He is not banned, he is temporarily in the read-only mode. I believe that the rules should be the same for everyone. And any discussion of problems during the contest is unacceptable. We cannot predict how this or that opinion about the problems will affect the participants. I am pleased to discuss the problems, but this can only be done after the end of the round.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Too much easy problem set!

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anybody tell me if this solution is correct for problem E? My solution use segment tree without lazy propagation. For each node in the segment tree I know v[nod].left = number or '(' without a pair (basically open) , v[nod].right = same but for ')' and v[nod].depth = how many colors do I need. How to find v[nod].depth if we know every information for its children? v[nod].depth = max ( v[ 2*nod ].depth, v[ 2*nod+1 ].depth) maximum depth of its children + min ( v[2*nod].left, v[2*nod+1].right) this if for: '(' CONFIGURATION + CONFIGURATION '))' so in this case I increase the depth with 1 because I make new pairs. I had a bug in implementation so I couldn't submit it, but does anybody have the same approach?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Alternatively, You can consider point updates +1 for '(', -1 for ')' and 0 otherwise. Then maximum prefix sum is depth and minimum prefix sum should be 0 for correct sequence.

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

      yeah, this is the approach with lazy propagation. Or, could it be solved without lazy?

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

        You can maintain the maximum and minimum prefix for each segment node. Then you won't need lazy propagation.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Time limit for different languages is different or same for all?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone Explain How To Solve Problem C? I kind of felt it was related to divisors

»
11 days ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Maybe I am the only one who solved B using mincost-maxflow.

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

    maybe I am the only one who solved B using randomization?

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

      I used srand(time(0)) ; in your code and got WA at first at test-8 , then on test-10. But without using srand(time(0)) , your code gets AC . Any idea why this is happening ?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    I'm calling the police

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Yeah, you used a bomb to kill a mosquito.

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

    I thought of using Hopcraft Karp algo. but gave up even before I began to code XD

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Was it bipartite matching implemented with flows? Cool! Here is my idea: start with the 10 pins; this is part A. Connect each pin with numbers that differ in one place or don't differ at all. You get up to 40 neighbors. This is part B. Now find a perfect matching between A and B. The numbers which pins are matched to are the answer.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How?

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

My first submission to D got accepted but it doesn't pass

4 
a 
ac 
b 
cb
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Answer should be 1 right? I saw both of your submissions giving 1 as output :3...

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

      When I ran it in the Codeforces custom test it printed 2.

      My first submission should be wrong because my find() function recursively calls find(cur) instead of find(par[cur]), and when I insert the numbers into set< int > cnt, I should insert find(par[cur]) instead of par[cur].

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Seems that there's a problem in judge data... Some other solutions also got AC which was actually wrong.. sad :(

»
11 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Good contest!

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

I think the problems were much easy and this should've been a div 3... anyways... thanks to the setters.

»
11 days ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

MikeMirzayanov Supermagzzz My solution for E passed the pre-tests, but after system testing gave TLE on test case 5 which was part of the pretests.65979337

Moreover changing language from c++17 to C++14 got accepted 65994359.

Can you look into it.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    See, your solution is on the edge between OK and TL. It is just a random it fits in TL or not. Just try to improve your solution a bit. Also, it is a good practice to verify that your solution fits in TL with some gap on pretests.

    As I see this problem can be solved even on Python, so I don't think the TL is too tight.

»
11 days ago, # |
  Vote: I like it +9 Vote: I do not like it

I Got AC in problem D, I think it shouldn't pass. Consider the following test case: 3 asd qwe aq

»
11 days ago, # |
  Vote: I like it +31 Vote: I do not like it

I used a O(n) algorithm to solve Problem F.

It can be proved easily that when each of the electrical devices is covered by just one grid, the answer will be the best. And the problem guarantees that every nodes x in the grids will cover a range [l, r]. That means we can disconnect the electrical devices with the gird if we erase the edges connecting to the nodes in the subtree of x. We can get it by doing a dfs/bfs. Then the problem is transfromed to an easier problem: There are some ranges, each range has a value. we need use them to cover the range [1, n] and maximize the sum of these values. dp[i] means the maximum sum of value when the range [1, i] is be coverd. For dp[i], we just need to check the ranges beginning at i + 1 to transform it. So every range will be used just one time. It also solves in O(n).

»
11 days ago, # |
  Vote: I like it +16 Vote: I do not like it

F can be easily done in $$$O(n)$$$

https://paste.ubuntu.com/p/8SJHkS5w6d/

I'm very confused about range of $$$n$$$ in contest....

»
11 days ago, # |
  Vote: I like it +15 Vote: I do not like it

It is the first time I reach Purple, thanks to this interesting contest.

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't understand why my submission for B got WA.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Study how your code performs when the input is 3 0000 0000 1000

    Your code makes 2 moves, whereas the minimal moves required is 1.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

The templet of segment tree used in Problem E. can be found at https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/UESTC/2156.cpp

But someone else used that templet in E and our codes are almost the same. So I was blocked, but I promise that we didn't communicate with each other during the contest.

I wonder how to solve the misunderstanding.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A idea is same as https://codeforces.com/problemset/problem/478/C (Table decorations).

»
11 days ago, # |
  Vote: I like it -13 Vote: I do not like it

MikeMirzayanov, why has my 65968043 to 1263A - Sweet Problem been "Skipped"? It's the first time when i see this. By the way, I didn't cheat. At the round verdict was all pretests passed and I leave round with happy thought that I 'll become green. Now I am very disappointed.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Your earlier submission of A accepted so your later submission is skipped.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    This is really unfair, king. I think we all must do everything possible of us to correct this blatant act of injustice. MikeMirzayanov, you really need to look into this horrible situation.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Instead of a thousand words:

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      Could you check another accounts by IP? Especially my time is different.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -41 Vote: I do not like it

      MikeMirzayanov, maybe I could prove my innocent. Before send I program in ideone.com . In this site there is a page "Recent code". This is my code: https://ideone.com/L2fM6l . It's a public paste. On 23:22 I have found this code here (https://ideone.com/recent/19). So, all users that use ideone are at risk be unrated, don't they?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +38 Vote: I do not like it

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        In the terms of agreement when you register, you are forbidden from sharing or publishing your code before the contest finished. Also I have no idea why you need to paste your code onto public paster. No matter intentionally or not, the fact that your code is somehow published makes your code skipped. This would be fair for everyone.

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the answer for this input of problem D?

4
a
b
ab
acd

EDIT: How about this?

3
abc
abd
abe
»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Test case for 1263D - Secret Passwords was weak.

This submission 65988894 gives output 2 for input 3 ab bc ca, but output should be 1.

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

    yeah, I got accepted with the false solution(naive one), after the contest, you can check 66023526 which fails for a simple test case like this: 7 a b c d ab cd abcd

    Here the correct answer is 1, but the program outputs 0.

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

So, I am done with the comments, would like to read the editorial now. Thanks!

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

in the rating changes the rating predictor rating is not same as the changed rating for this contest has codeforces changed their rating algorithm and forgot to update the predictor????

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

I don't understand what hacking is. Does anyone explain it to me? And when I get hacked?

»
11 days ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Well at least I found out about how editors color the brackets in code today! XD

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In my experience they mostly stop responding or crash horribly when you load a huge file of parentheses...

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess it indicates brute force implementation in editors. :D

»
11 days ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Can anyone please tell me how to hack a submission after the contest ? I am getting this message "You cannot hack the submission"

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

This was a very interesting contest !

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There seems to be a problem with the C compiler for problem C. My solution 66003014 submitted in GNU C11 TLEd on test 4 but the exact same solution submitted in GNU C++17 66003340 passed comfortably MikeMirzayanov supermagzzz

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

    You have to choose the compiler yourself. Different compilers have different efficiencies (optimizations).

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

      I'm pretty sure GNU C11 is the only compiler available for C. There is no reason why a SQRT(N) solution would timeout when compiled in C vs when compiled in C++ (both are compiling the SAME SOURCE code). My guess is that an incorrect TLE multiplier was applied(some sites apply multiplier for different languages so that implementation in slower languages like Java don't TLE)

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

        printf is very slow in C11

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Checks out! Replacing printf with putchar brought down the execution time from 2s to 46 ms. Thanks for pointing it out. Something to remember during future contests

»
11 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

If you want to see my personal editorials for the problems, come to my blog!:p CF Round 603 Broken Editorial

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

WDYT about solving 1263F - Economic Difficulties with min-cost-max-flow? Let every edge have flow one and cost one. The sink is connected to the two root nodes, and the n devices have a single outgoing edge to a sink node; each with flow 1. The min-cost flow will then use as few edges as possible. MCMF can be solved in $$$O(E^2)$$$, which should be small enough since $$$E\approx 2000$$$.

If I'm right, then the whole of the problemset could be solved pretty easily with standard copy-pastable algorithms.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Between witch nodes are you running min-cost-max-flow ?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I connect a source to the two root nodes, and I connect all devices to a sink. All edges have capacity one.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you pass $$$k>1$$$ units of flow on some edge then these edge have cost $$$k$$$ not $$$1$$$, so I think that your solution are wrong, you have implemented it?

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    My solution is related to maximum independent set. Consider each tree as a part in a bipartite graph with the vertices are its edges. Now if two edges from different trees cannot be removed simultaneously, connect a edge between them in the bipartite graph. Answer is the maximum independent set of the bipartite graph.

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

when the editorial will be posted?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Problem A solvable with binary search? If yes, can anyone explain a bit :)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't find the tutorial. I saw someone solved problem A with the following idea. sum <- r+g+b if the smallest two of r,g,b is smaller than the largest one ans = the sum of the smallest two else ans= (r+g+b)/2

Can anyone prove the correctness of it mathematically?

  • »
    »
    10 days ago, # ^ |
    Rev. 4   Vote: I like it +4 Vote: I do not like it

    Assume that the values are sorted $$$a \leq b \leq c$$$

    If $$$a + b < c$$$, then the optimal strategy is to take $$$a$$$ with $$$c$$$ until $$$a$$$ is gone, then take $$$b$$$ with $$$c$$$ until $$$b$$$ is gone. It is impossible to access the rest of the candies in $$$c$$$. Total number of moves = $$$a + b$$$.

    Otherwise, the optimal strategy is to take $$$a$$$ with $$$c$$$ until $$$c = b$$$, at which point $$$a := a - (c - b)$$$, then take $$$b$$$ with $$$c$$$ until $$$a = b = c$$$. Then, there are three sub-scenarios:

    • $$$\geq 2$$$, in which case you can take $$$ab$$$, $$$bc$$$, $$$ac$$$ and decrease all of them by two, then repeat

    • $$$= 1$$$, in which case you just take any two and leave a single piece,

    • $$$= 0$$$, in which case you obviously stop

    Since the strategy for this scenario always leaves $$$0$$$ or $$$1$$$ candies, the number of steps is $$$\lfloor \dfrac {a + b + c} {2} \rfloor$$$.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm pretty new to Codeforces and competitive programming in general. Where do I find the editorials to the problems?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will Editorials be updated ?

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why MCMF is wrong for F ? see some MCMF solution with same wrong answer on test 5. code

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I figured it out .I miss understood MCMF.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, can you share why is it incorrect?

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

        the cost of flow is flow multiply the the cost of this pipe .if a pipe with flow more than one the answer is not equal.

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

I solved problem E in O(n) by six stacks.

As we can see, for a regular bracket sequence, we can calculate depth of it by simply calculating the max prefix sum of bracket sequence by assume '(' for -1 and ')' for 1,else for 0.

e.g

"((0)())" can convert to 1 1 0 -1 1 -1 -1,and the prefix of it is 1 2 0 1 2 1 0,which the max value is 2 for the answer.

However,we have to deal with the irregular bracket squence like ")(",because it should be output -1(for irregular) instead of 0,this can be solved by calculating the min value of ths prefix sum array.If it is a negative number, it must be a irregular sequence.

Now we just need to deal with the problem by what we said before.

We maintain two stacks for prefix sum,stack A for restoring from begin to current cursor,stack B for current cursor's next position to the end of the prefix array.We can see the each operation will only happen in the curosr's postion,so if the cursor move to the left,we just need to pop the top value of stack B to stack A,moving to right is same.

e.g

"((0) ())", space for separating. For stack A,it is [1,2,0,1]. For stack B, it is [1,2,1]**(looking from right to left,it is '))(')**.

In the same way,we maintain two stacks for max prefix sum and two stacks for min prefix sum.

Thus we can calculate the answer by these stacks just check the top value of prefix sum stack A and prefix sum stack B are the same and sure two min stacks's top value is >=0,if all the condition is true,the answer is the max of two max prefix stacks

The code is here 66020705

Sorry for my poor English >_<

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

This contest is so great!!!

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1263/submission/66026507 how could this problem got accepted ? it is giving wrong answer in this test case: 3 ab cd da output:2 ans:1

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For me, A is still harder than B,C and D... It required more time than any other task for me... What's the idea behind solving it in one line?

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

    a = [r,g,b] a.sort(reverse = True)

    ans = 0
    
    if(a[0]>=a[1]+a[2]):
        ans = a[1]+a[2]
    else:
        ans = a[0] + (a[1]+a[2]-a[0])//2

    if the maximum of r,g,b is greater than the sum of the remaining two terms than the answer is sum of those two terms.

    else the answer will be maximum term + floor((extra sum of next max two terms)/2)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you help me find a mistake in my code of Problem B... https://codeforces.com/contest/1263/submission/66032322

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

      Your code doesn't properly maintain the order of the PINs given in the input. It is appending the changed ones to the end of the list.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve problem E using lazy segment tree? :)

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem with problem D is still not fixed? There are still WA solutions out there having AC verdict. :/

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Verdict won't change as old submissions won't be rejudged even if some of them are hacked later. But new submissions will face stronger tests so WA solutions will probably not get AC now. See this blog

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, the contestants who submitted wrong solutions and still got AC, will still get the points?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It was fun participating! Thank you for the contest and the editorial!