sszcdjr's blog

Refact.ai Match 1 (Codeforces Round 985, Div. 1 + Div. 2)
By sszcdjr, history, 2 months ago, In English

Hello, Codeforces!

We (KDOI Team) are glad to invite you to take part in Refact.ai Match 1 (Codeforces Round 985), which is the 8th CP contest held by us! You can view the previous rounds by us here.

  • Number of problems: $$$9$$$ ($$$0$$$ interactive);
  • Start time: Nov/09/2024 17:35 (Moscow time);
  • Contest duration: $$$180$$$ minutes;
  • Score distribution: $$$750-1250-1750-2250-2500-3000-3500-5000-5500$$$.

The problems were authored and prepared by Error_Yuan, wyrqwq, Otomachi_Una and me sszcdjr.

A few words from our sponsor:

We’re Refact.ai, an open-source AI Coding Assistant, and on November 9th, we’ll be hosting our first round on Codeforces! Winners will receive valuable prizes, and all participants will have a chance to get some exclusive merch from us.

Refact.ai is pushing AI beyond simple code completion. Soon, we’ll launch the Autonomous AI Agent—a developer’s buddy that handles real engineering tasks end-to-end, from planning and coding to testing and deployment. You can read more about us in this announcement.

If you're excited about AI in software development and want to build the future instead of focusing on the trivial, join Refact.ai, founded by a former OpenAI researcher. We’re looking for talented Researchers and Backend developers to join our team.

Apply

Prizes:

  • 1st place: 500 USDT
  • 2nd place: 300 USDT
  • 3rd place: 200 USDT
  • 4-5th place: 100 USDT
  • Top 50 participants will get T-Shirts
  • Additionally, 50 random participants from the top 51-500 will receive a T-shirt

Good luck in the contest!

On the right, badges of the authors. From top to bottom, left to right are Error_Yuan, Otomachi_Una, sszcdjr and wyrqwq respectively.

We would like to thank:

Good Luck & Have Fun!

UPD1. The Editorial was published.

UPD2. Congratulations to the winners!

  1. Benq
  2. jiangly
  3. hos.lyric
  4. Radewoosh
  5. arvindf232
  6. Nachia
  7. ksun48
  8. Szoboszlai10
  9. Endagorion
  10. _Serge_
  • Vote: I like it
  • +645
  • Vote: I do not like it

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

As an author, I can confirm that no problems are authored by AI!

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

    As another author, I can confirm that as I authored at least one problem, I'm not AI!

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +185 Vote: I do not like it

      I think you are a bot as I don't know how your mind works.

      → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +167 Vote: I do not like it

      As a tester, I can confirm that the authors are all bots.

      → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      As a tester, I can confirm that a lot of people think I am AI!

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +49 Vote: I do not like it

        ...which really kinda shows from the downvotes, I told you 😂

        → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      I think you are a bot as I don't know how your mind works.

      → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

As a bot, I can't participate in this contest.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +117 Vote: I do not like it

As a tester, I was really looking forward to participating in this sponsored contest, only to realize that I had already tested it.

→ Reply
»
6 weeks ago, # |
  Vote: I like it -137 Vote: I do not like it

As the boyfriend of the girlfriend of the tester cayaxi09, may you good luck & have fun!

→ Reply
»
6 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it

The round's number "985" is special for chinese, especially for our students.

Hope you all can perform well in the "special" round.

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

    why

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

      Because 985 mean a group of good colleges in China.

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

      Project 985 refers to the drive by Chinese government (announced in May '98) to push the best Chinese universities (original list had about 9) to be among the world's best.

      → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Heartbreakingly, my university is still 983 steps away from being a 985.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

As a newbie, I hope that I learn more in this contest.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

The score distribution is scaring. I hope I can reach master in the contest.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +114 Vote: I do not like it

As a tester, I might lose a T-Shirt.

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

I wonder what the tourist will choose: the chance to win money with the risk of losing their rating, or doing nothing at all?

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

    If you just think that he could ever think in the 2nd choice (losing the rating), then you don't know him.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +176 Vote: I do not like it

As an author, I prepared $$$998244353$$$ problems and wrote $$$998244353$$$ pieces of editorial in all (modulo $$$998244353$$$).

→ Reply
»
6 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Love the score distribution, 750 for A problem means 1 WA only cost ~ 7% score...

It'll be less painful for stupidity submission sometimes.

→ Reply
»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it
Spoiler
→ Reply
»
6 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

what is score distribution.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, there will be 0.3 problems about penguins.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

24 points to expert ! lesss gooooooooo

→ Reply
»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Bruh C is worth 1750!!! Thats actually too much. I'm assuming it'll be wayy more difficult than usual.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +84 Vote: I do not like it

As a tester,I'm a bot.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

As a tester, I really like some of these problems.

For Chinese high school students, "985" is a special number. Wish everyone to get into the university of their dreams!

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

    what's the coloration

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

      a kind of Chinese university, they are usually the best in China

      → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +47 Vote: I do not like it

As a tester and the friend of the author sszcdjr, I can confirm that the authors are all not AI, because I can't solve any of their problems! GL&HF!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just out of curiosity, what is the relationship between the score of a question in a contest and its difficulty in the problem set (https://codeforces.net/problemset). I know higher score questions are more challenging, but after noticing 2 questions with score ≥ 5000 and no questions in the problem set with this difficulty it made me realize its not a identity mapping between the two (that is difficulty(score) != score)

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's AI vs Human Mind

→ Reply
»
6 weeks ago, # |
  Vote: I like it -48 Vote: I do not like it

Is there Chinese statement?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

Finally got the Tourist title :)

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How come the badges of the authors are not related to their PFP I thought in CF badges come from your CF PFP.

→ Reply
»
6 weeks ago, # |
  Vote: I like it -52 Vote: I do not like it

Please reschedule, it's my birthday

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Want to see tourist's rating change!

→ Reply
»
6 weeks ago, # |
  Vote: I like it -43 Vote: I do not like it

HANK!!! DON'T ABBREVIATE COMPETITIVE PROGRAMMING!!! HANK!!!

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

wyrqwq What's the behind your badage ?

light ray ? physics ?

btw like it

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    geometrical optics, it's a convex lens and the object is positioned b/w the pole and focus hence a virtual image is formed.

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    In fact, it is the badge of sszcdjr)

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

→ Reply
»
6 weeks ago, # |
  Vote: I like it +71 Vote: I do not like it

rainboy vs 5500 points problem

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to Become candidate master after this contest

→ Reply
»
6 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

Is it rated?

→ Reply
»
6 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

this contest is rated? ;-;

→ Reply
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope to reach CM in this contest!

→ Reply
»
6 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

So this contest is rated?

→ Reply
»
6 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

I thought of reaching the pupil at the end of the contest, need 126 rating. After seeing score distribution, I guess I need to wait for another contest.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I think it clashes with COCI :(

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

    Nope, it seems that COCI starts 25min after the CF round ends.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Loved the '0' interactive phrase .

→ Reply
»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Good luck for everyone!

→ Reply
»
6 weeks ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

I think, contest will be interesting without interactive problems, (because I can't really solve it)

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

dsf

→ Reply
»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

As an author, I can confirm that no problems are authored by AI!

→ Reply
»
6 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

The contest is about to start in an hour, but only 17000 people registered!? Is this a special feature of Div1+2?

Last Div2 30000+ people registered, and this one is a Div1+2, shouldn't there be more people?

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

    As i see in previous rounds,it's probable due to length of the round,many people skip the 3 hr contests.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

As a tester,Hanghang007 hanghanghanghanged

→ Reply
»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

this is the hardest div

→ Reply
»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

rainboy being RAINBOY !!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I read all the comments!

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

c any hints??

edit : got it thanks

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

    DP

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    dp with 3 states — in interval, before interval, after interval

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Me personally, I did a Binary Search on answer but I'm expecting an FST lol

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

      can you explain

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

        So... Let x be the final rating i can achieve. Here's how u verify if there's a possible answer. So u start from 0 and reach i with rating say a. Now the final rating is x so u can trace it back and check what the possible rating could have been at every index j from back.

        Now for any index i, U can remove the subarray [i,j] if i can achieve the rating x from j. And this is something that we have already precomputed from the back.

        Will share the sub after system testing

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

          how did you calculate the achievable rating from back

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

            I just simulated the process in the backward direction.

            Here's the sub: https://codeforces.net/contest/2029/submission/290731708

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

              I also cam up with same idea but while simulating backward I couldn't get it right as in case when my current rating after ith x and ai is also x so previous possible rating would be either x-1 or x this divergent thing makes it tedious and branching outwards for implementation, could you explain how u came up with computing from the back.

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

                Yeah i faced the same problem. So the trick is to always consider it to be x-1 and not x. This is because u wanna consider the minimum possible rating at index j with which u can achieve the final rating x. So its always optimal to take x-1 instead of x when ever u have a choice.

                Another way of thinking would be that the rating is always continuous. So if i got some y<x (final rating) I would have always got all ratings between y and x included.

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

                  ohh nice, missed it there

                  thanks.

                  → Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Note that at each index $$$i$$$ (right of the interval), you need to maximize the current rating at $$$i$$$ to reach the global maximum. It is not easy to note this.

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

    Binary search

    → Reply
»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

I spent 2 hours on C, yet did not solve it.

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Prolbem E. Why this is WA21? (I can't resubmit now, and in submission there is junk code.)

Code
→ Reply
»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

wtf C, I'm so broken mentally, been doing cp for nearly 2 year still cannot solve C confidently, how this is even possible. god abandoned me

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Why such a small number of participants? Only 7k+ solved A.

Edit: contest without subtasks feels so good.

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

    A must have scared them away

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

    participating div1+2 is generally harmful for div2

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    It clashed with leetcode's contest. Maybe that's the reason.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do C?

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

    you can use dp

    → Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    imagine three states:

    Before

    Skipped

    After

    From before, we can go to:

    — before again

    — skipped

    From skipped:

    — skipped again

    — after

    From after:

    — after again

    With this in mind, keep three arrays (one for each state).

    From the transitions, hopefully you can see:

    before[i] = max rating with i before interval = before[i-1]

    skipped[i] = max rating with i in skipped interval = max(skipped[i-1], before[i-1])

    after[i] = max rating with i after skipped interval = max(skipped[i-1], after[i-1])

    you also need to compare after[i] and before[i] to a[i] and add 1, take 1, or leave the same accordingly

    You can then set base cases:

    before[0] = 1 (ai > 0, rating starts at 0, so rating will always be 1 to start, if we take i=0)

    after[0] = -1 (0 cannot be after interval)

    skipped[0] = 0

    then fill the arrays from i=1 -> i=n-1, and the answer is max(after[n-1], skipped[n-1])

    (without before[n-1] since we have to skip atleast one contest).

    hope this made sense :)

    → Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Damn got cooked... someone explain C please?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Really enjoyed the problems. Great work authors!

→ Reply
»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Seems like some $$$O(3^n)$$$ passed H.Is it intended?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Looks like skipping C worked well for me, I solved A, B, D, E, F and then failed to solve C for about an hour lol

→ Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hints for F?

Things I could observe:

  1. If all edges have same colour, answer is clearly yes.

  2. If both $$$RR$$$ and $$$BB$$$ appear the answer is clearly no since there is at least one pair $$$(i, j)$$$ where all paths start with $$$R$$$ and end with $$$B$$$ and can thus never be palindrome.

  3. For simple alternating colours ($$$RBRBRB\ldots$$$), the answer is yes for odd $$$n$$$ and no for even $$$n$$$.

  4. The answer is no if an even length blocks of a colour appear more than once since there will be paths which are forced to start with $$$BB$$$ or $$$RR$$$ but can only have an odd number of the same colour at the end (example graph).

But I still have no clue how to generalize this to a solution.

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

    For simple alternating colours (RBRBRB…), the answer is yes for odd n and no for even n.

    Consider the sample RBRBRB.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The answer is no in the samples which matches my statement?

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

        Oh my bad, I misinterpreted your statement. Honestly you are very close to the solution, consider the case where there are only odd length blocks.

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

    You just have to add

    • The answer is no if there are no blocks of even length (unless we have only a singe block, of course, which is covered by (1))

    And it's "YES" in all other cases. You can remove (3) since it's a corollary of the rest.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      One more edge case: the answer is yes if there are no blocks of even length, but there are only $$$2$$$ blocks and one of them has length $$$1$$$ (because both vertices always start in the same big block).

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

    You can't have alternating colours with odd $$$n$$$, the array is cyclic. RBRBR is the same input as RRBRB, which isn't alternating.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hello everyone!! contest was superb. Very nice problem set by the authors.

→ Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I was trying to hack this solution during the contest — https://codeforces.net/contest/2029/submission/290747953

Can anyone tell me why this is not giving TLE for the case tc = 1e4, l = 1, r = 1e9, k = 1 sszcdjr

→ Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

rainboy orz

→ Reply
»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

C>E

→ Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

A construction similar to the one from problem D appeared at IMO 2019, problem 3. (But of course, it is a completely different problem.)

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

My solution for C:

dp[i][0] = the maximum answer up until i given that you haven't skipped any elements so far

dp[i][1] = the maximum answer up until i given that you are currently skipping elements

dp[i][2] = the maximum answer up until i given that you skipped some elements and are now back to not skipping elements

Transitions are annoying but its pretty much just casework. The final answer is max(dp[n][1],dp[n][2])

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

    and how to track how many you have skipped? I thought similar but gave up when I thought I also need to track how many we are skipping.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The decreased number of edges is 1 or 3.

      → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Got it, it is like a destruction and after a reconstruction to obtain a tree, in case when all degree can't be zero, isn't it?

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

simple code for C : 290735677

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this WA on D? I thought you just needed to get rid of cycles then it was easy

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how to solve B? I think I almost get it, yet I can't arrive at a full-fledged reasoning.

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

    replacing with a 1 doesnt change the count of 1s in s, but replacing with a 0 decreases the 1s. So if the count of 0s in r and 1s in s is same, the final bit in s (which is actually last element of r) should be 0. one more case is if count of 1s in s is just one more than the count of 0s in r, then the final element should be 1 (i.e r.back()) also as long as both zeros and 1s are there there will be atleast one adjacent different pair so we can ignore where to replace ezactly

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Note: there exists a $$$01$$$ or $$$10$$$ if and only if the binary string contains both $$$1$$$ and $$$0$$$.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a pupil coder, C is too difficult for me.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C is like 4500 rated problem... I almost gave up on it at some point :)

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Pretty sure you've overkilled it

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

    Skipped it, solved DE, and then while looking at it somehow thought "wait, this is obvious dp"

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

    every overkill solution solves something more than necessary, so i am curious, can your solution solve for a variation of this problem where instead of k increasing by 1, k increasing += b[i] where b is an array of points you get for each time your x > a[j] and j is the i'th contest you measure against? In the original problem you can think of b as an array on only 1s.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Argh, I read B's statement wrong (thought that you to replace $$$s_ks_{k + 1}$$$ with $$$r_k$$$. That makes the problem waaay more difficult :(

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

Just saw some mf sharing solutions in contest time on YouTube

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    I still haven't understood why people think videos are a reasonable way to share content that consists almost entirely of text.

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Are the downvoters cheating, or did I write something incorrect?

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

      Generally, it is not a good idea to share links to such channels. You will probably do more harm than good by giving potential cheaters an explicit location that they could look out for next time.

      However, I'm not sure where one is supposed to report such occurrences; Mike and round authors come to mind, but I don't think they can actually do anything to take channels/videos down on youtube? idk

      → Reply
»
6 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

Seems like people are quite confused about C while it has a relatively straightforward solution:

Binary search the result x, and check if you can construct a solution whose score is x.

A solution needs some prefix + some suffix. You can calculate $$$prefix[i]$$$ = score as you get to position i, $$$suffix[i]$$$ = minimum score needed, starting from i, so that the score is x. Then you can calculate $$$min_suffix[i] = min(suffix[j], j \ge i)$$$.

The answer is valid if there exists i such that $$$min_suffix[i + 2] \le init[i]$$$: e.g. we take a prefix up to i, skip some elements, then take on a suffix that brings your final score to be x.

Of course you also need to handle the edge cases where the prefix or suffix is empty.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it +27 Vote: I do not like it

    There is an even simpler solution:

    • A higher score is clearly always better, so I store $$$dp[pos][0 / 1]$$$ = max score after the first pos contests with 0 / 1 indicating whether we've skipped a segment.

    • The regular (non-skipping) transition is a typical $$$dp[i + 1][j] = dp[i][j] + \text{(score change for current rating = dp[i][j] and performance = a[i])}$$$.

    • For skipping a range, its just $$$dp[i + 1][1] = \text{best prefix value of } dp[i][0]$$$ :)

    Code — 290717116

    I'm actually surprised so many people bricked on this problem, to me it feels like an extremely standard problem I'd expect to see in an Atcoder Beginner contest D or E.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You don't need a fenwick tree in problem C, just maintain a prefix sum array and update it when adding number, and then you get a linear solution!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wtf is E? Something to do with least primes?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    You're on the right track.

    Hint 1
    Hint 2
    Hint 3
    Hint 4

    Code — 290740094

    → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Check out neal's solution to problem C, you won't believe how simple it is.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

C can be solved with 3 priority queues, without dp or binary search.

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

    explain please

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      We have 3 states: before interval, in interval, after interval.
      Loop over the array with maintaining 3 max PQ (one for each state),
      in each iteration we do the following:
      1) update the top of the after interval PQ. (interval has been closed)
      2) push the top of the before interval PQ to the in interval PQ. (open an interval)
      3) update the top of the before interval PQ. (interval has not been opened yet)
      4) push the top of the in interval PQ to the after interval PQ. (close an interval)
      Finally, the answer is the top of the after interval PQ.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Your solution is exactly the same as dp from editorial. Priority queues are not needed, you can simply store value of each state in variables.

        → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good One

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone knows what's special about problem D test case 21?

