Блог пользователя blobugh

Автор blobugh, 4 года назад, По-английски

Hello Codeforces!

We invite you to Codeforces Round 821 (Div. 2) starting on Sep/19/2022 17:35 (Moscow time). The round is rated for users whose rating is lower than 2100.

All problems were mainly created and prepared by me. One problem is revised by mejiamejia. I would also like to thank:

You will be given 5 problems with one subtask and 2 hours to solve them. The score distribution will be announced closer to the start of the round.

Good luck, and have fun!

UPD1: Score distribution is 50010001500 — ( 1500 + 750 ) — 2750.

UPD2: System testing has been finished. Congratulations to the winners!

Out of competition

  1. Geothermal
  2. SSRS_
  3. tabr
  4. jiangly
  5. tute7627
  6. m_99
  7. kotatsugame
  8. Ethan_Rao
  9. maspy
  10. smax

Official participants

  1. LikeStrangers
  2. i_will_be_less_than_blue
  3. tlvvpdus
  4. PokerCareer
  5. casual11
  6. wildwolf_ptyzs
  7. MahiruShiina
  8. 963noah
  9. LovelyEther
  10. warner1129

UPD3: Editorial is published.

  • Проголосовать: нравится
  • +404
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +292 Проголосовать: не нравится

How is this post 2 years old lol

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +203 Проголосовать: не нравится

    If you create a blog post and save it as a draft, when you publish it, it is labeled with the creation time instead of the publish time for some reason. But it still takes a huge amount of foresight to create a blog post for a contest 2 years in the future...

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Does it mean, I have to wait approximately half year more for my contest?)

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +125 Проголосовать: не нравится

2 years ago ◔_◔

»
2 года назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

2 years ago!!

LOL!

»
2 года назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится

Imagine getting a necroposting warning for commenting on a future contest

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

    "This post was published a long time ago. Please refrain from commenting unless you have a really reasonable cause to leave a comment. Necroposting is discouraged by the community." The reasonable cause is that the contest is starting in 4h :)

»
2 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

This must be a long-term project of creating a VERY VERY HIGH-CLASS Contest.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +118 Проголосовать: не нравится

Imagine waiting 2 years for a score distribution

»
2 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Imagine preparing a blog and waiting 2 years on round queue to publish the blog

»
2 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Hello, please put more contests on weekends thanks

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +113 Проголосовать: не нравится

Writes blog . . .

pic

Gets published

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

wow, what a scheduled site :) They have prepared times of contests since more than tow years ago!

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

wow 2 years ago

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Finally getting a canon episode after 2 years of fillers :)

»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

King Arpa orz

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

2 years ago ? amazing!!!

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

This is what called " time travel to 2020 " .

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

2 years ago ? it is ez to flash to see a scoring distribution >

»
2 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

When you use internet explorer to make a contest:

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

i like how just 2 of the testers are actually in div2

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    More of them were probably Div2 when they tested but their rankings have gone up in 2 years..

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I feel the same way, maybe I should invite some testers with lower ratings.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but the difficulty balance/overall was amazing for div2 round nonetheless, thanks!

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Eager to participate in a contest which was ideated before I even started Competitive Programming!

»
2 года назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +79 Проголосовать: не нравится

Blog owner waiting

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wonder if this round will be more difficult

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The round drafted to years ago! Wow!

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Blog should also contain:

Thanks to blobugh for coming up with the idea to use the drafted blog.

Really a nice idea, I think almost 50+comments will be just on this (at the end of contest).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Imagine creating a blog in corona period and posting it two years later when it's finally over...

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2 years ago I have only 0 ratings lol

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I created a blog too in case i become master and prepare a contest :)

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

