dario2994's blog

By dario2994, 11 days ago, In English

General comments

Broadly speaking, problems A-B-C-D were "div2 problems", while F-G-H were "strong grandmaster problems" (with E staying in the middle). I did not expect anyone to solve all the problems and thus I decided to give the scoring F+G=H (so that maybe someone would have solved H).

Many of the problems (A, C, D, E, G) admit multiple solutions. Sometimes the core of the solution is the same (C, D) and sometimes the solutions are truly different (A, E, G).

If you are an experienced participant, I would like to hear your opinion on the problems. Feel free to comment on this post or send me a private message.

Overview of the problemset

Hints

A
B
C
D
E
F
G
H

Solutions

A
B
C
D
E
F
G
H
 
 
 
 
  • Vote: I like it
  • +725
  • Vote: I do not like it

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

Awesome editorial and even awesome questions. After this round, I feel like practicing more now.

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

I really liked this contest. All problems between A and E are well-balanced. They are not almost ad-hoc, and they are not stupid realization. Ideal balance! Thanks for this round!

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

    But i must to say, that in my opinion it is makes no sense to do score distribution like 500-750-1000-1000-1500

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

thanks for blazing fast editorial. Loved the problems <3

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

For problem C This is a classical dynamic-programming task with a twist. Which task does this refer to?

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

    It's quite similar to the longest increasing subsequence, but the condition to pick the previous element is $$$dist(i, j) \leq t_j - t_i$$$ instead of $$$a_j > a_i$$$.

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

      There is the use of upper_bound in the regular longest increasing subsequence problem of O(nlog(n)). But in this problem how I make a binary search. (dist(i,j)≤tj−ti) can give only true or false, not greater than or less than. Actually, I can't be sure my temp array will be sorted.

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

        The "twist" is not binary search: it's that $$$t_j - t_i \geq j - i$$$ and $$$dist(i, j) \leq 2r$$$, hence the condition is true for each $$$i, j$$$ such that $$$j - i \geq 2r$$$.

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

          Oh, thanks. Got it :)

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

            TheScrasse RoyalCoderPRO Can someone please explain what 2*r means? The idea is that if |k−i| is big, then i and k are always compatible. More precisely, if k−i ≥ 2r then tk−ti ≥ 2r How can we be so sure about this?

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

              Since the side of the grid is $$$r$$$, the distance of the farthest vertices (two opposite corners) is $$$2r - 2$$$.

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

              If r == 500 then max distance ever possible from (0,0) to (500,500) dist: abs(0-500)+abs(0-500)=1000 or 2*500 or 2*r.

              So, let i,k (i<k) indices of given data. if i+2*r < k then its possible to go i to k, whatever value tk,ti. Because all t are distinct and sorted. It is also possible to go from all indices less than i to k for the same reason. So no need check indices for less than i. :)

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

              TheScrasse RoyalCoderPRO Got it. Thank you so much. One small doubt. Im sorry if it is stupid. since r is atmost 500 there can only be 25000 intersections right? But n has a value 10^5 which means intersections may repeat also?

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

        After reading your comment a was able to understand editorial Thanks

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

    I think the task is Longest increasing subsequence:- https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

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

it fits easily in the time-limit. it doesn't...

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

    I have quickly checked your last submission during the contest, it seems to me that it is $$$O(n^4)$$$ (you are calling janusz.dinic() $$$O(n)$$$ times). If I am wrong (which is very likely), sorry.

    If you implemented the first solution in the editorial in $$$O(n^3)$$$ and you got time-limit-exceeded, I am sorry, that was of course not intended.

    Since I am here, let me comment a bit more on the time-limit of problem G. I have the feeling that in many flow problems, the general mentality is "let's ignore complexity because any flow implementation will work". In this problem this was not true. A nontrivial amount of contestants got TLE because of this. Before the contest I thought a lot about this time-limit, because I knew it would have generated quite a bit of struggling. The fundamental reason why I decided to keep it as it is, was to avoid $$$O(n^4)$$$ solutions passing and to award contestants that instead of using fancy (but with bad complexity/terrible constants) implementations of the flow algorithm were implementing the good old Ford-Fulkerson (proving its complexity!). It might be that this choice generated more suffering than joy... but as always it is much easier to judge a posteriori.

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

      I run dinic() $$$n$$$ times, but in total, I'll push only $$$O(n)$$$ units of flow (I'm using the network from the previous iteration).

      After the contest, I've changed Dinic to work like Ford-Fulkerson, so it doesn't run bfs. It was a bit faster, which was enough.

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

        That is unfortunate and it is my fault. Hopefully next time I will not make the same mistake.

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

Anyone wasted an hour in B?

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

    I was stuck on B for the entire contest after solving A in 00:04 :'(

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

      Oh I wasted an hour in A.... But I just spend 30mins in solving B problems...

      I think the string can be divided into three situations for discussion.

      Then it will be solved soon :)

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

    I solved A in 00:14 and B in 02:10. That was a hard time.

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

    I solved B at 2:59 .

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

    I couldn't solve B. I got the idea right but I couldn't prove it. Feeling lame especially when you are(were) an expert.

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

    I missed checking if the final ans according to my Code is <=0 then should print "0" ..... :(

    And that costed me almost 2 hrs!!!!

    I don't know though I was upset but I loved the things I tried at that time :)

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

In parallel universe.

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

If $$$a=b+1$$$ and $$$b$$$ is even, then $$$a^b=1$$$.

In Hint $$$4$$$ of the first solution of problem $$$E$$$, maybe it should be $$$a\oplus b=1$$$($$$\oplus$$$ denotes xor)...

Also in Hint $$$3$$$ of the second solution, it should be $$$2^{19}$$$ but not $$$2^19$$$.

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

Many of them could have got ac on D if it were 2*n steps,lol. By the way,thanks for a great contest.Liked it. Thanks for strong pretests

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

Me :Could only solve one, feeling low...

Also Me : After reading the overview of problemset...I am glad I solved A.

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

This is peak editorial writing. From giving some extra time to the ones who were really close to getting AC on H to writing multiple hints for us to be able to figure out the rest of the solution by ourselves. Great work dude!

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

    I love that, I was close to getting C and only read the hints and was able to solve it. A good way to learn is by using hints instead of revealing the whole solution.

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

Thanks for the awesome Tutorial keep it with hints its such a good way of learning and explanation :D !

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

The way of presentation of the Editorial is very Nice. Going through the Hints before The Actual Solution really helps in learning. I request all editorial should be posted like this (Hints and Then solution).

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

I have lost more than 200 rating points in the last 3 contests, Don't really know what's happening :/

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

    You just reached where you actually belonged :P

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

Great format for the editorial! Loved the bunch of hints before the elaborated solution. Thank you!

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

it would have been better , if the editorials were given with the problems in the contest.

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

Here are video solutions for A-E, as well as complaining about gaining rating (apparently)

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

sorry for such a silly question but why am i getting TLE here? 95114705 I tried to form all possible permutations coz the constraints were very small. But still i got TLE. If anyone got time a slight help would be great. Thank you. Have a good day

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

    what is the value of 50! ?(50 factorial).

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

      oh i see. Yeah man you're correct. Thanks man!!

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

    I also did something similar and it worked for me. I am also confused if I should use this or not in the future.

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

      ya i checked your solution. It's somewhat similar. i might have done some silly mistakes. Have to figure out what

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

Can anyone tell why my solution is incorrect for Problem — B ( Chess Cheater )? My approach :

Step 0: Find the initial score and store it in variable sum
Step 1: Find all contiguous Loss substrings and store 
        (length,0) if the substring is not a prefix/suffix 
        (length,1) if it is a suffix/prefix
Step 2: Sort the vector in increasing order, putting prefix and suffix substrings at the end
Step 3: iterate for elements in the sorted vector ( for i=0;i < it.size(); i++ )
        if( k >= it[i]) // meaning we can change the whole interval 
            sum += 2*it[i] +1 if the i'th substring of L's is not a suffix or prefix
            sum += 2* it[i] if i'th substring of L's is a prefix/suffix
            k -= it[i]
        else if( k < it[i] ) // this is the last substring we can change, and we can't change it fully
            sum += 2*k 
            k=0;
Step 5: cout<< sum <<" \n" 

Link to submission : Can anyone point out the mistake kindly? Thanks in advance :)

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

    I had the same solution in contest. Consider the case

    2 0

    WW

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

    Step 2: Sort, ..., putting prefix and suffix substrings at the end

    However, this isn't what happens in the code — you sort by length first, then consider the type.

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

      Yeah, I just figured it out after posting the comment :'3 Thanks for the prompt reply anyway. I guess sometimes we rookies just lost, tearing out hair over trivial mistakes which then builds frustration and tosses the self confidence into a black hole temporarily!

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

C was much harder than D for me.

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

    Depends. If someone has good DP knowledge, C was way more easier than D and less time consuming. I took like one hour and half in D which I was too late to solve in contest so I solved it and AC after contest.

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

Nice editorial! It would be great if we can have hint on all the future editorials! (but that would be time consuming for the writer)

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

    I am glad that the hints were so appreciated. I have just followed a suggestion by Errichto.

    In any case, writing hints requires way less effort and time than writing the editorial. So, I would advise any problemsetter who has some spare time before the contest (or also during the contest!) to write hints.

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

Great Set of questions. Even the editorial in this format is very informative and help in logic building.

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

This is the toughest round for me so far.

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

    Same, couldn't solve C or D ..

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

      Found solutions to D and E but couldn't code it, and failed B due to a very stupid bug.

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

        Solved C at Last moment just one step missed. Chain will continue.

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

There is an elementary solution to E which does not use Bezout's Theorem.

First idea of the solution
First step of the solution
Completing the solution
»
11 days ago, # |
  Vote: I like it -52 Vote: I do not like it

For B, I used the idea of finding the contiguous substring with maximum consecutive Ws by performing at most k flips(where a flip is from W to L, L to W). Then I would calculate the winning score. I am getting the wrong answer on pretest2. Can somebody help me find out what's wrong with my solution?

Here is my code — void solve() { cin >> n >> k;

string s;
cin >> s;

vi A(n);
fo(i,n){
    if(s[i]=='W')
        A[i] = 1;
    else if(s[i]=='L')
        A[i] = 0;
}

// Now I find the contiguous substring with maximum consecutive 1s by doing at most k flips.
int l=0, r=0, maxLen=INT_MIN, maxL, maxR, c=k;
for(r=0,l=0; r<n; r++){
    if(c<0){
        while(l<=r){
            if(c>=0)
                break;
            if(A[l]==0)
                c++;
            l++;
        }
    }
    else{
        if(A[r]==0){
            c--;
            if(c<0){
                r--;
                continue;
            }
        }
        if((r-l+1)>maxLen){
            maxLen=r-l+1;
            maxL=l;
            maxR=r;
        }
    }
}

int ans = 0, j = maxL;
if(maxLen!=INT_MIN){
    while(j<=maxR){
        A[j] = 1;
        j++;
    }
    fo(i,n){
        if(i==0){
            if(A[i]==1)
                ans++;
        }
        else if(i>0 && A[i]==1){
            if(A[i-1]==1)
                ans+=2;
            else
                ans++;
        }
    }
}  

cout << ans << endl;

}

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

    Note that the solution might not be to create a single substring: consider the input

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

hence I will leave them a couple more hours to try getting AC

https://codeforces.com/contest/1427/submission/95152627

It turns out my problem was that I was simply losing too much precision when considering escaping through a very close point :(

Knowing that my answer is actually bigger than the correct one was enough to find the issue immediately.

Thanks for the contest!

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

    Congratulations!

    By the way, I had exactly the same bug when preparing the problem. I lost a full day on that!

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

    Can you very briefly describe the solution? I'm dying to know how far away I was.

    I assumed that it's enough to consider the prisoner to start from some point on the boundary and guards can then choose where they start. Iterate over segment of prisoner, ternary search his exact position there, one guard must stand at same position, iterate over segment of the other guard, ternary search his exact position, then check with Apollonius circles who wins (well, actually find the ratio for tie).

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

      I have posted the editorial.

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

      It's very similar to the editorial, but in a few words:

      indeed, let's assume that the prisoner starts at the boundary. Then one of the guards must be in the same point or they'll escape immediately, so the other guard can guard only one of two segments that this point splits the boundary into. So if we compute the speed needed to catch the prisoner that runs to some point at the bottom part (via iterating over the segment we run to and using ternary search), the speed needed to catch the prisoner that runs to some point at the top part, and take the minimum of those two values, it will be a lower bound on the answer. Now we treat it as a blackbox function f(x) and try to find its maximum (I'm not sure ternary search within each segment is enough, so I had something slightly more general). I don't have a proof that the maximum of those lower bounds is the answer, I guess the editorial does :)

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

In the question C... I tried a code with dp approach but with some restriction (difference of index). It passed all the test cases.

But for this test case my code outputs 0 but the answer should be 1.

500 2

100 50 60

2100 500 500

Are the test cases of C weak or Am I wrong somewhere?

Submission link:- https://codeforces.com/contest/1427/submission/95152766

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

In problem C, I thought that R in the input is useless then tried solving the inequality tj — ti >= |xj — xi| + |yj — yi|, (tj > ti) to solve the problem in n*log(n) time but didn't come up with the solution, is there any such faster solution possible?

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

My solution for problem G seems to be a weird modification of the standard solution.

I do binary search on the candidate values, run min-cut, then divide the vertices into two halves. Thus there will be $$$O(\log n)$$$ layers, each consisting a total of $$$O(n^2)$$$ vertices and edges. The complexity will be $$$O(n^3\log n)$$$. (Since Dinic's algorithm works in $$$O(E\min\{E^{1/2},V^{2/3}\})$$$ on networks with unit capacities)

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

Difficulty of 'B' should not be less than 1500

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

95149492 wrong at pretest test 2 in B

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

hello cf community, I am very confused about where my code of question B of this contest is failing.It is showing WA on 202th TC. I request you to help me by telling where am I going wrong. My submission link is : https://codeforces.com/contest/1427/submission/95153570 Thanks in advance :) !

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

I'm unable to access the solutions in the editorial. Could you please check and possibly fix the issue?

By the way, Great Contest!

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

Another deterministic solution of E:

Step 1: Let $$$p \in N$$$ be the unique number such that $$$2^{p-1} < x < 2^{p}$$$. Write $$$2^p x$$$ and $$$(2^p - 1) x$$$ on board with $$$O(p)$$$ operations.

Step 2: Write $$$(2^p x) \oplus ((2^p - 1) x) = 2^{p+1} - x$$$ on the board. Then, write $$$x+ (2^{p+1} - x) = 2^{p+1}$$$ on the board.

Step 3: We can write $$$2^i$$$ for all $$$i \ge p+1$$$ on the board. Write $$$2^p$$$ by using xor operations for all the bits of $$$2^p x$$$ except $$$2^p$$$.

Step 4: Write $$$(2^{p+1} - x) \oplus (2^p) = (2^p - x)$$$ and repeat the steps with new $$$x = (2^p - x)$$$ while $$$x \ge 1$$$. New $$$p$$$ of new $$$x$$$ is strictly smaller than current $$$p$$$, so it repeats at most 20 times.

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

Can dynamic programming in Problem C be done with recursion and memoization? If yes, how? Please help.

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

    Yes, taking help from the "alternative optimization" in the editorial, you can solve it using recursive DP, just make sure you don't consider more than $$$4*r$$$ of the next celebrities.

    That being said, the iterative approach is cleaner and easier, so try to practice that instead.

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

Problem D is actually very easy if you realize the operation is same as reversing each deck individually and reversing the entire array. Since you can fix the reversing of the entire array with one operation, the problem is reduced to "sort an array with at most N subarray reverses", which is easy

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

    Good one!

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

    I would be thankful if you can give a quick example.

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

      Let's say array is $$$[1, 3, 4, 2]$$$ and you choose decks $$$D_1 = [1, 3]$$$ and $$$D_2 = [4, 2]$$$. Then, after the operation it becomes $$$[4, 2, 1, 3]$$$. This is the same as these two operations applied, one after another:

      1. Reverse the decks: $$$[1, 3, 4, 2]$$$ -> $$$[3, 1, 2, 4]$$$ (here each deck was reversed individually inside the array).
      2. Reverse the array: $$$[3, 1, 2, 4]$$$ -> $$$[4, 2, 1, 3]$$$

      Ignoring the second operation, according to the link I posted to the solution of the reduced problem, you would choose decks with sizes:

      • $$$[1, 3]$$$ (puts 2 in its place) and array becomes $$$[1, 2, 4, 3]$$$
      • $$$[1, 1, 2]$$$ (puts 3 in its place) and array becomes $$$[1, 2, 3, 4]$$$

      Now, to consider the second operation, you just need to keep a flag if the array is reversed or not. If it is, you reverse the decks you print. If by the end this flag is true, you print one last time: $$$[1, 1, 1, 1]$$$ (this will only reverse the array).

      Hope it is clear now!

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

Can someone explain to me if there exists a way to solve problem B through DP? (case of changing 'L' to 'W' and maintaining max score at each step). I tried to solve B in the contest by using DP and even after 2 hours couldn't come up with a proper solution.

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

    I actually did DP for problem B at first. (Though obviously it gives TLE.) Here is the link if you are interested: https://codeforces.com/contest/1427/submission/95116795

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

      Same idea but obviously no good here with the given constraints.

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

        smh countless times when I did a DP for one of the first questions that can be solved with greedy ;c

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

          I never expected B problems would TL with dp. I coded it without calculating the complexity only to realize it will give TL before submission.

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

In the editorial for problem A, it's conjectured that a random shuffle works with probability at least $$$\tfrac1n$$$ (assuming the sum of all the numbers is nonzero). This is true, and here is a proof. The key claim is that, given any shuffle, some cyclic permutation of it works. This easily implies the desired result.

Suppose that the claim is false for some shuffle $$$a_1,\ \dots,\ a_n$$$ (so $$$a_1 + \dots + a_n \ne 0$$$). Interpret all indices modulo $$$n$$$. Since no cyclic permutation of this is valid, for any $$$k$$$, there exists some $$$f(k)$$$ such that $$$a_k + a_{k+1} + \dots + a_{f(k)-1} = 0$$$.

Thus, we have a function $$$f$$$ on the integers modulo $$$n$$$. (Formally, we have $$$f\colon \mathbb Z/n\mathbb Z \to \mathbb Z/n\mathbb Z$$$.) Thus, this function has a cycle, say $$$t_1 \to t_2 \to \dots \to t_k \to t_1$$$.

This gives us the $$$k$$$ relations $$$a_{t_1} + \dots + a_{t_2-1} = 0$$$, $$$a_{t_2} + \dots + a_{t_3-1} = 0$$$, $$$\dots$$$, $$$a_{t_k} + \dots + a_{t_1-1} = 0$$$. Summing these all up, we get $$$c(a_1 + \dots + a_n) = 0$$$, where $$$c$$$ is the number of "revolutions." Thus $$$a_1 + \dots + a_n = 0$$$, as wanted.

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

    Very cool! If you don't mind, I will add a link to your comment in the editorial.

    UPD: Added.

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

      That’s okay with me. Thanks for the great contest!

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

    Thus, we have a function f on the integers modulo n. (Formally, we have f:Z/nZ→Z/nZ.) Thus, this function has a cycle, say t1→t2→⋯→tk→t1

    I didn't get this. Will you please elaborate on it?

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

      Recall that for each $$$k$$$, we have an $$$f(k)$$$ for which $$$a_k + a_{k+1} + \dots + a_{f(k)-1} = 0$$$.

      Now draw an arrow from $$$a_k$$$ to $$$a_{f(k)}$$$ for each $$$k$$$. Since we have one arrow leading out of each term, there must exist a cycle of arrows. (To see this, imagine following the arrows: travel from $$$a_k$$$ to $$$a_{f(k)}$$$ to $$$a_{f(f(k))}$$$, etc. Then eventually we must revisit some term, which gives a cycle.)

      Suppose the cycle takes $$$a_{t_1}$$$ to $$$a_{t_2}$$$ to $$$a_{t_3}$$$ to ... to $$$a_{t_k}$$$ to $$$a_{t_1}$$$. Now we can follow the last paragraph of the proof.

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

    That's pretty good! I think the below also works as proof (correct me if I'm wrong).

    In the case where n-1 numbers are 0 and one is non-zero, the only possible permutation that gives you an acceptable answer is when non-zero number comes first. Probability of that happening is 1/n. Probability will keep decreasing as you replace non-zero numbers with 0, so the lowest positive probability is 1/n.

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

I have a straight forward solution for E with no randomization or coprime numbers required.

Let k be the MSB of x. Notice that we can get 2^n * x for all n by adding x to itself and then repeating. Now, for any number on the board y, we can set all bits >= k equal to 1. We can do this by xor-ing 2^n*x to set each bit above k if it is not set for some appropriate n. So we just need to find two numbers for which, after setting all bits >= k to 1, all of the bits below k are the same, except the 1 bit. We can just check the first 3e6 multiples of x (no randomization required).

Submission: https://codeforces.com/contest/1427/submission/95156859

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

I solved problem C the way you suggested and thought that 2rn = 10^8 will not fit so I didn't implement it...
Did this happen to anyone else?

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

    Sadly same thing happened with me, I was trying to think of applying segment tree on n but it got too messy. Hopefully I would have tried D first which was relative easier to me.

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

    I implemented as said in the tutorial. Hope it helps :) Solution

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

    Same. Was able to think O(nr) and was like 10^8? No that won't work.

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

95127605 I used random_shuffle for problem A because the constraints were small whereas everybody else used sorting. Is it my luck that my submission got accepted? Also, what are the chances that my solution won't work?

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

    nice idea :). thumbs up!

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

    The approach I used to solve problem A was the following:

    Given input [-3, 4, 0, -1, 5] create three arrays: 1) positives [4, 5] (sum is 9) 2) negatives [-3, -1] (sum is -4) 3) zeroes [0]

    To begin constructing the answer we choose the array of positives or negatives according to which has the larger magnitude. In this case it's the positives. If our sum of positive numbers is 9 and the magnitude of the sum of our negative numbers is -4 we know that adding in numbers from the array of negative numbers will never result in the value of zero being reached.

    Solution is positives + negatives + zeroes = [4, 5, -3, -1, 0]. O(n) time.

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

For E, I had similar solution to the gcd one, but the step of finding a co-prime pair is randomized. It randomly generates new numbers until it finds a co-prime pair. It too completes in $$$\le 100$$$ operations. 95149535

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

one of the best editorial. Loved it!!

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

if it is possible, try to keep hints option in every editorial .. it is so beneficially for a newbie like me :)

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

I like the solution to E with bezout theorem very much! Thanks for fast editorial.

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

Could you check pls what is wrong with my solution for C (WA15)

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

    v[t] = {p,q}

    Can't 2 celebrities exist at the same time in different locations?

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

