prvocislo's blog

By prvocislo, 5 weeks ago, In English

We hope you enjoyed the problems! Thank you for your participation! We are really sorry that A and D turned out to be harder than usual.

Problem A: idea by prvocislo and satyam343, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Solution:

Problem B: idea by prvocislo, prepared by prvocislo

Definition:
Hint 1:
Hint 2:
Hint 3:
Solution:

Problem C: idea by prvocislo, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Solution:

Problem D: idea by prvocislo and TimDee, prepared by prvocislo and TimDee

Hint 1:
Hint 2:
Hint 3:
Hint 4:
Hint 5:
Solution:

Problem E: idea by prvocislo, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Hint 4:
Hint 5:
Solution:

Problem F: idea by prvocislo, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Solution:
  • Vote: I like it
  • +214
  • Vote: I do not like it

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

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

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

first. please don't downdoot me

also I think B was a very nice problem

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

    you have a great growth within 10 months on your profile how do you manage to do so?

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

      I appreciate it broski but I have also done a lot of leetcode so, between the two platforms, it is normal growth. I think that leetcode is better than codeforces when you are beginning 100%.

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

        will surely try leetcode because i have barely any growth on cf. any tips?

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

          don't waste time or energy learning advanced stuff, just focus on simple 9th grade math, logic and thinking. after u got better at that(rating around 1000), learn prefix sums, sets, lower/upper bound

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

            yup i kind of couldn't even get 1st problem here in this contest

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

          In my opinion, leetcode is the best way to start competitive programming because it introduces the most common competitive programming concepts (greedy, binary search, dp, graphs/trees, etc etc) through more or less straightforward problems. The good thing about this is that you aren't gonna have to do some weird math things while solving leetcode dp problems, for example. You can just focus on learning dp. Another benefit of leetcode is that it has a much bigger community than cf. If you get stuck on a problem, you will have much more than just a single editorial to read. There are videos, writeups, and there is even a solutions tab that you can use to understand the problem.

          If I were you, I'd go to https://neetcode.io/roadmap and just start working through that list. NeetCode, the guy who made that website, has great explanations for each problem. Once you finish that list, start doing random mediums, and when you feel comfortable with those, start trying some hards. When I was grinding out mediums, I'd try to limit myself to 45 minutes and then I'd look at the solution.

          Make sure you're doing the weekly and biweekly contests while you're practicing. Once you reach a 2000+ rating, I'd say that you should start practicing on some more serious competitive programming websites. 2000 rating should get you to specialist on codeforces at least.

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

            will surely try so

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

            Thanks a lot man, very helpful :)

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

            Yes I agree, I did Leetcode for a few months and now codeforces seems much more approachable to me. I still have a lot to learn, but at least I can now understand what topics, and how to learn them

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

          Growth starts from the point you feel like quitting. Do leetcode but don't leave cf. Leetcode contests are very good, try that also.

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

            true that my growth has just been downwards wanted to quit but did that once and ended up in not so good institution so won't do that again

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

    I am not able to solve problem A. Can you help me with the logic. I couldnot understand the editorial. only got -1 part. and how do you come up with such logic.

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

      So you understand that if the sum is odd, the answer must be -1. Let's show that if the sum is even, the answer is never -1. In order for p1 + p2 + p3 to be even, all 3 must be even or 2 / 3 of them must be odd. We can achieve all possible (p1, p2, p3) when p1, p2, p3 are even through just wins (aka by adding 2 to each one independently). Now for the case where 2 / 3 of them are odd, we can just throw in a draw between the two which we want to be odd (add 1 to each), and we can then keep adding 2 to each one of them and we can see that, by doing this, we can achieve all (p1, p2, p3) where 2/3 of them are odd. So whenever p1 + p2 + p3 is even, the answer is never -1.

      Now that we know that, how can we find the max number of draws? Well let's try to take draws from the two greatest elements in (p1, p2, p3). You can think of this intuitively like this: if you take a draw (that is subtract 1) from the two greatest elements in (p1, p2, p3), you bring the elements in (p1, p2, p3) closer together. If the elements are closer together, there is more "drawing potential" since if the elements are all equal to each other, we can guarantee that all the games can be draws (we can draw p1, p2 then draw p2, p3 then p1, p3 and then our elements become (p1 — 2, p2 — 2, p3 — 2) and we can do this down to 0). Hopefully the intuition here makes sense.

      So the algorithm is just sort (p1, p2, p3) and while the second greatest element is > 0, take a draw between the first and the second greatest elements and resort the list.

      Don't focus too much on the proof of div. 2 A in contests though. This comment doesn't even prove the greedy algorithm but rather shows what the intuition to get there might be. Do your best to solve A by educated guesses.

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

        Is the math written in the solution correct:

        I'll just put the scores in here:

        • 0 0 0
        • 1 0 1
        • 2 1 1
        • 3 1 2
        • 3 2 3
        • 3 3 4

        This is what the math in the bonus states the answer should be. I get that there can be another draw between p2 and p3. Just wanting to know whether I'm doing the math wrong or the math written in the bonus question is incorrect.

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

          looks right to me

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

            But I did the above calculation for the case where the final scores are 3 4 5. Yet the final result on following the calculations is coming out to be 3 3 4. Seems like there's a typo in the bonus hint then.

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

              Where are you confused? You wrote out 5 draws to get to 3 3 4 and you can add another draw to get to 6 draws at 3 4 5. The answer is min( (3 + 4 + 5) / 2, 3 + 4), which is 6

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

      Deleted

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

      If you want the explanation for the $$$O(1)$$$ solution, it goes like this:

      As, we are always increasing $$$p_1+p_2+p_3$$$ by $$$2$$$ ($$$1,1$$$ in case of draw and $$$2,0$$$ in case of win), the invariant is pretty clear, i.e.., $$$(p_1+p_2+p_3)\%2 = 0$$$ for a valid game.

      Now, we have $$$p_1 \le p_2 \le p_3$$$, so we can always have atleast $$$p_1$$$ draws. Thus, from $$$p_2$$$ and $$$p_3$$$, we have to remove $$$p_1$$$ points, leaving us with $$$p_2+p_3-p_1$$$ points. Obviously, in the most optimal case, we could have $$$(p_2+p_3-p_1)/2$$$ more draws (if we had equal points left for both), but this is not necessarily the case as it is possible that $$$p_2 < (p_2+p_3-p_1)/2$$$, in such a case, we can add $$$p_2$$$ to the score. So my final $$$O(1)$$$ solution looks like:

      1) If $$$(p_1+p_2+p_3)\%2 \ne 0 \implies$$$ No solution possible.

      2) Otherwise, the answer can be found out using the expression $$$p_1 + min(p_2,(p_2+p_3-p_1)/2)$$$.

      Hope this helps!

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

    could you explain this claim in detail ? if the array is k-lonely, the array is also k+1-lonely .

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

      Sure. If we look at this problem bit by bit, there are two cases:

      1. The ith bit is not set anywhere in the array. If this is the case, we can think of the array as [0, 0, 0, 0 ...] where array[j] represents whether or not the jth element in the original array has the ith bit set. The or of all subarrays in this array is 0 so every k works.

      2. The ith bit is set in some places in the array. We can think of our set bit array as [0, 1, 1, 0, 0, 1, 0, 1] or something. In order for some k to work, it must be the case that every subarray of length k contains at least 1 set bit. This is true because there is at least 1 subarray of length j (1 <= j <= n) that has at least 1 set bit, so therefore all subarrays of length k must contain at least 1 set bit for this k to work. If every subarray of length k contains at least 1 set bit, then surely every subarray of length k + 1 contains at least 1 set bit. So if k works, k + 1 works too.

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

idk why in B i' didn't think of binary search

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

can someone please the logic of this solution for B: 261346413, I'm not getting it

EDIT: got it

explanation for anyone who didn't
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Look at the problem bit by bit: in order for all of the subarrays of length k to have the same or, for each bit, there has to be at least 1 of them in each subarray or there has to be 0 of them in all subarrays (aka 0 of them in total).

    For example, if we have the array [1,0,0,1,0,1], and we try to have k = 2, well there is a subarray of length 2 that doesn't have an on bit and the rest of the subarrays have at least 1 on bit. So k = 2 can't work. Looking at a few more examples, you will see that k has to be the maximum distance between consecutive 1s so that once a subarray loses a 1, it will surely gain another 1.

    The answer will be the max of these maximum distances for each bit that is present in the array. If a bit is not present in an array, we can disregard it.

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

      thx for the explanations, I just understood how it works and it took a while to write the edit, sorry for the waste of time, maybe someone doesn't understand my explanation and yours is more understandable, sorry for the inconvenience

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

        haha no problem broski, the more explanations the better

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

      SO, for example 2 0 4 0 2, why is the answer not 3, but 4??

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

        for 2 bit, the array is [1, 0, 0, 0, 1]

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

          Ahh, my bad !!!. Was thinking from another angle . Got it, thanks. Will try more next contest :)

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