OP’s first contest was held on 8/21 two years ago This blog was created two years ago and the Round is 821

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Time to upsolve everything from 2 years ago...

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think pset might be harder than as usual div.2 :(

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

In the spirit of blobugh, I too have created a draft for a future round:

https://codeforces.net/blog/entry/107056

See you all in 2 years for Round #999

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2 years ago lol?

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

when will there be a weekend round T_T

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I hope this everyone can achieve good results, and I hope I can also break through

»
2 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Jokes aside, I can think of two plausible explanations for the 2-year-old timestamp:

  1. It really did take that long to actually finalize the contest, possibly because people got busy or unavailable, or there was a lot of back-and-forth about the problems, etc. Observe that blobugh was not involved in problemsetting since August 2021, so they may have been preparing this contest across two years.

  2. blobugh started writing a blog entry two years ago (which may have been completely unrelated to any contest announcement) and then abandoned it for some reason. Two years pass, and they now decided to host a contest, realized that they had a draft from back then, and figured it would be amusing to edit that ancient draft to reflect this new contest, in order to see how people would react to the apparent age of the posting.

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I hope I'm the Candidate Master this time. Come on!

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Though I don't participate because the next day is one of my most important event at my school...

But two years for participating, waiting, and then publishing.

I have a huge respect for all the people who built this contest!

Hope everyone luck!

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

When will the score distribution be announced?

»
2 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

The score distribution will be announced closer to the start of the round.

So, we have to wait 2 years for score distribution.

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I hope I reach Expert today

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What about "The score distribution will be announced closer to the start of the round."??

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

blobugh may be author forgot to update score distribution. It's 3 minutes left to start contest.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

How many problems can you solve/submit in one minute in a contest ?

tourist : yes

(tourist orz)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's a nice contest , because I think each promblem is of the almost right difficulty .

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve D2?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Yes, i also wanna know. I think it is some dp that i'm just too stupid for. My greedy doesn't worked out

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      dp solution idea:

      create array pos of indexes of points we need to change

      it's easy to see that we only want to change the neighbors in our array using the x operation several times

      dp from left to right, 2 values — cost if used X for points i and i — 1 and if not used. Points modified with x add (pos[i] — pos[i — 1]) * x, other add y / 2 for each

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was this contest relatively easy compared to other div2 contests or I just had a lucky day?

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Well-balanced contest, thanks for authoring it, loved problems <3

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

After one day's work, I am too dumb to code...

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to do C?i could not think of any idea.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    let the first element of array has parity p . now check for the last element whose parity is p (let its position be j) .now for all 'i' from 1 to j-1 elements whose parity of element is p, apply one operation on i and j since both has same parity arr[i]+arr[j] will definitely be even i.e a[i]=a[j]

    now for all i from 2 to n whose parity is not equal to p apply one operation on 1 and i since arr[1] and arr[i] are of different parity their sum will be odd i.e arr[i]=arr[1]

    after this every element in array becomes equal.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I can describe my algo:

    1. Check weather first element even or not

    (if it is even)

    1. Find last occurrence of even element

    2. Now go through the whole array from left to right and if we meet even number do (i, lastEvenInd) to make them equal. If we meet odd number do (1, i) to make it equal to the first element

    Pretty the same if first one is odd, but all "odd" replaced with "even" and vice versa

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится

      Just do $$$l=1, r=n$$$ as first operation, then you can make all other elements equal to the border ones. Saves you the analysis by cases.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Make a[1] and a[n] equal. For i = 2 to n — 1, if a[i] + a[1] is odd, then the operation is (1,i), otherwise (i,n). After this we can achieve an array with the same number using n — 1 operations.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very nice problems!I have really enjoyed C!Congratulations to authors!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to do that C?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If first value is even, change all evens to last even, then change all odds to the first even (which is now equal to the last even).

      Similarly, if first value is odd, change all odds to last odd, then change all evens to the first odd (which is now equal to the last odd).

      In both cases, all values become equal.

»
2 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

E is the most ingenious task I have ever seen.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.net/contest/1733/submission/172736981 can somebody help me to find a stress test for my solution for c

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    test case:

    Spoiler

    your answer :

    Spoiler

    5 > 4

    Here is an answer:

    Spoiler
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there any chance of FST today? :3

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

In D1, what would be answer for the following test case

Test case

6 right?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    in D1,5 <= n <= 3000

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    n will be greater than 4

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    min array length is 5

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Not valid, since $$$n \geq 5$$$. I was worried about this case too, but they always made sure it's possible to deal with a consecutive mismatch through two $$$y$$$-swaps.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's an invalid test case.

    N>=5, Mentioned in the constraints.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for pointing that out! I totally missed this case. (So if not for the restriction on $$$N$$$ I would have failed probably pretest but for sure system test. Note: Always think about small cases! The only special case I thought about was with $$$N=2$$$, which would have needed a seperate consideration too.)

»
2 года назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

I feel like D2 should not have been worth only half of D1, since the additional work required for D2 that isn't covered by D1 is significantly tougher than D1 by itself, in my opinion. Like, I understand the argument that D2 by itself is worth 2250, but I think the distribution should've favored D2 more, to something like (1000 + 1250) instead, which would also suggest that D1 is easier than C (which, imo, is the case, if only because it's easy to get confused in C by the two scenarios, whereas D1 is very straightforward).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve B and C?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    B: One of $$$x$$$ or $$$y$$$ must be 0, because the loser of the first round wins 0. WLOG let $$$x$$$ be the non-zero value. Then everyone who won at least once would win exactly $$$x$$$ times, so $$$n - 1$$$ must be divisible by $$$x$$$. Now it's easy to make somebody win $$$x$$$ times and then let the next challenger be the winner for $$$x$$$ rounds and so on (it's simpler if 2 wins at first, so the winners are all gonna have IDs of the form $$$2 + ix$$$).

    C: If the first value is even, then apply the operation on each even with the last even, to make all evens equal to the last even. Then apply the operation on each odd with the very first value (even) to make all odds equal to the first even (which is now equal to all other evens). Similarly, if the first value is odd, then apply the operation on each odd with the last odd, to make all odds equal to last odd. Then apply the operation on each even with the very first value (odd) to make all evens equal to the first odd (which is now equal to all other odds).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A great contest and 200+ rating increment :) Problem D2 is really nice Thanks !

»
2 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

You changed the constraints of D2 after the contest started and didn't even bother to make an announcement? I opened the “complete problemset” at the beginning of the contest. Got so many runtime error because of this. This is pathetic.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry for that. The constraint changed just before the contest start, and it seems to have taken some time to reflect on the problem page.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

imo, today contest is a lot of casework. It's not very interesting.

»
2 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Problem E is similar to JOI 2009 Finals Problem 4. Also Problem D2 can be solved in $$$O(n)$$$ time

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Can you explain your O(N) approach?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      What's a non-O(n) approach? I couldn't think of one except an O(n) algorithm.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +42 Проголосовать: не нравится

      I used a simple DP whose size is equal to the number of mismatched positions. $$$dp[i]$$$ is the optimal way to pair up the first $$$i$$$ mismatches, except if $$$i$$$ is odd, in which case, one element is left unpaired. The array $$$mis[]$$$ stores the mismatched indices.

      For even $$$i$$$ (nothing should be unpaired),

      $$$dp[i] = \min (dp[i - 2] + (mis[i] - mis[i - 1])x, dp[i - 1] + y)$$$

      For odd $$$i$$$ (one element unpaired),

      $$$dp[i] = \min (dp[i - 2] + (mis[i] - mis[i - 1])x, dp[i - 1])$$$

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        This can be made even simpler by not separating into an even and odd case and changing the recurrence to $$$dp[i] = min(dp[i - 2] + (mis[i] - mis[i - 1])x, dp[i - 1] + y/2)$$$ and setting $$$dp[1] = y/2$$$.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        Hello. For even i, in the second part of the min function, how can you assume that the unpaired index in dp[i-1] is not i-1? Because if it is i-1, you cannot pair it with i with y cost. Thanks.

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          I only use the DP for the case of $$$x < y$$$ (D1 has a trivial algorithm that can be copied for $$$x \geq y$$$ in D2). If $$$dp[i - 1]$$$ has the last element as unpaired, then the minimum of the two considered values will always be $$$dp[i - 2] + (mis[i] - mis[i - 1])x$$$. Therefore, the $$$dp$$$ array will never store a value that corresponds to spending $$$y$$$ cost for an adjacent pair.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        The cost of the operation is x, if mis[i-1] + 1 == mis[i]. Can you please explain, why you are multiplying x with the position difference. Why (mis[i] - mis[i-1]) * x ? Thanks

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Let's say there is a mismatch at index $$$p$$$ and the next mismatch is at index $$$q$$$. One way to flip both of these is to apply the operation on $$$(p, p + 1)$$$, then on $$$(p + 1, p + 2)$$$, then $$$(p + 2, p + 3), \ldots, (q - 2, q - 1), (q - 1, q)$$$. This will flip index $$$p$$$ and $$$q$$$ as desired, while indices in between (if any) will flip twice and will therefore be unchanged. There are $$$q - p$$$ operations being performed here, each with a cost of $$$x$$$, so the total cost of this approach is $$$(q - p)x$$$.

          It is easy to observe that if any $$$x$$$-operation is to be performed at all, an optimal solution would apply it to some mismatched index chained to the next mismatched index as described above. Therefore, the DP only considers whether the latest mismatched index should be restored through an $$$x$$$-operation chain from the previous mismatched index or not, choosing the minimum of the two options.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone else totally misread A without the second mod k? just me being uniquely bad at reading problem statements... again? oh.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    My misreading was more severe. I thought the operation was a[i] = a[i] % k, a[j] = a[j] % k and then swap a[i], a[j]. I have no idea how I could read like that.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    misread C and didnt note m had to be less than n and wasted 30 mins coming up with a soln then realized after seeing pretest 1 fail and got correct soln 10 mins after contest ;)

    i should really get better at reading in contest nerves

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Solved 3 and one partial problem on Div.2 for the first time. Maybe the problems were a bit easier than usual Div.2.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

is D2 just D1 with x >= y, and if x < y then we:

get all the indices with different value of a[i] and b[i] clearly we can only make flip the bit pairwise. So the number of differences must be even. lets go from right most index to left most, If the gap (i — j) is D, then cost is D*x, but cost is capped at y. It's clear that it's always best to greedy starting from the right most index.

Just greedy imo solved in O(n) time. Idk what's the n^2 solution is given the max input is only 5k

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    then why did my approach — 172725963 — get a WA2? what cases did I miss?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    I think that this does not work in this case:

    Test
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    This is not correct. It is not necessary that you always match consecutive ones. Consider all non-matching indices to be $$$[1,3,4,7]$$$. You might match 4 with 7 and 1 with 3(cost = $$$min(y,3x) + min(y,2x)$$$). But matching 1 with 7 and 3 with 4 could be better($$$min(y,6x) + x$$$). This may happen when $$$y = 2x$$$ for example.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    This is incorrect. Imagine that the indices where a and b are different are 1, 3, 4, 7, x = 1 and y = 2. Your solution would match 4, 7 and 1, 3 for a total cost of 4. But the optimal cost is 3, from matching 3, 4 and 1, 7.

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

    That should not work. Do you have a submission to try and hack? X_XX_X with $$$y=3$$$ and $$$x=2$$$ should hack it.

    Edit
  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Consider case:

    12 1 6

    100001100001

    000000000000

    According to you greey algo,the strategy is:

    -change the 7-th and 12-th bit costing 5;

    -change the 1-th and 6-th bit costing 5.

    The total cost is 5+5=10.

    But the optimal strategy is:

    -change the 1-th and 12-th bit costing 6;

    -change the 7-th and 6-th bit costing 1;

    The total cost is 6+1=7.

    Maybe I misunderstand you method,can you explain it?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Greedy doesn't work. Consider the following test-case:

    6 2 5
    101101
    000000
    

    A greedy approach would pair the first two 1s with a cost of 4, and the last two 1s with a cost of 4 as well, for a total cost of 8. However, the optimal choice would be to pair the middle two 1s for a cost of 2, and then the first 1 with the last 1 with a cost of 5, for a total cost of 7.

    If your submission was truly accepted, then it could not have followed the greedy approach that you just described (unless the pretests were really bad, but I doubt that's the case, considering how many penalties I observed in D2).

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ok this doesn't work then. I guess it'd have to be DP.

»
2 года назад, # |
Rev. 5   Проголосовать: нравится -18 Проголосовать: не нравится

Can anyone help me finding the cause of getting runtime error in problem C?

This is my submission of C

UPD:

GNU C++20 (64) giving AC but

GNU C++17 and GNU C++14 giving RE. Don't know why!!
AC Submission
RE submission
Can anyone explain?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used GNU C++17 (64) and got Accepted.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But why?!!!!

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You have a problem in this line : ll mn=a[od[od.size()-1]],pos=od[od.size()-1]; Take this test case for example :

        1
        1
        0
        

        Here (od.size() == 0) so od[od.size() — 1] ==> is like od[-1], which is a problem in cpp, I'm not shure but I think it's a buffer overflow.

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Look, there is condition
          if(a[1]%2) then do the odd part first else do the even part first.

          so there will be at least one element in the container. so its not the problem.

          in your case. even part will execute first.

          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            sorry, you are right. actually it's this line :

            ll mn=a[ev[ev.size()-1]],pos=ev[ev.size()-1];

            for this test case :

            1
            1
            1000
            

            in this case (ev[ev.size() — 1] ==> 1000) so a[1000] will be out of boundary.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ok, here is your code giving AC in GNU C++17 : 172837822

        Changes :

        for(ll i=od.size()-2;i>=0;i--) ==> for(ll i=(ll)od.size()-2;i>=0;i--)

        for(ll i=ev.size()-1;i>=0;i--) ==> for(ll i=(ll)ev.size()-1;i>=0;i--)

        for(ll i=ev.size()-2;i>=0;i--) ==> for(ll i=(ll)ev.size()-2;i>=0;i--)

        for(ll i=od.size()-1;i>=0;i--) ==> for(ll i=(ll)od.size()-1;i>=0;i--)

        od.size() is unsigned, and when you tried to subtract a bigger value it caused a problem, you can search more about that.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

such a great contest! orz blobugh

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for the second case of B,why can't make each player won x times to achieve it? just like print:2 3 4 5 6 7 8 instead of -1? qwq

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have managed to pass D2 using a naive $$$n^3$$$ dp but checking only limited transitions. Feel free to hack this.

https://codeforces.net/contest/1733/submission/172714403

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain the recursive formula for D2?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain D1 in a simple way please? Thank you...

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    Count how many indices have mismatches. Each operation flips exactly two bits. If the number of mismatches is odd, then it's impossible to fix all the mismatches, so the answer is -1. Otherwise, there are two cases:

    1. The exceptional case to watch out for is when there are exactly two mismatches AND they are on adjacent bit positions. In this case, you can pair them directly for a cost of $$$x$$$, or you can pair each of them with some other distant bit position for a cost of $$$2y$$$ (note that this distant bit position flips twice, so it reverts to its original value). In this case, we output whichever of $$$x$$$ or $$$2y$$$ is smaller.

    2. In all other cases, it's always possible to resolve the mismatches using $$$y$$$ operations. If we have only two mismatches, then they're not next to each other (since that's covered by Case 1), so you can just use a $$$y$$$ operation. If there are more than two mismatches, you can divide the number of mismatches by 2, and pair indices from the first half with indices from the second half, so the paired indices are never adjacent and the cost is always $$$y$$$. Here, the answer is just (number of mismatches)/2 * y. This is always optimal because $$$x \geq y$$$.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Me being happy for everyone else while getting prolly -80 myself

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

D1 is like is it this easy, what the fuck?????

»
2 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

I have managed to solve problem D2 with O(N) time complexity using simple dp.

https://codeforces.net/contest/1733/submission/172742046

blobugh I think it would be better to make N up to 2e5, but anyway contest was great. Thanks for problems!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    Thanks for enjoying! Actually, some testers gave O(n) solution of D2 already, but we decided to accept O(n^2) solution for difficulty balance.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Submitted AC solution of D1 2 seconds after end of contest , sad

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is my first contest. In contests this comes under unrated contest but the blog post says its rated. Can anyone clarify?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It's rated, but it takes some time for rating changes to apply, since there is system testing after the contest (which is already done for this one) and a procedure to find and remove cheaters (which can take quite a while). After that, the rating changes are applied and the contest should be moved to the rated contest list.

    There are exceptional scenarios in which a contest that is supposed to be rated becomes unrated (such as when a problemsetter unethically copies a problem directly from another source), but I don't think there were any issues for this particular contest, so it should hopefully be rated. Just be patient...

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Until the rating changings will be done it is unrated (it usually takes about 12h-16h)

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

OperationForces

»
2 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

For Problem B, I observed that either player 1 will win 0 matches or player 2 will win 0 matches.

That means for a valid solution either x has to be 0 or y has to be zero.

Am I correct?

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

In D1 problem, I finded an bordercase.

I sended two codes and both receive Accepted. But the output for this input:

1 4 4 1 0110 0000

is different. The correct output is 3, but in the second submission the output is 4.

This special case is to n = 4, a2 != b2, a3 != b3 and x > 3y.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

A memorable round for me!

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

All Top 10 USERS are newly registered except 1-2. this is so demotivated things I have seen on CF

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится

.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to Solve E,the last problem?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cyan Gang finally

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I was inspired by this question https://codeforces.net/contest/1728/problem/D ,and write the dp dp[l][r] from dp[l+2][r], dp[l][r-2],dp[l+1][r-1], but it failed. It seems be same as the dp like others, but it is sure may be wrong. my failed solution is https://codeforces.net/contest/1733/submission/172731642 , thanks for comments!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As an expert, i messed up in this contest :((

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

I tried solving Problem D1, but getting wrong answer on 49th entry of test case 2, Please tell me where I am wrong....Please Help. I already did 9 wrong Submissions.

ll f(ll i, string s, string s1, ll n, ll x, ll y) {
    if(s==s1) return 0;
    if(i>=n) return 1e10+7;
    if(s[i]==s1[i]) return f(i+1, s, s1, n, x, y);
    ll p=(ll)1e10+7, q=(ll)1e10+7;
    if(i+1<n) {
        string s2=s;
        s2[i]=s1[i];
        s2[i+1]=='0'?s2[i+1]='1':s2[i+1]='0';
        p=x+f(i+1, s2, s1, n, x, y);
    }
    for(int j=i+2; j<n; j++) {
        string s2=s;
        s2[i]=s1[i];
        s2[j]=='0'?s2[j]='1':s2[j]='0';
        q=min(q, y+f(i+1, s2, s1, n, x, y));
    }
    return min(p, q);
}

void solve()
{
    ll n,x,y;cin>>n>>x>>y;
    string s,s1;cin>>s>>s1;
    ll ans = f(0, s, s1, n, x, y);
    if(ans>=(ll)1e10+7) cout<<-1;
    else cout<<ans;
    cout<<ln;
}
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Here is a counterexample:

    5 3 1
    00011
    00000
    

    Your algorithm returns 3, but the correct answer is 2. You can simply apply the operation on indices $$$(1, 4)$$$ and then on $$$(1, 5)$$$. Index 1 flips twice, so it reverts to 0, while indices 4 and 5 each flip once and become 0. The cost is $$$2y = 2$$$, which is better than spending $$$x = 3$$$ cost on flipping $$$(4, 5)$$$ directly.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

it was good . But I miss one condition in problem D.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please upload the editorial !!! blobugh

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

No tutorial?

»
2 года назад, # |
Rev. 5   Проголосовать: нравится +40 Проголосовать: не нравится

Problem E is quite beautiful. First we note, for each slime its sum of coordinates increases by 1 each step. So each diagonal can hold only one slime per timestep. So Slimes will never combine.

Now we look at a modified game. Imagine there are $$$t-x-y$$$ slimes in $$$(0,0)$$$. We move them all at once. If there are $$$S(X,Y)$$$ slimes in $$$(X,Y)$$$, then $$$\left \lceil{S(X,Y)/2}\right \rceil $$$ will move to the right and $$$\left \lfloor{S(X,Y)/2}\right \rfloor $$$ will move down. This way in dp-style we can determine how many slimes $$$S(X,Y)$$$ will have passed through each field.

Now we start a lonely last heroic slime at $$$(0,0)$$$ and move it along the axes. It is the only one that possibly can fulfil the query (because, as we have noted, their sum of coordinates always increases by one). If $$$S(X,Y)$$$ is even, we move it to the right, because an even number of slimes passed this field so the conveyor will point to the right. If it is odd, we move the slime down. If it ever reaches $$$(x,y)$$$, then the answer is YES. Else the answer is NO.

See also here, my commented code: 172810570

Also here's a program and some snapshots to animate the state of the conveyor after each slime:

1k slimes
50k slimes
Program for Animation
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could you please share the editorial?

»
2 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Ah, yes. Here we go again! How can we prove that we didn`t cheated if the problem was very simple and we wrote some same fucking "for"s and "if"s? Please, can you do something about it? sadly I have no suggestions.

Внимание!

Ваше решение 172700828 по задаче 1733D1 значительным образом совпадает с решениями других участников и находится в группе одинаковых решений magnuscarlsum/172691072, allcasepass2/172699857, Daqlet/172700828, ashutosht-code1845/172701732, Willcheatyou/172703661, Eccentric_9/172704862, master_codencode/172707763, 3ayzMedal/172710754, abdelrahmanlotfy317/172712290, nithinkumar7070/172713581, rank01/172713911, manojkumar1438/172714519, Peeyush556/172715164, Ssr_536/172715571, aditya_ahlawat_1309/172715592, 2001atanughosh/172716000, 2000032121/172716579, SouvikCH/172716698, VeeraVamshi/172716771, comddingg/172717409, off_campus/172717545, new_start_for_win/172717554, lohith1216/172718150, gandesaikiran8902/172718165, Krilin/172719125, padmasai1216/172719379, praneethadevulapalli/172719576, Sase/172719821, 2000031362/172719887, rishav__01/172720183, abhinavvvv131/172720486, Kal.El/172721004, poojith_mannepalli/172721475, Rai_Utkarsh/172721634, klu_2000031535/172721653, Abhyudai_Mishra_2024/172721673, Twinkle_Star29/172721976, janender0707/172722279, sriya30295/172722593, CheatPlusPlus2/172722888, s23singh/172723100, yashika_03/172723830, KL_2000031102/172724435, oko053651/172725936, officialnj26/172726410, asal.jahanshiri/172726760, abhishek_090802/172727205, Raj088/172727415, suiiiii/172727578, pera2008/172727869, MananPopat/172728011, brainsoft/172728527, NoDrop30/172728830, dharabindal123/172728942, pasyanthi/172728989, azhakim/172729176, kl_2000032077/172729267, testac2/172729273, Sultanov_I/172729734, Parthverma22/172729855, ROBOSTAR/172730887, 2000031415JayanthKrishna/172731001, MomenSh306/172731333, Omar_Khaled_Me/172731412, Mohammd_Benni/172731596, Kither/172732436, ankitkr22201/172732495, Mohd_aman000/172732598, el_2000030813/172732819, uokeynoname/172733416, klh2010030535/172733528, Pranav1903/172733534, stunner2k22/172733859, Youssef_mkdaad/172734296, harshit0077/172734836, Coding1212/172734863, Sai_Chandu/172734996, kruthik/172735039, navneetguptacse/172735437, Pavan_Yaddanapudi/172735715, g_aadesh29/172735885, VLovesD/172735998, max_d/172736062, Pinakakali/172736150, umamhesh/172736756, 2010030159/172736858, xanaxrehabclub/172737066, ahmedfereg480/172737296, Kaustubh01/172737441, klu_2000031628/172737629, CeLLxMaTTriX/172737688, anujmishra/172737884, ishivchaudhary/172738211, Levii_Ackerman/172738319. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://codeforces.net/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Regarding Similar Solution between ojasGupta/172672316, smit086/172709047. I think its mere coincidence that the codes where so similar, I havent cheated once and was only using vscode. Whereas the other person has been caught cheating multiple times. Please review.