Why is the approach at problem A correct???

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

I stupidly misread the constraints for D, and even more stupidly called my results vector in the solution "omgconstraints", as a way to punish myself for not reading constraints, by typing that name like 50 times. Given that my successful submission for D was 10 seconds before the contest ended, I cursed myself every time i typed "omgconstraints" rather than the usual "res" that I use. Had I known that these extra letters might have pushed cost me the problem, I would have definitely thought twice.

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

Hey, I have some problems with B.

Just Have a look at this test case and tell me how's the answer for this test case is 16.

1

12 2

WWLWLLWLWWWL

Ans:- 16 I think the answer should be 15

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

In problem C.Who can explain completely Hint 3 ?

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

Can anyone tell me the error in my code : Chess Cheater problem. Here is my submission link: https://codeforces.com/contest/1427/submission/95129328

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

My first CP contest! got stuck on implementing B..

See you in the next round, :)

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

Hello there, I am just a beginner , i try to solve two to three questions per day but other than some type of questions i am just blank, where should i go to learn further ds algo concepts. is there any course or anything that i should do to build my logic.

Thank you in advance:) Happy coding:)

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

I am getting WA on 2740th number in 2nd test case (Problem B). Can anyone point out the mistake in my code.

Code Link — https://codeforces.com/contest/1427/submission/95170560

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

Based on this contest, I believe that dario2994 is one of the best problemsetters on CF. Would love to see another contest from you!

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

Can someone explain step1 of the deterministic solution of Problem E . Particularly this line :- y=(2ex)^x=(2e+1)x−2e+1 and therefore gcd(x,y)=gcd(x,2e+1)=1

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

Who is an "experienced participant" in your view dario2994?

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

    Anyone who participated in at least 10 contests and is able to enjoy a contest even if he gets a negative rating change.

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

Hi, Can anyone help to understand why my solution of problem D works. Here is the link to solution : SOLUTION

Approach: I am counting the number of operations from 0.

When the parity of number of operation is even : In this case I select subarrays staring from first element till the elements are in decreasing order. When I find an element that is bigger than previous element, I stop and considers the chosen elements as a split. Now I start fresh from this element and repeat this process until I have some k splits. Now I perform the operation on them.

When the parity of operation is odd, I am doing the same process except I chose subarrays that are strictly increasing.

For example : Input:

5

4 2 1 5 3

Output:

2

3 3 1 1

4 1 2 1 1

Given 4 2 1 5 3:

Operation 0 : Parity = 0

We split as (4 2 1) (5 3)

New array : 5 3 4 2 1

Operation 1: Parity = 1

We split as (5) (3 4) (2) (1)

New array : 1 2 3 4 5

We get the sorted array.

I am not able to prove why this works. I saw this pattern during contest but forgot about the case that k should not be equal to 1. Is this same as the approach given in the editorial intuitively ?

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

It was awesome round actually motivated much to practice.Thanks :)

»
11 days ago, # |
  Vote: I like it -37 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
string change(string str,ll k,ll cntL)
{
    if(cntL==0||k==0)//if count of L or k is 0 then returning the original string
    return str;
    if(cntL<=k)//if count of L is less than k then changing all the L to W at one go
    {
        for(ll i=0;i<str.length();i++)
        if(str[i]=='L')
        str[i]='W';
        return str;
    }
    //cout<<k<<" "<<cntL<<"\n";
    for(ll i=0;i<str.length()-2;i++)//filling all the L in substring WLW
    {
        if(str[i]=='W'&&str[i+1]=='L'&&str[i+2]=='W'&&k>0)
        {
            str[i+1]='W';k--;cntL--;
        }
    }
    //cout<<k<<" "<<cntL<<"\n";
    if(k==0||cntL==0)
    return str;
    for(ll i=0;i<str.length()-1;i++)//filling all the L in substring WL if k is left and L is left
    {
        if(str[i]=='W'&&str[i+1]=='L'&&k>0)
        {str[i+1]='W';k--;cntL--;}
    }
    //cout<<k<<" "<<cntL<<"\n";
    if(k==0||cntL==0)
    return str;
    for(ll i=0;i<str.length()-1;i++)//filling all the L in substring LW if k is left and L is left
    {
        if(str[i]=='L'&&str[i+1]=='W'&&k>0)
        {str[i]='W';k--;cntL--;}
    }
    if(k==0||cntL==0)
    return str;
    for(ll i=0;i<str.length();i++)
    if(str[i]=='L'&&k>0)//filling all the left L if k is left
    {
        str[i]='W';cntL--;k--;
    }
    //cout<<k<<" "<<cntL<<"\n";
    if(k==0||cntL==0)
    return str;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t,n,k,i,cntL,score,c;
    string str,nstr;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;cntL=0;score=0;c=0;
        cin>>str;
        for(i=0;i<str.length();i++)
        if(str[i]=='L')
        cntL++;//counting the number of L in str
        nstr=change(str,k,cntL);
       // cout<<nstr<<"\n";
        ll cntW=0,cntS=0;
        for(i=0;i<nstr.length();i++)
        {
            if(nstr[i]=='W')
            cntW++;
        }
        for(i=0;i<nstr.length();i++)//counting the number of W streaks
        {
            if(nstr[i]=='W')
            c++;
            else
            {
            if(c!=0){
            cntS++;c=0;}}
        }
        if(nstr[nstr.length()-1]=='W')
        cntS++;
        score=2*cntW-cntS;//computing the score
        cout<<score<<"\n";

        
    }
}