Interesting, I thought of binary seraching for B but couldn't come up with the NlogA traversing algorithm, so instead I stumbled on the NlogA solution.

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

C is really good

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

Wow rating changes and editorial were kinda fast... speedforces

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

I used segment tree for B. I am sooorry ;).

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

    that's what happens when u learn something too soon, it could be solved using just prefix sums for query, or sparse table at worst, a segment tree...

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

      Haha my solution used sparse table. The core idea is that range or has a similar property to range minimum, that is a range can be split into two overlapping subranges and merge the result.

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

      Can you please look into my code and tell why its giving me MLE i m not sure what is going wrong 261444005

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

        I couldn't understand the logic, nor the reason of mle

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

          It is binary search on all values of K,it led to TLE during contest. So i tried to optimise it using hashing for previous values of K for any index or the maximum subarray of size K' form the same index. So here is the first iteration: from B.S--> K=3 i.Since its first iteration than map will be empty. ii. For all subarray of size K=3,we also can hash the OR for all subarrays from an index i, of size t such that t<=K (i.e 3,2,1) which is why i used the map[(index,K_size)]=OR_value. iii. The prev is just for checking if there are different OR.

          iv.Next time when BS gives K=5,then i found the max(t) such that (t<=K) from the map using findK function.If it finds it then we will use it for all index that it has already computed and for indexes it hasn't we will compute it normally.

          This led to MLE

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

            Finally understood the code, I believe there is a way to set up the inputs such that the map will take n² pairs of numbers leading to tle

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

      Not really too soon, I think learning it is good but overusing it is really problematic

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

    Me too!! Used binary search with segment tree!!

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

B without binary search: 261388922

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

prvocislo orz <3

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

I think for Problem C hint 2 should be n/2-1.

prvocislo

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

C was nice from the proof and math work side

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

in C 2nd hint

n/2 -1 not +1

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

B with segment tree and binary search 261367730

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

Can someone explain the intuition, rather than proof, behind problem C?

"... Then since $$$n$$$ belongs to an odd index, the $$$a_i$$$ for each odd $$$i$$$ will be at least $$$n+1$$$ while the $$$a_i$$$ for each even $$$i$$$ will be at most $$$n$$$."

While I can indeed verify this statement after the contest, I found it rather counter-intuitive that a simple greedy method would work, so I quickly dismissed the thought of trying it out. Any thoughts?

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

    The fact that n is even should signal that maybe you can somehow split numbers into two groups.

    Secondly, it'd fairly common to sort permutations in opposite directions (ascending/descending) and match them greedily.

    Also worth noting, it's very easy to get sums of all elements of final array to be equal to (1+n), by matching $$$p_i$$$ with (1+n-$$$p_i$$$).

    This was my thought process during the contest, it's really just 3 standards ideas combined together. If you write all these out at some point you'll notice that you can ensure (n+2) is reachable in n/2 points so ot suffices to make the others no greater than n+1, which like we said has an easy construction.

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

    I ended up coming up with the editorial solution and another in the contest, so I'll describe them both:

    Editorial Intuition We suppose $$$n$$$ has odd index and then try to make all odd elements into peaks. Is it possible? The worst case might be when $$$1, 2, 3 ... n/2-1, n$$$ are the elements in the odd positions and $$$n/2, n/2+1, ... n-1$$$ are the elements in the even positions. We can even go further and assume $$$n-1$$$ is next to $$$1$$$ and $$$2$$$, and $$$n-2$$$ next to $$$2$$$ and $$$3$$$ and so on.

    Obviously let's assign smaller labels to the ones in the even position and larger labels to the ones in the odd positions. Well $$$n-1$$$ gets the label $$$1$$$, so $$$1$$$ and $$$2$$$ need the labels $$$n$$$ and $$$n-1$$$ respectively, and then continuing in this way we can make the observation that you call counter-intuitive.

    My Intuition We can construct $$$q$$$ so that all the $$$a_i$$$ are equal (make $$$q_i + p_i = n+1$$$).

    Now we want to reorder some elements of $$$q$$$ such that all the odd/even elements become peaks. Since all elements of $$$a_i$$$ are equal at this point, we just need to reorder the elements of $$$q$$$ so that the ones in odd indices increase, and the ones in even indices decrease (or vice versa).

    There's a lot of ways to do this, the first one that came to my mind is just suppose that $$$n$$$ appears at an even index $$$2k$$$ and sort the odd indices in increasing order of value.

    Then do $$$q_{o_1} \rightarrow q_{o_2} \rightarrow q_{o_3} \dots \rightarrow q_{2k} \rightarrow q_{o_1}$$$.

    i.e. the smallest odd index gets value of the next larger odd index, etc. and the largest odd index gets the value of n.

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

      Nice alternative approach :)

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

      So after making the sum equal at all indices, we have to solve the problem: increase values at even indices and decrease values at odd indices. This (for me at least during the contest) was not helping to explain why there will always be a solution that gives n/2 — 1 peaks (though i agree it is easy to get the solution for n/2 — 1 peaks this way). We still need the editorial approach to build the worst case and show that n/2 — 1 peaks will always exist (for best q). Can you elaborate if you could show n/2 — 1 peaks always exist with your intuition?

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

        With my approach, first we get a permutation $$$q$$$ that makes all values of $$$a$$$ equal. Then we increase the value of $$$q_i$$$ at all odd indices, without increasing any value at an even index. (In fact, we decrease the value at one of the even indices.)

        Therefore $$$a_i$$$ increases for odd $$$i$$$, and doesn't change change (or decreases) for even $$$i$$$. Therefore all odd indices will become peaks and we will have $$$n/2 - 1$$$ peaks.

        This is pretty much independent of the editorial approach.

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

in problem C hint 2, it should have been n / 2 — 1 : )

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

B is a very nice problem.

»
5 weeks ago, # |
Rev. 4   Vote: I like it +39 Vote: I do not like it

My idea for C is slightly different and imo cleaner. Its also much easier to prove why my idea actually works.

Here's my code: 261430375

The explanation

Incase I explained something poorly, please let me know! And I'll try to help if I can. :D

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

    great explanation sir : )

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

    Excellent solution! I didn't get the part "We iterate over the elements at even indices in increasing order of their value." -> could you explain this part?

    Overall, how did you come up with this thinking, if you could share your thought process!

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

      Yeah, so lets take an example, lets say the array is this -

      Spoiler

      Here $$$p[2] = 1$$$, so we try to make values at odd indices local maximums.

      The values at odd indices are $$${5, 6, 4}$$$.

      Since we are going to iterate over increasing values, we go in the order $$$4 \rightarrow 5 \rightarrow 6$$$.

      So we first swap(q[pos[1]], q[pos[4]]) to get -

      Spoiler

      Then we perform swap(q[pos[1]], q[pos[5]]) to get -

      Spoiler

      Then we finally perform swap(q[pos[1]], q[pos[6]]) to get -

      Spoiler

      And we are done!

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

    Damn ! that's a nice observation

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

in problem A, what's the intuition behind if p1 + p2 > p3 , then the answer is (p1+p2+p3)/2 ? , I wasn't able to prove it, all I did was guess it based on the test cases

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

    After giving it a thought, I was able to come up with this explanation, correct me if I'm wrong please.

    Since each 2 points contribute to a game, (p1+p2+p3)/2 is the total number of games, and since we want to maximize the number of draws, we would consider all the games to be a draw.

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

      ah yes and for the case p3>p1+p2 it is not possible to have all the matches draw

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

    You can check out https://codeforces.net/blog/entry/129556?#comment-1149923 for an intuitive explanation :)

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

Thank you prvocislo for all the hard work <3

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

I have another solution for F, which run in 796ms, but I don't know the time complexity for it
https://codeforces.net/contest/1973/submission/261433060
Idea: - Calculate least common multiple (lcm) for each pair a,b
- Calculate lcmv = gcd of all lcms
- Reduce a,b of each pair to gcd(lcmv, a), gcd(lcmv, b)
- Add cost of all elements with the same new a,b (From the observation that for any i,j, if ai == aj and bi==bj then we must either swap i,j or not swap any)
- Sort all triple (a,b,c) by a ascending, b ascending
- For each item, maintain a map of (a,b) => minc; with a,b is the current gcd of sequence a,b; c is minimum possible cost
- After that, we create the array of [(sum gcd value), (min cost)] ascending for both elements, and do binary search for each query

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

