Supermagzzz's blog

By Supermagzzz, history, 5 years 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 29.11.2019 17:35 (Московское время). 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. saketh
  4. KrK
  5. Byzantium

UPD2: Editorial is out!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Are there any subtasks?

»
5 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Please share the score distribution.

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

    Why do you have negative contribution?

    • »
      »
      »
      5 years 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 :)

  • »
    »
    5 years 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?

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

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

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

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

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

      Or because it's spam

    • »
      »
      »
      5 years 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

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

    Me too!

  • »
    »
    5 years 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..:(

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

This time no copy-pasted part ! ;)

»
5 years ago, # |
  Vote: I like it -31 Vote: I do not like it

hope to become specialist in this contest.

»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

good luck for all

»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Score distribution?

»
5 years 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!

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

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

  • »
    »
    5 years 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.

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

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

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

      got timeout using this :? Python3.6

      • »
        »
        »
        »
        5 years 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 years 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

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

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

»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Non-dp solution for F:

Solution
  • »
    »
    5 years 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
  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

A-E all classical problems

  • »
    »
    5 years 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 ?

    • »
      »
      »
      5 years 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

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

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

  • »
    »
    5 years 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.

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

    You could refer to this post.

  • »
    »
    5 years 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?

    • »
      »
      »
      5 years 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.

  • »
    »
    5 years 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

  • »
    »
    5 years 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

  • »
    »
    5 years 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 .

  • »
    »
    5 years 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)).

»
5 years 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

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

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

  • »
    »
    5 years 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 !

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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

»
5 years 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?

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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

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

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

  • »
    »
    5 years 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

  • »
    »
    5 years 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!

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

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

    • »
      »
      »
      5 years 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

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

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

        • »
          »
          »
          »
          »
          5 years 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

          • »
            »
            »
            »
            »
            »
            5 years 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?

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

            New test case after contest ??

  • »
    »
    5 years 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.net/contest/1263/submission/65980587

»
5 years 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?

  • »
    »
    5 years 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.

»
5 years 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.

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

    I had the same issue — little bit annoying lol

    • »
      »
      »
      5 years 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 :(

      • »
        »
        »
        »
        5 years 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 )

  • »
    »
    5 years 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... :(

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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.

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

        How to use segment tree WITH lazy propagation in this problem? I came up with a solution only needed to modify a single position.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do first if there are n piles.

  • »
    »
    5 years 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)

  • »
    »
    5 years 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!

»
5 years 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?

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

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

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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.

»
5 years 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

  • »
    »
    5 years 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

»
5 years 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.

»
5 years 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.net/contest/1263/submission/65990422 (I stresstyped every possible case because I was getting the wrong answer :( )

  • »
    »
    5 years 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.

»
5 years 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".

  • »
    »
    5 years 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.

»
5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very easy div2 contest.

»
5 years 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 .

»
5 years 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)

»
5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B..?

  • »
    »
    5 years 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.

  • »
    »
    5 years 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....)!

    • »
      »
      »
      5 years 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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years 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))

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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.

      • »
        »
        »
        »
        5 years 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.

  • »
    »
    5 years 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.

»
5 years 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".

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Too much easy problem set!

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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.

»
5 years 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.

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

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

    • »
      »
      »
      5 years 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 ?

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

    I'm calling the police

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

    Yeah, you used a bomb to kill a mosquito.

  • »
    »
    5 years 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

  • »
    »
    5 years 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.

»
5 years 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
  • »
    »
    5 years 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...

    • »
      »
      »
      5 years 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].

      • »
        »
        »
        »
        5 years 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 :(

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Good contest!

»
5 years 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.

»
5 years 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.

  • »
    »
    5 years 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.

»
5 years 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

»
5 years 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).

»
5 years 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....

»
5 years 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.

»
5 years 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.

  • »
    »
    5 years 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.

»
5 years 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.

»
5 years 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.

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

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

  • »
    »
    5 years 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.

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

    Instead of a thousand words:

    • »
      »
      »
      5 years 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?

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

      • »
        »
        »
        »
        5 years 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.

»
5 years 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
»
5 years 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.

  • »
    »
    5 years 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.

»
5 years 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!

»
5 years 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????

»
5 years 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?

»
5 years 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

  • »
    »
    5 years 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...

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

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

»
5 years 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"

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This was a very interesting contest !

»
5 years 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

  • »
    »
    5 years 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).

    • »
      »
      »
      5 years 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)

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

        printf is very slow in C11

        • »
          »
          »
          »
          »
          5 years 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

»
5 years 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.

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

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

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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?

  • »
    »
    5 years 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.

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

when the editorial will be posted?

»
5 years 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 :)

»
5 years 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?

  • »
    »
    5 years 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$$$.

»
5 years 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?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will Editorials be updated ?

»
5 years 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

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

    I figured it out .I miss understood MCMF.

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

      Hi, can you share why is it incorrect?

      • »
        »
        »
        »
        5 years 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.

»
5 years 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 >_<

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

This contest is so great!!!

»
5 years 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?

  • »
    »
    5 years 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)

  • »
    »
    5 years 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.net/contest/1263/submission/66032322

    • »
      »
      »
      5 years 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.

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

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

»
5 years 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. :/

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest!