arvindf232's blog

Codeforces Round #822 (Div. 2)
By arvindf232, history, 8 months ago, In English

UPD: The round has been rescheduled to a different time due to a clash with a CodeChef contest

Hello CodeForces!

Me, happy.potato and __jk__ are excited to invite you to participate in Codeforces Round 822 (Div. 2). It will start at Sep/23/2022 15:05 (Moscow time). The round will be rated for everyone with less than 2100 rating. You have 2 hours to solve 6 problems. Please note the unusual start time.

We would like to take this opportunity to thank everyone who have contributed to our round:

We look forward to seeing you on the leaderboard!

UPD: Score Distribution: 500 — 750 — 1250 — 2000 — 2250 — 3250

UPD2: Editorial

UPD3: Winners!

Div 1 + 2:

  1. GOI_Official
  2. Um_nik
  3. SolarFlea
  4. Second_Brave_Niuniu
  5. hitonanode

Official:

  1. GOI_Official
  2. SolarFlea
  3. Second_Brave_Niuniu
  4. Sand_Emperor
  5. steven14414
  • Vote: I like it
  • +370
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +96 Vote: I do not like it

As a co-author, the problems are nice and I recommend everyone to join this contest!

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

    As another co-author, I can assure that problems are great and I also recommend everyone to join!!

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

      As a tester and not a co-author, the problemset is very amazing and you should join the contest!

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it -56 Vote: I do not like it

        As a participant and not a co-author or tester, i will surely join the contest.

        Why are u downvoting for just no reason.

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

          If you ever ask why people are downvoting you for no reason, just know that you'll get a shit ton of additional downvotes just for that

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

        As another tester, I agree with you!

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

        As a participant and not a co-author or a tester, i highly recommend this amazing contest with those amazing problemes

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

      My translator is so bad that it translates great problems into big problems.LOL

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

Ooh, a very early announcement. This should be good news.

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

Hopefully I will solve two problem this time. All the Best to everyone .

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

Yaay

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

Very excited to participate, gl everybody

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

My rating is 822. SolarFlea

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

CodeChef Lunchtime is clashing with this round. After a long time, CodeChef is having a rated contest for div 1. I think many of us want to participate in both the contests so could you change the date or timings of the round (if possible)?
arvindf232 happy.potato __jk__

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

As a tester... I have nothing to say other than good luck.

-QuangBuiCP

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

    I like Takina more than Chisato. BTW I wonder what you study at the Institute of Sexology?

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As an Unrated... I will make sure to make me rated.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in last div 2, i did question 1 very quickly,i figured out question 2 quickly 2 and coded it but wasted my 1 hour just coz i had a wrong value assigned to a variable, made wrong submissions many times, and question three which was very easy i could not figure it out coz i wasted my energy alot on the second one. this is me in literally every contest and im even loosing hope now.can someone please guide me how to fix these issues, i can never maintain pupil due to these sillly mistakes.

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

    you made a mistake, and you will not do it again. Im sure that there a finite amount of doable mistakes, so just attend more contests!

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

Hong Kong Round! Support!

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

-

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

Can you guys please reschedule this round little bit as the contest time is intersecting codechef lunchtime contest(If possible) . Because many of us will willingly want to participate in both contests. But if the contest time collides it is hard to choose one contest Between them. Please "_|_"

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

As a participant, I will participate in this competition to improve my strength

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

I hope reach CM after this contest ಥ⁠‿⁠ಥ

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

    i love your graph haha

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

      -100 +100 -100 +100 :'(

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

        any tips for me to reach specialist , other than fast ABC

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

          Practice 1500+ rated problems

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

            I practice 1200-1500, I thought that would help me reach specialist because I struggle with div. 2c 2/5 times during the contest, am I doing it wrong?

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

              yes u should always pratice problems of higher rating than your current one.So donot waste time in 1200 go for 1400+ ones.

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

    Wishing you luck :)

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

lucky

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

Plz keep the original starting time but re-schedule to a different day

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

    No way, i think it's much better than before, but each person's experience depends on the local time zone, which is something that cannot be done perfectly ^-^

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

      In my opinion, time zone is not the main problem. What matters more is that it's preponed... And I happen to be one of the unlucky guys who missed this round because of that...

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

Oh,Very excited to participate .

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Alright, time to comeback and on my way back to 1k4 after I throw a lot of contests down the drain

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets hope ill mange too make 2 problems :))

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

The contest has been preponed. Do not miss it! All the best everyone!

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

Respect++ For respecting codechef :)

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope get delta >= 5

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone.

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