Can anyone explain problem A intuition? why are we drawing between two maximums?

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

    Our task is to maximize the number of draws . So the first thought should be to assume if all games played are draw . We know each game played contributes 2 points to the total . So total_games=(p1+p2+p3)/2 Our assumption fails if all games are not possible to be a draw . Only time this fails is if (p1+p2)<p3 . In this case p1 games are played between p1 and p3 and p2 games are played between p2 and p3 which result in draw . Further games which leads to a draw is not possible. So out final answer is min(total_games,p1+p2)

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

can someone please tell why am i getting TLE on test2 in this submission

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

    You only need to query K times for one iteration but in your case it can get >K times, Take K=1 case and all elements are same then in this case you are iterating n * ( n+n/2 + n/3 +n/4....) or n^2 logn which is clearly greater than n query .

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

It seems that there's a typo in problem C, Hint 1.

"the number of the prefix maximums" -> "the number of the local maximums"?

prvocislo

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

What a talented prvocislo, writer of one of the best Div2 round. A great round and great problems.

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

I don't understand the Editorial for problem E. Isn't L + n > R + 1? it's very confusing

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

    think i kinda understood it by algebra, but it doesn't look intuitive. can somebody explain the intutition?

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

      By definition, the value $$$L$$$ is misplaced and wants to participate in some swaps to reach index $$$L$$$. If we set $$$l > L + n$$$, then there are no swaps that value $$$L$$$ can participate in. This is bad, so $$$l \leq L + n$$$. You can argue similarly for the $$$r$$$ constraint.

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

I solved the B problem using two pointers only. During the contest, I was missing an edge case that's why my code didn't get AC. But when I up solved and found the loophole. I managed to get AC using two-pointers.

Here is my submission: https://codeforces.net/contest/1973/submission/261450556

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

    most 2 pointer problem can be solved using binary search, bs on the length of the subarray

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

C is amazing! Brilliant round!

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

Hey! Check out my video solutions for the contest. I've covered Problem A-D here: https://youtu.be/owawrSp2ywU

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

Thanks for the tutorial, it was really helpful.

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

Loved The B Problem.

My Binary Search Solution

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

in case anybody wanted it:
B with binary search: 261420803, without the use of any fancy data structure

B without binary search: 261423079, logic

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

The number of draws between p2 and p3 should be p2-(p1-(p3-p2))/2.

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

D is a very good problem.Interesting.

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

    Can you explain why M will always be a multiple of N(size of the array)?

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

Round is awesome. But error in Russian statement was fixed only after 5 minutes, and I spend that time solving wrong problem with wrong statement

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

can anyone explain me problem A. I could not understand the editorial. I got the -1 part but how do you guys come with such logic in the contest.

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

    You could check my comment in this thread for a detailed explanation of the $$$O(1)$$$ solution, and ask me if you have any questions or if you feel like I've made any mistakes. I could get this solution only an hour after the contest ended though :(

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

In problem B why can we say if an array is k-lonely then it is k+1-lonely too??

Update: nvm I got it

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

fxxk problem B, I use "bin" function many times caused the TLE, fxxk!! After trying for 10+ times, I preprocess the bin of each num, and then accepted! WTF!

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

In Problem B, my solution is giving tle verdict while another solution get accepted using my same idea. Can someone help me finding out mistake in my code.Thanks in advance.

My Submission

Accepted Submission

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

can someone tell me why https://codeforces.net/contest/1973/submission/261471081 tle? I think the complexity of it is o(20*n*logn) is there anything wrong with it?

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

    you should only initialize the part of the array you use. (memset part) and you should learn std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr) and stop using std::endl.

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

I am not able to understand the solution for problem C.

It is saying that We can do this by placing the numbers $$$\frac{n}{2}+1,\frac{n}{2}+2,…n$$$ at the odd indexes in q, giving the bigger numbers to the indexes with smaller pi, and placing the numbers $$$1,2,…,\frac{n}{2}$$$ at the even indexes in p, giving the smaller numbers to the indexes with bigger pi. Then since n belongs to an odd index, then ai for each odd i will be at least n+1 while the ai for each even i will be at most n.

