prvocislo's blog

By prvocislo, 6 months 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

»
6 months 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).

»
6 months 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

  • »
    »
    6 months 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?

    • »
      »
      »
      6 months 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%.

      • »
        »
        »
        »
        6 months 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?

        • »
          »
          »
          »
          »
          6 months 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

          • »
            »
            »
            »
            »
            »
            6 months 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

        • »
          »
          »
          »
          »
          6 months 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.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            will surely try so

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks a lot man, very helpful :)

          • »
            »
            »
            »
            »
            »
            6 months 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

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

            :)

        • »
          »
          »
          »
          »
          6 months 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.

          • »
            »
            »
            »
            »
            »
            6 months 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

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          looks right to me

          • »
            »
            »
            »
            »
            »
            6 months 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.

            • »
              »
              »
              »
              »
              »
              »
              6 months 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

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

      Deleted

    • »
      »
      »
      6 months 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!

  • »
    »
    6 months 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 .

    • »
      »
      »
      6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months 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
  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        haha no problem broski, the more explanations the better

    • »
      »
      »
      6 months 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??

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 months 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 :)

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C is really good

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

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months 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...

    • »
      »
      »
      6 months 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.

    • »
      »
      »
      6 months 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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 months 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

          • »
            »
            »
            »
            »
            »
            6 months 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

    • »
      »
      »
      6 months 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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B without binary search: 261388922

»
6 months ago, # |
  Vote: I like it +26 Vote: I do not like it

prvocislo orz <3

»
6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C was nice from the proof and math work side

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

in C 2nd hint

n/2 -1 not +1

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

B with segment tree and binary search 261367730

»
6 months 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?

  • »
    »
    6 months 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.

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice alternative approach :)

    • »
      »
      »
      6 months 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?

      • »
        »
        »
        »
        6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

B is a very nice problem.

»
6 months 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

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

    great explanation sir : )

  • »
    »
    6 months 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!

    • »
      »
      »
      6 months 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!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Damn ! that's a nice observation

»
6 months 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

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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

  • »
    »
    6 months 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 :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you prvocislo for all the hard work <3

»
6 months 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

»
6 months 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?

  • »
    »
    6 months 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)

»
6 months 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

  • »
    »
    6 months 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 .

»
6 months 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

»
6 months 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.

»
6 months 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

  • »
    »
    6 months 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?

    • »
      »
      »
      6 months 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.

»
6 months 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

  • »
    »
    6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C is amazing! Brilliant round!

»
6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the tutorial, it was really helpful.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Loved The B Problem.

My Binary Search Solution

»
6 months 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

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is a very good problem.Interesting.

  • »
    »
    6 months 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)?

»
6 months 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

»
6 months 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.

  • »
    »
    6 months 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 :(

»
6 months 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

»
6 months 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!

»
6 months 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

»
6 months 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?

  • »
    »
    6 months 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.

»
6 months 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

»
6 months 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.

  • »
    »
    6 months 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}$$$
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I mistake bitwise-or for XOR.

      • »
        »
        »
        »
        6 months 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

»
6 months 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

»
6 months 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.

»
6 months 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.

»
6 months 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?

  • »
    »
    6 months 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

    • »
      »
      »
      6 months 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"

      • »
        »
        »
        »
        6 months 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.

»
6 months 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.

»
6 months 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

  • »
    »
    6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months 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

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

259945476

Anyone why MLE??

  • »
    »
    6 months 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?

»
6 months 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

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

the spoilers make the solutions hard to read

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

261627325 Anyone why does it fail??

»
6 months 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.

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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?

      • »
        »
        »
        »
        6 months 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.

        • »
          »
          »
          »
          »
          6 months 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$$$.

          • »
            »
            »
            »
            »
            »
            6 months 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.

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

              how is it guarantee we can swap L and R with at least one other element? Tutorial does not clarify this and I can't

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

              Separated these conditions are useless, why if we combine them it's enough to swap them with at least one another?

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
6 months 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 ?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Problem B is high-quality.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was easier than B

  • »
    »
    6 months 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 .

»
6 months 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

»
6 months 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.

»
6 months 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.

  • »
    »
    6 months 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.

»
6 months 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.

  • »
    »
    6 months 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
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! It helps a lot!

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

      i am not able to figure out the checking if array is m-lonely part , how to check that in less than o(n*m) , i am so confused

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months 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.

»
6 months 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

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

problem B is also can be solved using segment tree and binary search

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

for problem E, i am not able to count the number of pairs $$$l, r$$$ such that $$$l \neq r, l \le L + n, r \ge R + 1$$$. Specifically, i don't know how to count when $$$L + n > R$$$. It seems that some pairs would be count more than once. 261999566 I can't understand the impementation.

    ll l = 0, r = 2 * n;
    for (int i = 0; i < n; i++) if (i != p[i] &mdash; 1)
    {
        l = max(l, p[i] + 1);
        r = min(r, p[i] + n);
    }
    ans += all(2ll * n) &mdash; all(l &mdash; 1) &mdash; all(2ll * n &mdash; r);

what does $$$l, r$$$ denote? and why add those number to answer?

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

For problem E, the editorial only mentioned that such an $$$x \in [l, r]$$$ exists.

we can actually let $$$x = \max(l, X + 1)$$$ which is valid.

Proof