I'm getting TLE and cannot reproduce it on my pc by generating random test cases

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

    From what I can see in the partial input data, I guess that it's a huge star-shaped graph centered on vertex $$$30954$$$, that is, its edges are denoted as: $$$E = \{ (30954, i); 1 \le i \le 100000, i \ne 30954 \}$$$.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

Glad to win one ninth of a T-shirt!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for F, let $$$s$$$ be the parity of the lengths of the runs of the color which doesn't appear in only groups of $$$1$$$ (WLOG, suppose it is red). I deluded myself into thinking about the problem as if every time you cross a blue, you always start at the left end of the corresponding red segment, for which I think the answer to the problem depends on whether $$$s$$$ equals any of its cyclic shifts

why am I regarded 🤣

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to understand why and how https://codeforces.net/contest/2029/submission/290751375 has TLE?

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i reached candidate master at this round ,finally div1

→ Reply
»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

nowadays problem setters gave us notes below the problem statement to confuse us even more hahahahaha

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain dp implementation of C. thankyou in advance .

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it 
for _ in range(int(input())):
    n = int(input())
    
    def f(a, x):
        return a + (a < x) - (a > x)
    
    dp = [0, -n, -n]
    for x in map(int, input().split()):
        dp[2] = max(f(dp[1], x), f(dp[2], x))
        dp[1] = max(dp[1], dp[0])
        dp[0] = f(dp[0], x)

    print(max(dp[1], dp[2]))