Let us suppose $$$p_3 = 1$$$ and we choose $$$q_3 = \frac{n}{2}+2$$$, then $$$a_3 = \frac{n}{2}+3$$$, which is less than $$$n+1$$$ and similarly, we can show it for even index.

Is there anything that I am missing out here? If someone can help me, I would highly appreciate it.

Thanks

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

why ai|...|ai+k=(ai|…|ai+k−1)|(ai+1|…|ai+k) is correct ? when I expanded these term, it didn't match.

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

    Because of a property of bitwise-or ($$$a_i | a_i = a_i$$$, also note that it is associative):

    $$$a_i | ... | a_{i + k - 1} | a_{i + 1} | ... | a_{i + k} = a_i | a_{i + 1} | a_{i + 1} | ... | a_{i + k - 1} | a_{i + k - 1} | a_{i + k} = a_i | a_{i + k}$$$
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I mistake bitwise-or for XOR.

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

        | is the symbol for the bitwise OR

        ⊕ is the symbol for the bitwise XOR

        & is the symbol for bitwise AND

        it's always the case

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

The Rating Change and Editorial came in like 10 mins... Great Work Authors

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

In problem F the step to calculate "prefix sum" of $$$P$$$ and $$$S$$$ can also be some in $$$D(k) \sum D(d_i)$$$ somehow. Does anybody have some upperbound of this sum? It feels like it's some really small $$$D^3(k)$$$ or something.

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

I have some trouble understanding the given proof for the $$$O(1)$$$ solution for Problem A. I'll explain how I got that solution. Let us take an optimal solution (i.e., a solution with the max possible number of draws that corresponds to the given values of $$$p_1$$$, $$$p_2$$$, and $$$p_3$$$). The total number of games played is $$$\frac{p_1 + p_2 + p_3}{2}$$$. Let $$$a$$$, $$$b$$$, and $$$c$$$ denote the number of draws in the $$$A_1$$$ vs. $$$A_2$$$, $$$A_2$$$ vs. $$$A_3$$$, and $$$A_1$$$ vs. $$$A_3$$$ matches respectively, where the names of the players are $$$A_1$$$, $$$A_2$$$, and $$$A_3$$$. Since this is an optimal solution, the correct answer to the problem is $$$a+b+c$$$. Now, if it so happens that more than one of these players had wins (say, $$$A_1$$$ and $$$A_2$$$ both had nonzero wins — say, $$$k_1$$$ and $$$k_2$$$) — then, we could have repurposed them as $$$\min(k_1,k_2)$$$ more draws in $$$A_1$$$ vs. $$$A_2$$$ games, and one of them having $$$\mid k_2 - k_1 \mid$$$ wins instead, contradicting the optimality of our solution. Therefore, we may assume that only one of these players had wins (if any), say $$$w$$$ of them, in our optimal solution.

Suppose $$$A_3$$$ is the player who had all $$$w$$$ wins ($$$w \geq 0$$$) in our optimal solution. Then, $$$p_1 = a + c$$$, $$$p_2 = a + b$$$, and $$$p_3 = b + c + 2w$$$. Solving for $$$a$$$, $$$b$$$, and $$$c$$$, we get $$$a = \frac{p_1 + p_2 - p_3 + 2w}{2}$$$, $$$b = \frac{p_2 + p_3 - p_1 - 2w}{2}$$$, and $$$c = \frac{p_1 + p_3 - p_2 - 2w}{2}$$$. Verify that these values for $$$a$$$, $$$b$$$, and $$$c$$$ will be the same even if you assume $$$A_1$$$ or $$$A_2$$$ won all $$$w$$$ games! Note that we get integral solutions for $$$a$$$, $$$b$$$, and $$$c$$$, iff the number of odd numbers in $$${p_1, p_2, p_3}$$$ is even. If this is not the case, we output $$$-1$$$, and finish.

Now, thanks to $$$p_1 \leq p_2 \leq p_3$$$, $$$w = 0$$$ (i.e., all games are draws) leads to a valid (i.e., nonnegative integer) solution for $$$b$$$ and $$$c$$$, and a valid solution for $$$a$$$ only if $$$p_1 + p_2 \geq p_3$$$. That is, if $$$p_1 + p_2 \geq p_3$$$, the answer we must output is $$$\frac{p_1 + p_2 + p_3}{2}$$$. The case left to deal with is when $$$p_1 + p_2 < p_3$$$. To make the value of $$$a$$$ nonnegative, the minimal value of $$$w$$$ to be set (we want a minimal value for $$$w$$$ as we want maximum draws) is $$$\frac{p_3 - p_1 - p_2}{2}$$$. With this setting of $$$w$$$, we get a valid solution $$$a = 0$$$, $$$b = p_2$$$, and $$$c = p_1$$$, so that the answer is $$$a + b + c = p_1 + p_2$$$. I wrote this solution (sadly, after the contest) and it was accepted.

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

For Problem, C, can someone prove how the upper bound n/2-1 is always achievable, i.e., there always exists a permutation q such that the array constructed by summing individual elements of p and q will contain n/2 -1 local maxima?

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

    Endpoints can't be local maxima, so the possible positions of local maxima is 2..n-1
    (n — 2 positions)
    2 local maxima can't be next to each other
    => Maximum n/2 -1 local maxima

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

      So what? Question is not "why n/2 — 1 is at most value", but "why we can always can obtain n/2 — 1"

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

        You see in this case, you can construct a sequence such that:

        • for $$$i \bmod 2 = p$$$ you'll have $$$a_i >= n + 1$$$

        • Otherwise you'll have $$$a_i <= n$$$

        Where p is $$$0$$$ or $$$1$$$.

        So then you'll find expect these numbers which is at position $$$1$$$ or $$$n$$$,you will have $$$i \bmod 2 = p$$$ is greater than both on the sides.

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

In solution editorial for problem B, the size of array t is log A (not log n). I'm confused so much reading that editorial.

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

for the question B, what am i getting wrong here: any corner cases or something?? or my logic is wrong?

https://codeforces.net/contest/1973/submission/261565983 i tried to debug but im unable to

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

    here is the testcase where your code failed

    1
    5
    2 3 0 2 1
    

    it's giving 2 unstead of 3

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

For problem F I wonder if it's necessary to swap a[1] & b[1] and solve twice, I think we can record the minimum and maximum cost to achieve a solution case and add the less of minimum cost and total cost minus maximum cost.

With this method I can solve some cases but got wa on test 10, and I cannot figure out what is wrong. For detailed implementation here is my submission: 261587221

»
5 weeks ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

Correctness Proof for Problem C Algorithm

Observation

There can be at most $$$\frac{N}{2} - 1$$$ local maxima (because boundaries cannot achieve this).

Constructing $$$\frac{N}{2} - 1$$$ Local Maxima

Even Positions (excluding $$$N$$$

  1. We aim to achieve local maxima at even positions (excluding $$$N$$$).
  2. We use a greedy approach to place $$$\frac{N}{2} + 1, \frac{N}{2} + 2, \ldots, N - 1, N$$$.
  3. Assign the larger $$$p_i$$$ to the smaller $$$q_i$$$.
  4. Then $$$a_{\text{new even}} \geq N + 1$$$.
  5. Next, we place the remaining positions with $$$1, 2, \ldots, \frac{N}{2}$$$, assigning the smaller $$$p_i$$$ to the larger $$$q_i$$$.
  6. Then $$$a_{\text{new odd}} \leq N + 1$$$.
  7. You know that "=" can only occur when $$$a_{\text{odd}} = N$$$.
  8. Therefore, this is correct for all odd positions where $$$a_{\text{odd}} \neq N$$$.

Odd Positions (excluding (1))

  1. We aim to achieve local maxima at odd positions (excluding (1)).
  2. We use a greedy approach to place $$$\frac{N}{2} + 1, \frac{N}{2} + 2, \ldots, N - 1, N$$$.
  3. Assign the larger $$$p_i$$$ to the smaller $$$q_i$$$.
  4. Then $$$a_{\text{new odd}} \geq N + 1$$$.
  5. Next, we place the remaining positions with $$$1, 2, \ldots, \frac{N}{2}$$$, assigning the smaller $$$p_i$$$ to the larger $$$q_i$$$.
  6. Then $$$a_{\text{new even}} \leq N + 1$$$.
  7. You know that "=" can only occur when $$$a_{\text{even}} = N$$$.
  8. Therefore, this is correct for all even positions where $$$a_{\text{even}} \neq N$$$.

Since there is only one $$$a_i = N$$$, the above discussion ensures that one of the above approaches must be correct.

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

259945476

Anyone why MLE??

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

    I think the query function is making a lot of recursive calls (O(n * lg (n) * lg(n)) which is a lot. Maybe write it iteratively?

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

Problem C (Cat, fox And double maximum) Video Editorial (Audio : Hindi) YOUTUBE CHANNEL LINk :: --Click Here

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

the spoilers make the solutions hard to read

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

261627325 Anyone why does it fail??

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

For problem E, why the necessary condition is "l<=R+1" and "L+n<=r". I can't understand... What do you mean by "being able to swap L,R with anything"? Under such condition, we can just swap L with [1,n] and swap R with [1,n-R+L]. Can anyone further explain it? Thank you very much.

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

    Sorry, I meant "to be able to swap $$$L$$$ and $$$R$$$ with at least one other element". The paragraph explaining this was a bit hard to understand, so I rewrote it a bit, hopefully it's clearer now.

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

      Sorry, I'm still confused. $$$l\le L+1, r\ge R+1$$$ should be enough to swap $$$L,R$$$ with one other element like $$$1$$$, right?

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

        $$$l \leq L + 1$$$ is stronger than $$$l \leq R + 1$$$, so some pairs $$$(l, r)$$$ for which you can sort the permutation may not satisfy your first condition. For example, in the last sample from the statement, the pair $$$(4, 5)$$$ doesn't satisfy your first inequality, yet you can still sort the permutation by choosing it. That's why you should look for another set of inequalities to describe the necessary condition.

        Note that we don't care about $$$1$$$ or any other element in particular, we just want to be able to swap $$$L$$$ and $$$R$$$ with anything else, possibly two different elements.

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

          Thanks for your reply!

          I just realize it is $$$l\le L + n$$$ or $$$r\ge R+1$$$.

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

            It's actually $$$l \leq L+n$$$ and $$$R+1 \leq r$$$. You need to be able to swap both $$$L$$$ and $$$R$$$ with at least one other element.

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

https://codeforces.net/contest/1973/submission/261664728

Can someone check what's the issue with this?? I know I am bad in implementations.

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

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

Problem A

The last test case 1 1 10.

How this is possible ? Question says , first and second friend made two points by two draw with the third friend( One by each) . So the third friend should have made 2 points . How he managed extra 8 points ?

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

I think Problem B is high-quality.

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

Problem C was easier than B

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

    C was more maths and problem solving based , B relied on knowledge more,i mean anyones who know segment tree or sparse would kill the problem .

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

For Problem C.

How did the no.of local maximas are atmost n/2-1?

For n=5

We've 2 maximas then how it is n/2-1

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

highly recommend this round cuz every problems have step-by-step hints so that we can solve the problem without relying too much on editorials. Wish to see in other rounds.

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

In problem B why can we say if an array is k-lonely then it is k+1-lonely? I don't understand why (ai|...|ai+k-1)|(ai+1|...|ai+k) = (aj|...|aj+k-1)|(aj+1|...|aj+k) in the editorial.

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

    You know that $$$(a_i| \ldots |a_{i+k-1}) = (a_{i+1}| \ldots |a_{i+k}) = (a_j| \ldots |a_{j+k-1}) = (a_{j+1}| \ldots |a_{j+k})$$$ if the array is $$$k$$$-lonely (it follows from the definition), so then you also have $$$(a_i| \ldots |a_{i+k-1}) | (a_{i+1}| \ldots |a_{i+k}) = (a_j| \ldots |a_{j+k-1}) |(a_{j+1}| \ldots |a_{j+k})$$$ , thanks to the properties of bitwise OR.

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

Can someone tell me how to solve the bonus2 in B? I'm just interested in it. Thanks.

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

    I'll leave some hints on how to get to the solution.

    hint1
    hint2
    hint3
    hint4
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

B was a very good problem. Has a very reusable idea

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

    Yeah I think it's great too,especially the two Bonus. Also D is pretty good, just interesting.

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

I have a weird WA in problem D when I add a line of code in the beginning:

if (n == k && k == 1) {cout << "! 1" << endl;continue;}

which will output the answer directly when n and k are both 1 and continue to the next testcase

following are two submitsions which only differ from the description above

https://codeforces.net/contest/1973/submission/263160320

https://codeforces.net/contest/1973/submission/263160243

Can someone teach me why, I'm new with interactive problems, thanks