sad for west coast :’(

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

Just noticed the contest was preponed.

I think postpone is far better than prepone. Many people registered the contest and back online on the time the contest was scheduled. prepone could make them miss the contest, but postpone won't.

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

    I think sending a mail to everyone who registered might be a good idea to avoid that.

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

As a uni student who would have been unable to attend this contest due to it being during my classes, I am very grateful for this opportunity.

(Yes it would be 5am in my local time, but I literally don't care.)

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

Can you help us ? here -- > World War III will begin D:

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

Why is cf accomodating for codechef and not the other way around?

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

    Maybe codechef have more money.

    And money talks

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

    Because codeforces cares for us

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

    Codechef had postponed its previous contest from 21 to 22 Sep. So they are like its your turn now.

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

    CodeChef is holding rated round for div1 after almost a month thus many don't want to skip it. If no contest accommodates it think many will end up giving CodeChef round.

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

As someone waking up at 4:30 to do this contest, please let me solve ABCD.

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

    Only you have to solve the problem. Only way someone else can let you solve a question by giving hints or telling solution which is cheating so you are going to cheat

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

codeforces are very kind for programmer who rescheduled their contest timing because of codechef contest time at same time.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CodeChef contest is 3.5 hours long why??

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

20:05-22:05 UTC+8 is friendly to Chinese!

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

finally, the contest at 9 pm

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

3250.

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

I like this Score Distribution : 500 — 750 — 1250 so much

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

I hope I become expert in this contest... :)

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest has been preponed ...Nice!

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

UPD: Resolved thanks!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My calendar didn't reflect the time update, I am wondering whether I registered from a wrong source. If anybody's calendar works correctly pls let me know, thanks!

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

I happen to be one of the unlucky guys who missed this round because of the prepone. I came online just to find that the contest has already started... Perhaps changing the date might be a better idea than preponing in such short notice?

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

Wrong answer on pretest 1,Wrong answer on pretest 2,wrong answer on test 1,runtime error,Time limit exceeded,Memory limit exceeded,Compilation error.I loves wrong and error,I love bad rating.

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

What the hell....I missed this contest :(

Didn't even received a mail about time change.

congratulations to all who will get positive delta due to this time change, not in my wildest thought had I even thought this way of improving rating. I hear "CHECKMATE" from admin.

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

    I literally did AB first and ate dinner then do C later only because of the time change TT. If it wasn't for the time change then maybe i could finish C quick enough:(

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

      I don't know bro. Maybe we need to practice for these time changes as well here.

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

Why is Codeforces such busy today? Even m1,m2,m3 are sometimes busy. But this contest is surely pretty good.

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

Someone solved E in 3 min. That is insane

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

It was a nice contest. i am waiting for a day when i will be able to solve div2 D.

is there anyone who can tell me how to approach problem D?

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    I used two pointers approach.

    Idea
    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is what i was thinking during the whole contest.

      But wasn't able to implement it.

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

        My solution lacks the optimization to not recalculate the whole route from k to the last l I checked, so it TLE's, but the idea in general is the same, so my implementation isn't correct either. welps

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

      Alex.Svanidze I did something similar but didn't TLE. I didn't submit it in the contest thinking it'll TLE. 173232461

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

        I guess me updating the values to zero changed it? lol, dunno, didn't really dive into your code, it looks quite similar, but there might be a significant one-liner difference

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

        Looking at it now, there is a huge difference. You check for the left and right separately, for just once. I go with loops until I reach a non-valid point. If the testcase needs to run on zig-zag, I will recalculate the whole segment between l-r and my solution will go up to n^2, yours will never exceed linear imo.

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

          I'm not quite sure whether it'll exceed linear or not. But if I'll divide the slimes into groups as mentioned in the editorial then I can be sure that it'll be linear because we on 2 checks at least one pointer will move, if it'll not move then it's impossible. There is no overhead of reiterating on the already seen indices. But in case of my solution without groups we are reiterating on some sets on points again and again.

          → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do c?

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? I was able to do recursive DP but that was MLE.

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

How to solve E?

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

    I solved it like this. I'm not entirely sure why this worked. 173206034

    Edit: See Shisuko's post below. That's why this worked.

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

    For this proof, we assume that the matrix is $$$0$$$-indexed, i.e. $$$0 \leq r < n$$$ and $$$0 \leq c < n$$$. Also, note that this is exactly the same as OleschY's solution shown above with the really nice visual diagram. So just read this if you're interested in a proof of correctness haha

    Note that the condition is equivalent to saying a[r1][c1] - a[r1][c2] != a[r2][c1] - a[r2][c2] (mod n). Let d_{c1, c2}(r) = (a[r][c1] - a[r][c2]) mod n; for a fixed (c1, c2), we want d_{c1, c2} to be distinct for different input values of r. But now we can see that we are very limited---there are n possible values of r, but also n possible different outputs of the function. So we want this d_{c1, c2} to be some permutation of 0 to n-1.

    Let's set the matrix such that a[r][c] - a[r][c+1] = r always holds. Then, note that this implies (by induction or whatever) that d_{c1, c2}(r) = (c2 - c1) * r mod n. But if (c1, c2) are fixed, then (c2 - c1) is just some nonzero constant, and because n is prime, we know that d: r -> kr mod n is a permutation for any nonzero k.

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

In problem C, why can't we just choose k=1 every time? S must contain a number multiple of k=1 and this/any number can therefore be removed with cost k=1.

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

    If we dont have to remove 2 then the smallest factor of 1 will be 2.

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

    You are required to remove the smallest multiple.

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

    u can only remove smallest multiple of k.So if 2 is there in T then if u select 1 twice then the second time 2 will also be removed.Which is wrong.

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

      Thank you! So we can just delete all multiples up-to a multiple that is in the target T. example if S={1,2,3,4} T={3} with k=1 we can delete just {1,2} because the smallest multiple remaining is 3 and that has to stay in T.

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

    what if lowest multiple of 1 needs to remain?

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

    you delete smallest multiple of K present in S.

    → Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

Problem D has the same idea with Circle Eating in Codechef. But in codechef contest, only 8 people get AC in contest, otherwise there are over one thousand people pass pretests in Codeforces Contest! It's amazing.

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

    How to solve D?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

      If I don't misunderstand the meaning of problem, you can see the editorial in Codechef to get the main idea.

      P.S. update the link of editorial. P.S.2 it seam the solution of the two problems are quite different...

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

        Editorial is a Pro feature now on Codechef............

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

    This contest should be unrated!

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much for problem E! I (don't) wish you good health, love, high esteem and respect from loved ones, achieving your dreams to infinity, happy life, have magical moments and memories, and obtain what you really want, because that is the only way to fulfillment, realization and happiness!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is My Submission to D failing test case 10 :( . Can anyone explain? Thank you!

Code : 173206067

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did Problem D just 15 seconds after the contest :(

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why Codeforces is really laggy today, even m1.codeforces. By the way, can somebody tell me a case where I got the wrong answer on Problem D. I got WA on 3rd pretest. Thanks alot <3 <3 <3 Here is my submission: 173222229

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my code of problem D wrong answer on Test #3? Can someone tell me? Thanks!

173220801

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

Dear MikeMirzayanov, Why are we penalized with a -50 for resubmission when the site goes down? I got -150 due to unwanted resubmission when the site went down.

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

    Same here, I have submitted 4 exactly identical codes due to CF lagging and got -150 for that.

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

    Same with me !!

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

    Same, although I've submitted identical codes, I got -100.

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

Can anyone give me a failing case for https://codeforces.com/contest/1734/submission/173197473

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

Good round but I didn't manage to write D:( can someone please give the failing testcase? I will be glad if someone could help me

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

Dumbass me trying to use Fenwick tree for D...

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

Because of the Website issues, In problem B the same code got judged twice and I got -100 so is there any solution or anyone got the same problem? 173177338

173176654

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

    Yes, I faced the same issue while submitting solution for problem A. it got submitted twice.

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

    Same, i got -150 for unwanted resubmission of B.

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

    I faced the same thing while submitting a I got 8 WA in 1 second.

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

      sad:'( I hope this issue will be solved ISA

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

i've done the solution for D and it passed the sample tests but i ran out of time and couldn't submit , i hope it gets WA after the system tests because i'd be so mad if it got AC

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

    How you did C ?

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

      I tried to do something like this but it was brute:

      #include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin>>t;
    
    while(t--){
        int x,l,ans=0;
        cin>>x;
        
        string s;
        cin>>s;
        
        l=s.length();
        
        vector<int>v(x+1,0),visited(x+1,0);
        
        for(int i=0;i<l;i++){
            if(s[i]=='1'){
                v[i+1]=1;
            }
        }
        
        for(int k=1;k<=x;k++){
            if(v[k])continue;
            int i=1;
            while(!v[k*i]&& i*k<=x){
                if(visited[k*i])i++;
                else {ans+=k;visited[k*i]=1;i++;}
            }
        }
        
        cout<<ans<<endl;
        
    }

    return 0;
}
      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      it is the same idea of sieve of eratosthenes , iterate over the string and if the current number (let it be num) needs to be deleted the the i should iterate over the multiples of that number (let it be j) and take the minimum cost to delete that j which is min(mnCost[j] , num) i should break when j is multiple of num but j cannot be deleted from the set as i won't be able to do this deleting operation using this num in the future look at my code for more clarification

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

        It feels like C was much easier than B, it was so direct question...

        I felt like some data in B was missing they should have mentioned if the current room where we have reached is having torch than it will be counted too.

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

          Yes it should have been mentioned, but you just have to see the test case and you will understand that the room is counted too

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

https://youtu.be/bOizr3O0elA

This channel posted correct solutions of A & B during the contest and many participants would have seen this. Due to this, the rankings would be skewed and would lead to an unfair contest, please do something regarding this.

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

    Plag check wouldn't be reliable in problem A & B to eliminate those who copied either. Probably making it unrated should be considered as those videos have 500+ views.

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

      Eh bad for you that the video was published after the contest

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

estimated rating of C?

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

    maybe 1100-1300

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

      understandable, did u know why your E works before submitting?

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

        Nah, I do not have proof of why it works, I am not sure, even now why it is working

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

          then how did it strike u that that could be the solution lol?

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

            Actually i dry run this on sample test cases and it is working fine, but I do not have the exact idea why it works for every test case. it is a kind of hit and trial.

            → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can this submission for problem F be hacked?

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

Hi, can someone help me understand why this submission gives TLE, isn't the complexity nlogn? https://codeforces.com/contest/1734/submission/173206247 Got it. It was due to resizing on 10^6 every time.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a shit and I didn't solve C,though C is very easy.

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

    Bro what will be the expected rating of that question I did solved it in last minute

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

      ig it would be 1200-1300 since its looks like typical div2b and too many people solved it lol maybe even 1100

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

This Ame-wiki guy were in my room-213..

when I was going to see his/her code at contest time. I was shocked!! Just try to unserstand what those line indicate.... Submissions are:

1734A

1734B

1734C

1734E

I think to makes code unreadable to others is nothing but scam..

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

I get very angry because of the time of this round.

I turned on my computer at 22:15(utc+8) and it is already over.

It's a good idea to put off it. But U chose to make it earlier. That's one of the worst decisions U can make.

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

    it's unrated for you, what's your problem?!

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

      It doesn't matter. I don't care whether it is rated. I only want to enjoy the process of competing. But I can't today.

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

        There's an option which is virtual participation, You can do it any time in the year !!!!!!

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

    I thought someone would comfort me. But just downvotes.

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

    Well if you always stay up to participate in a competition it can be bad. I think the time of this round is very good. 22:15 is too late.

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it -45 Vote: I do not like it

:/

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

nice problems! orz arvindf232, happy.potato and __jk__

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

why the fuck am I missing D by an inch every single contest !!!

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

    same. I didn't submit my D in contest thinking it'll TLE, now submitting the same gave me AC.

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

      D is basically two pointers with some painful implementation

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

May I ask why the data range of problem C is $$$10 ^ 6$$$, but $$$O(N \sqrt{N})$$$ time complexity can pass? I can't understand it.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did this brute force code get AC after the system test? Is it wrong or right?

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

    I don't think that is brute force cuz it's pretty same as my code and I can prove it :vv

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

      I optimized this code and proved the new one was right, so I think this is brute force. So how to prove this code is right? Thanks a lot.

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

        The code is way too long and complicated so I just view it fast and get the main idea (hope it not gone wrong :vv)

        Just start from k and then go left until got a better choice than the current then update to that point, if it invalid then do the same to the right and if it invalid then print no otherwise if get to 0 or n + 1 then yes

        (Sorry for my bad English and knowledge :<<)

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

          Oh, I know its correctness, but I wonder if it's time complexity is right (Why didn't it get TLE?).

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

            Because you start at k and then go for a better choice, if it exist on the left then update if not check the right and update (pretty same as 2 pointers but instead of pointing from the outer to k now we spread from k to the outer) so the time complexity is just O(n)

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

              But while it go to the left, the right also cost time. If there is a situation that every time it go to the left one step and need to check the right in $$$\mathcal O(n)$$$ time, it will cost $$$\mathcal O(n^2)$$$ time.

              (Sorry to my poor English)

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

                No, just go to the left and if the slime can get bigger then update l (considered as the id of the left) and the slime, if the slime got negative then go to the right then update r (considered as the id of the right) and the slime

                You just update when you meet the case that you got a bigger slime or negative slime when you go all the way to the left or right so it cost only linear time

                → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I view the 2839th token of problem D test 3?

Or could someone tell me where's wrong in my solution :(

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

    keep track of each testcase and print the respective testcase in string.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please check why my code is failing on pretest 3 173225741

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

Why my code of problem D wrong answer on Test #3 [60th token] ? Can someone tell me? Thanks! https://codeforces.com/contest/1734/submission/173229017

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone explain me the time complexity of problem C? What will be the expression in big O notation?

I thought it will give TLE but it didn't ╰(*°▽°*)╯

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D video Editorial

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a great round

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

Why my solution of C is getting TLE. Can anyone tell me please? Isn't it supposed to pass?

https://codeforces.com/submissions/tanvir942316

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

    It might be because you are doing too much map access, I once got TLE on a problem because I used map for frequency instead of a using normal array and set the elements of the array to zeros.

    anyway I changed map into array, and I moved the main array to global variables because your array size was only $$$2*10^5$$$ but it reached $$$10^6$$$ in the problem

    Your modified solution

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Estimated rating of D anyone?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

PLS write 2 days/ 1 contest

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't play well in this contest, so I hope I can cheer up in the next consest. ^_^

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

I’m leavin' my name here 'cause it’s the first contest I participated in. And I even got a rating rise!

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

Is it confirmed that GOI_Official is an individual participant? I find it quite incredible that they solved ABCDE all within a span of fifteen minutes. This includes a submission at 9m12s for D (WA test 3), followed by the first submission for C at 9m50s (AC) and then a second submission for D (AC) at 10m41s. This really gives me the impression that it likely involved at least two programmers coding in parallel.

There is also a slight inconsistency in their submission formatting. Submissions for A and D (173165060 173171017 173172113) include a header with the problem names and links, but these are missing in the submissions for B, C, E, and F (173169227 173171420 173175699 173185632). All submissions have the following two lines:

//author: wuge with noi2022 cu
//https://www.luogu.com.cn/team/48234

I would guess that noi2022 refers to a National Olympiad of Informatics (CU might be the institution?), which generally involves a team (wuge might be the team name?), and the link below (which seems to be inaccessible in my region) has "team" in its url.

If it is the case that this user is actually representing a team, where different members of the team were able to code in parallel, I don't think this is within contest regulations (which required the user to register "as an individual participant"), so they should not be included in the official standings then. Of course, I don't know for sure that the user represents a team, but I think this should be investigated.

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

    In fact Wuge seems to be a CPer's name,And in NOI2022,he actually got the bronze medal.

    I agree on your guessing,I think two CPers worked together,and one solved AD,another solved BCEF.

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

    U R probably right. It's imposisible to code at such a speed.

    They may share something, including read() and main() and the name of function meyi(). But A&D have a header. That is different. The time is also strange.

    GOI is a team. They hold a contest in luogu(a famous OJ in China), and it turned out to be a mess.

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

    Luogu is an OJ in China, and that url is a team of it.NOI is the Olympaid contest of China (Its whole appellation is National Olympaid in Informatics.) and cu is the symbol of copper, it means copper medal.

    That code and the time is quite strange, but the code mentioned a code editor called CP editor. There are also some strange variable names like shaya and wugecu. They look like Chinese Pinyin. Is that the editor's feature?

    Also, CP means couple. So is CP editor an editor that allow two persons code together? I think it is NOT individual, too.

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

Why do we care for codechef:(

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can solve problems A, B and C in div 2 most of the times now. Any suggestions on how can I solve problem D?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why not unrated?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

asghar dar kamin ast!!!!! asghar is lurking!!!!!! Асгар в бегах!!!!!!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, why does my submission give TLE? 173310975

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I am kinda stuck on Problem C with my solution.

My Approach:

Take two sets A and B, both maintains the numbers to be deleted from the set.

Set A is ordered and B is unordered.

Now for each element of A say X, first I find its smallest possible multiple in B say M. And then check from X to M, I check whether the multiples in b/w are given as 0 or 1 in the string.

If it is a 1 somewhere then I take the next element from A.

If no 1 is found, then I delete all the possible multiples of X starting from M and the same is done till either we reach the end of A or B becomes empty.

This approach somehow is failing on 512th number on Test Case 2.

I am not able to figure out what exactly is going wrong.

173315698

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not copy any solution and then too system tells that I copied and my rating did not increase, what should I do now?

→ Reply