i did not understand f(a,x) it should return a + (a>x) — (a<x) can someone help

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    That code uses some little-known feature of Python that bool is a subclass of int -- you can see isinstance(True, int) returns True. As a corollary to it, when a bool value is used in an arithmetic expression, True is converted to 1, and False is converted to 0. For example, 5 + True is 6 (!).

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

    variable names are reversed here compared to the problem statement. Swap a and x in the function f and it should make sense.

    → Reply
»
6 weeks ago, # |
  Vote: I like it -48 Vote: I do not like it

is tourist dead?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you very much for the contest.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://github.com/2105169/985_C_in_Codeforces_169_slfajlss-/tree/main

Where problem in my code? C.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Plagiarism Flag Clarification for Problem 2029B Solution #290758150

Hello Codeforces Team,

I recently received a notification that my solution (290758150) for including solutions from users such as [user:ssssssssssssss_11111, bdyby00, coderlazy5, and many others. However, I want to clarify that I did not engage in any form of plagiarism.

My solution is based on simple stack over flow tutorials any one with simple programming language can write this(https://stackoverflow.com/questions/31463092/using-namespace-std-and-vectors)

The problem itself was straightforward, and due to its simplicity, I believe it’s possible that many users might have come up with similar solutions. Despite this, I noticed that several of the flagged solutions, including mine, differ in various aspects. Given these differences, I’m unsure why my code was flagged.

I kindly request that the Codeforces team re-examine this issue. I am committed to maintaining the integrity of the platform and would like any misunderstandings clarified. Thank you for your time and assistance with this matter.

Thank You :))

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one help me with this problem https://codeforces.net/edu/course/2/lesson/7/1/practice/contest/289390/problem/B my solution is https://codeforces.net/edu/course/2/lesson/7/1/practice/contest/289390/submission/290874456 it may help me to learn thanks in advance.

→ Reply
»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

will i be contacted from recraftai if i had filled the form before the round and have got +79 rating points at the round?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Is the red text in I a correction of a constraint that was originally written higher or just emphasis?

→ Reply