This is my solution.It is wrong. is my approach correct at all?or i have to try another approach?

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

This is what I did in problem D.

Idea: for 1<=i<n we get i and (i+1) adjacent keeping everything else(less than i) adjacent. (Similar to the editorials idea). Hence in at most n-1 moves we can get the array sorted and 1 extra move if the array turns out to be descending.

So let us say we have first i numbers sorted(descending or ascending). We have 4 possibilities. D4587a81dcfc82f2a.jpg

The indicated boxes are how we can achieve our idea.

After this the code is fairly simple.

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

can someone explain how to do problem B

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

As asked by the dario2994, I have some feedback to offer. Some of the below points are for the a part of community who miss no chance to rant the organisers. So here we go.(expecting a lot of hate from those who can't agree diverse thought process)

What I loved about the contest:

  1. The contest in general was awesome. It was one those contests that kept me thinking about the problems for the entire time rather than reaching a point where one realises that later problems ain't their cup of tea. (Kudos for this because such contests are rare to find).

  2. The contest had a vast range of problem. Many people are of the view that contest was filled with ad-hoc ones, but I beg to differ. I think we can call these problems as non-trivial/non-standard rather than ad-hoc. (I know lot of people would disagree to this)

  3. The contest is an excellent example where the problem statement are not exactly short yet very interesting to read. I can't stress enough that length of problem statement doesn't matter as long as the description is to the point and doesn't make things messy to understand. As for me, I didn't loose interest in reading any statement and I read all of them (yes all until H) even though I knew I wouldn't be able to solve them realistically.(I expect most hate for favouring the length of problem statements).

  4. The contest had excellent sample cases. I can bet that without such samples a lot people would have had series of WA on pretest for question B.

  5. The contest had really high quality problem (even though I couldn't solve many problems doesn't take away the fact). I would genuinely like to appreciate the quality of the problems and beautiful ideas behind the solutions.

What I think could have made contest more interesting:

  1. I believe that scoring distribution could have been better than what it was. Of course this point applies iff one is able to solve problems else it is irrelevant. But I strongly believe that scoring can be made better by comparing the problems within a contest (and not with other CF rounds) relative to each other. I liked the math the errichto proposed to the author in one of his comment but I also understand that it is very hard to gauge the exact difficulty of problems just from handful of testers and that the actual round can have variations to this. I think that this round could have had been relatively high scoring (by increasing the point of C and onwards problems) or could have been low scoring (by decreasing the points of A and B). All I am trying to convey is that scoring could have been better distributed.

But overall, I'd place this contest in top 10-15 of all I have appeared in (appx 200 or more across various platforms). I'd sincerely appreciate the hard work of author and coordinators for making such a nice contest.

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

    Thank you for the feedback (and don't worry about downvotes).

    Regarding 4., I have to thank testers for this. Initially samples for B were much weaker and many testers complained.

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

95139472

Can someone help me with this, why this logic is wrong ?

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

So we are basically optimising $$$ O(n^2) $$$ dp solution for Problem C. My question is how do we optimize it if there is no $$$ \triangle{t} \ge 2\cdot{r} $$$. Won't it run on $$$ O(n^2) $$$ and give a TLE. Or am I missing something out? Thanks and Great Round.

Edit :

Got it. $$$t(i)<t(i+1)$$$ that limits maximum iterations to $$$2r$$$ and complexity to $$$O(2nr)$$$.

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

In the 1st question's editorial what will happen if a array is already sorted

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

I did come up with the $$$O(nr)$$$ solution for 1427C - The Hard Work of Paparazzi, but I thought it would not fit into the time limit :(

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

what are the optimal ways of thinking to find out the solution of codeforces A, B problems ?

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

I use another optimization in problem C and also get accepted: 95139974 My brief idea is using ans[i] to store the maximum photos can be taken when we already at i'th celebrity. We iterate from ans[n] to ans[1]. For each ans[i], instead of iterating all celebrities in [i+1, n], we use a map to record the ans[j] (j in [i+1, n]) in descending order, so we can just take the first celebrity that satisfies $$$|x_i-x_j| + |y_i-y_j| \le t_j-t_i$$$.

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

For problem C, is it possible that two consecutive celebrities appear at the same intersection?

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

    That has to be true for any test case where n > r * r according to the pigeon hole principle.

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

My solution for E:

  • try various inputs, bruteforce and print some shit to get an intuitive understanding
  • notice that the worst case is when $$$X$$$ is a simple binary palindrome 1000...1 and we need to create numbers approx. up to $$$X^2$$$ then
  • we want to generate a smaller (than $$$X$$$) number $$$Y$$$; if it's even, we can remove the largest 1-bit from $$$X$$$ using it, and if it's odd, we can solve recursively for $$$Y$$$ (there's the operation limit, but this recursion turns out pretty fast)
  • this seems to work for the palindromic case: try XORs of $$$X$$$, $$$2X$$$, $$$4X$$$ etc. up to $$$2^k X$$$, for each $$$2^k$$$, pick one of these (denoted by $$$A$$$), then $$$B = A \oplus X$$$, then create $$$(A+B) \oplus (2A)$$$ or $$$(A+B) \oplus (2B)$$$, and it turns out to be smaller than $$$X$$$ for a good choice of $$$k \le 20$$$
  • bruteforce check if it gives $$$Y \ll X$$$ for each $$$X$$$
  • it works and any odd $$$Y$$$ is around 2 times smaller than $$$X$$$! implement

I don't want randomised solutions because they carry a risk, but my thinking here is way more random. I have no idea why this works.

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

I like problem D. And I believe I'm producing nicest solutions out of all solutions I've looked at. :) 95384262

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

What will happen if there are simultaneous occurence in problem in C, as explained in editorial?

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

Every editorial should be like this one, having proper hints before full explanations and solutions. :)

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

someone please check my code i am going somewhere wrong that by getting WA in test case 1 itself since my logic is correct. Problem B chess cheater global round 11

include <bits/stdc++.h>

using namespace std;

define ll long long

define pb push_back

int main() { // your code goes here ll t; cin>>t; while(t--){ int n,k; cin>>n>>k; string s; cin>>s; vector vec; int ans = 0; int countW = 0,countL = 0; if(s[0] == 'L'){ countL++; ans = 0; } else if(s[0]== 'W'){ countW++; ans =1; }

    for(int i=1;i<n;i++){
       if(s[i] == 'W'){
         countW++;
         if(s[i-1]== 'W'){
          ans+=2;
         }
         else{
          ans+=1;
         }
       }
       else {
         countL++;
       }
    }
    int c =0;
    for(int i=0;i<n;i++){
       if(s[i]=='W'){
         if(c>0){
         vec.pb(c);
         }
         c =0;
       }
       if(s[i]=='L'){
         c++;
       }

    }
    // if(c>0){
    // vec.pb(c);
    // }
    sort(vec.begin(),vec.end());
    // int sz = vec.size();
    // for(int i=0;i<sz;i++){
    //     cout<< vec[i] << " ";
    // }
    // cout<< endl;

    if(countW==0){
       ans += max(0,2*k - 1);
       // return 0;
    }
    else{
       if(k>countL){
         swap(k,countL);
       }
         ans+=2*(k);
         for(auto it:vec){
          if(it<= k){
                 ans++;
                 k-=it;
              }
          }
         }
         // if(s[0]=='L'){
         //   if(ans){
         //   cout<<ans - 1 << endl;
         //   }
         // }
         // else{
          cout<<ans<<endl;
         // }
}
return 0;

}

//expected output 7 11 6 26 46 0 1 6

//my output 7 12 6 26 46 0 1 6

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

Anyone able to provide proof as to why we only need to consider 4r consecutive celebrities ? I'm not able to figure it out as I think, as said in the editorial, any element past the 2r point will be a compatible point. What different happens at 4r ?

Thanks in advanced!

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

    If the last celebrity you're choosing before celebrity $$$k$$$ is celebrity $$$i<k-4r$$$ then you can get a more optimal solution by also choosing celebrity $$$k-2r$$$ because you can always get both from celebrity $$$i$$$ to celebrity $$$k-2r$$$ and from celebrity $$$k-2r$$$ to celebrity $$$k$$$, so choosing $$$i<k-4r$$$ is never optimal.

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

Can anyone tell me any other alternative solution of problem B. It's not that I didn't understand the editorial but it's just I don't think the solution is intuitive to me. So if possible please help me.