cry's blog

Codeforces Round 979 (Div. 2)
By cry, 2 months ago, In English

Haiii Codeforces ^_^

Note the unusual starting time. This round starts 30 minutes before the standard starting time.

vgoofficial and I are extremely excited to invite you to Codeforces Round 979 (Div. 2) on Oct/19/2024 17:05 (Moscow time). You will be given 7 problems and 2 hours and 15 minutes to solve them. One problem will be split into two subtasks. This round will be rated for all participants with rating below 2100.

This round is based on... absolutely nothing.

We would like to mention the following individuals for making the contest possible:

Score Distribution: $$$250 - 500 - 1000 - 1500 - 2000 - 2500 - (3000 + 1500)$$$

UPD: Editorial

  • Vote: I like it
  • +417
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +62 Vote: I do not like it

As an author, I hope you like orangutans.

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

As a tester, I can confirm that the coordinator satyam343 coordinated.

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

    As a tester, I can confirm that problems have non-negative no of test cases.

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

    As a contestant, I can confirm that being a newbie and giving contests is sooooo damn hard but i solved a problem on my first contest, hail yeah!I feel like flying man.

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

Rating distribution?

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

Thanks for the perfect contest.

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

    unusual starting time so people have time to eat lunch before meta hacker cup

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

      We code on a full stomach — we code with full force!

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

    and score distrib out now

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

Great way to practice my regional ICPC round, which starts only 7 hours after this round. Good luck everyone :)

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

    There's meta hacker cup too just 1 hour after it ends

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

      Oh wow, love it but I'll have to stay awake till 3AM in my time zone and compete in ICPC at 7AM. Not so sure what to do...

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

    Factually speaking, it's not "regional" but "provincial". At any rate, good luck.

    Man, I miss the good old days...

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

satyam round.i am cooked :)

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

as a participant, good luck to all :)

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

I bet this round is based on Honkai: Star Rail :D

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

Let's hope my rating won't decrease this time

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

If I don't reach expert level in this round m gay

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

after getting destroyed by educational round hoping to get good +ve in this round gonna grind hard in VCs and problemset

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

    I was getting to green which I'm actually dying for and then the system tests on B destroyed me

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

      nt bro u will reach green in next div2

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

        thanks good luck for you too, this time if I managed to to solve a b c I will not look at any thing else and I will just check all my submissions because I need to reach pupil for my well-being

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

As a tester, i think orangutans are very beautiful.

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

uwu owo round

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

Are you impressed?

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

As a first-time tester, I learned a lot from testing this round!

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

    How to become a tester $$$??$$$

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

The best part of a cry round being announced is the emoji :) (and of course the round, cry rounds are the best :D)

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

I think I will solve 3-4 problems..

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

In problem B, why cant we take the first x biggest numbers, subtract the minimum, then add it to the answer?

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

Vote me down, if you think I will return to the specialist after this round.

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

Wow, 250 score problem.

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

as a participant, i am monke.

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

As a participant, I confirm that all the problems have inputs and outputs.

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

hope that I could become expert :-D

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

So many IM's, M's and GM's are testing this round :)

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

as a participant, good luck to all :)

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

good luck to all:)

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

Another cry round!

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

What does "ORZ" mean?

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

    A person kneeling on the ground

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

    U can use this word like "sto somebody orz",it looks like two persons are worshipping somebody.Isn't it fun?

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

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

genuine question — how are scores for problems chosen? does the score indicate difficulty of problems with respect to each other?

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

Finally, a cry contest!

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

How to become a tester?

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

Pookie Gorila... xd

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

Is it rated? I AK IOI.

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

seems kind of unfair that orangutans can't participate in the contest due to being too high rated

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

As a monkey tester, I have made sure no orangutan attacks you during the contest.

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

I'm so happy I can take the test on my birthday! It would be better if I pass as many as possible...

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

This is going to be a great Saturday!

First ABC contest on AtCoder, then Codeforces round in 25 minutes, then Meta Hacker Cup Round 2 in 40 minutes.

In total it's almost 7 hours of coding. Good luck to everyone!

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

    This comment literally gave me goosebumps. Let's go....

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

testuwuwuwuers

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

    If I can't reach Expert in this round, I'll play Distorted Fate AT16 until my accuracy reach 99%

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

      Wish you have fun :)

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

        lol I'm so unfortunate. But I've just reached 99.67% for the new AT16 instead, hope the both challenges are equivalent on difficulty

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

I have never solved E before, and I hope to solve E this time :D

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

Vladosiya fan = me

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

I have registered for tomorrow's div1, what if I lose rating points in this one and become expert, will I be able to give both div1 and div2 simultaneously tomorrow?

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

1 WA is 20% of problem A. is this not just bad scoring? why not multiply everything by 2?

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

    Maybe becase problem A is easier than usual div2 problem A's.

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

    $$$1$$$ WA is $$$20\%$$$, and most people will resubmit it (As it's the easiest problem). That's another $$$20\%$$$.

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

As a participant. I'm going to drink and drive if I don't reach 1000 in this contest.

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

So this is a div3 contest! Did everyone feel the same?

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

OMG i don't know what is wrong with my C

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

    us

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

    you start from the end to the beginning and the edge case was when the first number is 1, so if alice reaches the last 2 numbers you check if the first one is 1 too, because 1|0 is the same as 0|1

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

    same, wasted 1.5 hours figuring out what was wrong

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

    think greedy , just 2 cases 1. if 2 consecutive ones then Alice will put an OR between them 2. else if any of first or last is a 1 then Alice will put an OR next and before it respectively.

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

    OMG i thought we had to put or's and and's sequentially!! i did not read the test cases's explaination.

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

    for me it's B cost me ~ 90 min to figure what's wrong in my solution... and a tons of WA (painful as hell)

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

Bruh Does D need that much coding? I got the idea of the solution more than 1 hour ago, but still didn't finish implementing it.

segment tree to get min max range queries. every R that has L on left and right is where a new loop starts. check if minimum of a loop is lower than the maximum of the loop before it and it is then it's not possible to make non decreasing, but I didn't know how to store the results easily.

I had to create sets to min and max of each loop and update them with each query, but I was slow in doing this. was there an easier way? or am I just wrong about my idea

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

    Same idea

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

    p does not change so precalculate d[i] = max(p[1],..,p[i]).

    if S[i]=='L' and S[i+1]='R' then it is only possible to sort if d[i]<=i.

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

    On the permutation, only the intervals $$$[L,R]$$$ such that $$$\min(p_L,p_{L+1},\cdots,p_R)=L$$$ and $$$\max(p_L,p_{L+1},\cdots,p_R)=R$$$ matter.

    Meanwhile, on the string, only the intervals $$$[L,R]$$$ such that $$$s_L s_{L+1} \cdots s_R = \mathtt{"RRR}\cdots\mathtt{RRLL}\cdots\mathtt{LLL"}$$$ matter.

    I hope you can figure out the rest yourself.

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

    I had pretty much the same idea: Get the positions of 'LR' and find the minimum/maximum between such positions (using segment tree) and check if minimum = 'L' index and maximum = next 'L' index. This was indeed an implementation-heavy problem and required storing/deleting information into sets.

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

    same, I was searching for another idea because I knew I couldnt implement this one (also you have to use binary search to find which segment you are changing and there are also some cases)

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

    We should have the similar idea, and I spent a lot of time implementing it. But after that I realized there exists a much easier way, we just need to keep track of the min/max value on the left/right side of each LR, and since the array itself won't change, it can be done quite easily with some precalc...

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

      damn that would have made it much easier

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

    i dont use sets or segment tree, its can be simplified alot

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

Animated Video Editorial for the Contest! The video editorial has problems [A-F].

Link: https://youtu.be/CpSIK4YPi00

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

today C is extremely familiar with this 1988B - Make Majority

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

    How so? I believe it is quite different.

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

      both problem can be solved by if else a few cases and edge cases. i.e. find '11' or if start and end with 1 or a few cases...

      In my perspective, both problem have 1 same alternative solution: Count 1 and groups of consecutive 0, then compare them to have the final result.

      I copied my own code and change the last condition and AC.

      To make C exactly like 1988B, make Bob go first instead of Alice and n>=2 in both problems, here you go.

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

        Except implementation is not the only part of solving this problem.I’m sure nobody had trouble implementing the problem as much as they had trouble seeing the relevant observations. And I have no idea what you’re talking about regarding having Bob start because that’s definitely not the same problem. Just because having 1’s at the beginning or end is relevant to both problems doesn’t make them “very similar”

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

          ok I'm just being naive... I apologize.

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

can anyone share their solution for D?

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

    Consider positions where we have LR in the string. They basically split string into two independent segments that must be good: sortable and in the correct position. Keep segments in a set for splitting\merging, check if a segment [l; r] is good by querying min and max on it, min should be equal to l, max to r.

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

      I see. So, if I may ask, how did you handle the min max queries?

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

    a string of $$$L, R$$$ is good if and only if for any pair of adjacent $$$LR$$$ to the left of $$$L$$$ every number is > than every number to the right of $$$R$$$.

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

    if $$$s_i = L$$$ and $$$s_{i+1} = R$$$, you can't swap them which means that the subarray $$$[1,i]$$$ should be a permutation of length $$$i$$$. you can check this using XOR hashing and storing the invalid positions into a set and the answer should be YES if the set is empty

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

      Gotcha. So, in terms of implementation, it is kinda similar to the C2 from a few contests ago, right?

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

        IDK which problem ur talking about but this is the implementation I did

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

        You can see my implementation too,i didnt use anything fancy.

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

        as someone who failed to implement the C2 from a few rounds ago, and managed to implement this one, i think it's much simpler, and you can check my solution for details. You don't need sets or segment tree at all, and it actually is kinda clean if you do it properly.

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

    This is how I did it. This is the 1st time I solved a D problem in contest :)

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

    I am so proud of my submission 286812781. Though it gave me 4 WA's

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

Huge difficulty gap in C to D ? or skill issue

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

Hey, for today's D I keep getting TLE, my idea is slightly different from the intended but the logic is the same, could someone spot the mistake/correct me, I do not think my constant factor is THAT BIG: TLE CODE

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

My submission for E (286816083) does a very weird thing. When I run all samples together, it gives the right answer for the first sample and wrong answers for all subsequent samples.

BUT if I run every sample individually, it gives the right answer for each. I want to kms because I believe I have the right approach but cannot debug this bullshit runtime error.

E is a beautiful task though.

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

    I'd be grateful if someone can point out what undefined behavior in my code causes this torturous semantic error

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

      you initialize new variable mx in the for loop instead of updating existing one

      to expand: ll mx=min(mx, ct[i]) uses uninitialized value of mx, that's why you get inconsistent output. I found this by compiling your code with clang -fsanitize=memory which when running the program points out uses of uninitialized values

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

On problem B, my O(n) solution time limit exceeded when I used PyPy (https://mirror.codeforces.com/contest/2030/submission/286728378) and got accepted when I switched to Python (https://mirror.codeforces.com/contest/2030/submission/286730019). I've encountered this problem before, but never during a contest (got -50 pts because of this). Usually, PyPy is faster, so when should I use PyPy, and when should I use Python?

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

    fix the link, I can't read your submission

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

      that's because the contest hasn't been judged yet — I think the same is happening to other links as well

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

    Strings are a bit weird in pypy. Never use += since it is not appending to that string but creating a new string making it O(n).

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

thanks for helping me understand the meaning of cry once again :)

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

Nice contest. Loved the thrill of solving D with last 4 mins left.

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

great problemset.

nice problem D.

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

every time I enter a div 2 contest except the educational ones I regret it so much because of problems like B I couldn't solve C but at least it's not guessing problem like B why these kind of problem is only here in codeforces div 2 and not anywhere else on earth

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

    it has a pretty simple proof tho

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

      you need to guess the answer and then proof it I prefer 4000 rated problem in div 2 B instead of this one

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

        yeah, i see your point. But pattern recognition/deduction is also a constructive skill no?

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

          I thought f(t) was the number of subsequences that included exactly one zero and any number of ones I just realized it's just zeros

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

    I don't even guess but it cost me 2WA 1TLE to complete the problem (I brute force all the way to see the 1 "1" is optimal)

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

    But the problem B change in the middle of the contest really mess with my mind (prolly cost me ~ 15 minutes of confusing and get back to track). Also I'm late 20 min because of my own careless...

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

    its a simple observation, not guessing at all

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

      today I read B and C completely wrong that's why I was frustrated but it's my fault yeah you are right it's not guessing

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

Partial solutions:

A: Put min and max together therefore from i = 2 to i = n. Max(i) — Min(i) is max of array minus min of arrray. Answer is (max(arr) — min(arr))*size(arr) — 1).

B:

Answer: put one 1 anywhere in binary array. (I put in front).

This is because half of all subsequences contain that 1, the other half do not(including the empty subsequence). Therefore, the oneness of the array is |half of all subsequences(the ones with the 1) — (half of all subsequences w/o one — 1(because the empty subsequence is ignored). Since, the amount of subsequences that are nonempty is odd (2^size of array — 1). A oneness of one is the minimum oneness we can achieve.

C:

Alice has a winning strategy if

a) The beginning or the end are 1 in which case she inserts an OR surrounding that. This will make the final result 1 because 1 OR x/x OR 1 = 1. and all ANDs are precomputed, before any of the ORs are.

b) There exists two ones attached to each other.

Initial — 00000011000000 Alice move 1 — 0000000 OR 11000000 If Bob does 00000000 OR 1 AND 100000000 Alice responds with 00000000 OR 1 AND 1 OR 00000000. If Bob does 00000000 OR 11 AND 0000000 Alice responds with 0000000 OR 1 OR 1 AND 0000000. By turn three Alice has surrounded 1 or 1 AND 1, which evaluates to 1 with ORs, so therefore a sequence of 0s and 1 is gauranteed to OR with 1, and so the result is 1. Therefore, Alice wins.

All other scenerios Bob wins.

D:

Key Insight 1: If we see an LR we cannot push any element left to L to a position right of R.

This is because L allows swaps from (L and L — 1), while R allows swaps from (R and R + 1). All things past these two canot impact either position.

Key Insight 2: Try to divide permutations.

Take 1 3 2 5 4 , imagine it as 1 | 3 2 | 5 4. Now, considering insight 1, what must be true to allow this permutation to be sorted? Answer: The must be no LR is positions 2/3 or 4/5 LLLRR is fine as no element from the first three positions needs to move to the last two positions but LLRRR is not because now 2 and 3 cannot swap.

Computataion: Maintain a max seen for first k items in permutation, if k = max, then we have the division between new blocks. Store all divisions between blocks.

Then, create an array from 0 to n. If we see an LR, where LR does not stradle over a division of blocks, then arr[L] = 1, else arr[L]=0

Now for queries, if sum(arr) = 0, output YES else NO [Note: we can store sum as a variable as only two thing in array can change each query]. We input the query(Q), flip the bit, and check for LRs in block immediately to the left and right of Q, and update arr[Q] and arr[Q — 1]. sum -= old(arr[Q] + arr[Q — 1]). sum += new(arr[Q] + arr[Q — 1]).

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

thanks for the contest, really enjoyed the orangutan questions

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

Can someone please provide me the answer to D, during the contest i tried but couldn't solve it

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

    D:

    Key Insight 1: If we see an LR we cannot push any element left to L to a position right of R.

    This is because L allows swaps from (L and L — 1), while R allows swaps from (R and R + 1). All things past these two canot impact either position.

    Key Insight 2: Try to divide permutations.

    Take 1 3 2 5 4 , imagine it as 1 | 3 2 | 5 4. Now, considering insight 1, what must be true to allow this permutation to be sorted? Answer: The must be no LR is positions 2/3 or 4/5 LLLRR is fine as no element from the first three positions needs to move to the last two positions but LLRRR is not because now 2 and 3 cannot swap.

    Computataion: Maintain a max seen for first k items in permutation, if k = max, then we have the division between new blocks. Store all divisions between blocks.

    Then, create an array from 0 to n. If we see an LR, where LR does not stradle over a division of blocks, then arr[L] = 1, else arr[L]=0

    Now for queries, if sum(arr) = 0, output YES else NO [Note: we can store sum as a variable as only two thing in array can change each query]. We input the query(Q), flip the bit, and check for LRs in block immediately to the left and right of Q, and update arr[Q] and arr[Q — 1]. sum -= old(arr[Q] + arr[Q — 1]). sum += new(arr[Q] + arr[Q — 1]).

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

Was the server also unavailable to you for the last 15 minutes before the end and for 15 minutes after the end of the contest? I was only able to connect to m1.codeforces.com but not to the main website. Something needs to be done with stability of the service.

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

    Nope, worked fine except the usual cloudflare human check in the beginning.

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

Maybe I'll become pupil today

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

Difficulty guess

A:800

B: 900

C: 1400

D: 1800

E: 2400

I did not attempt F/G1/G2

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

    damn D was really hard still 2k+ submission I think I have skill issue

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

    i think C is 1200 at best, its a stupid observation that anyone can make. D is also 1800 only because implementation, but i think the idea itself is 1600 at most

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

      I put C higher because it is easy to miss the observation or take more than one try (as I did).

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

      I still didn't got the idea of D can u help me out in that. While C's idea was stupid but was definitely tough to make so I think it can be 1300-1400

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

    I think E is *2200 and F may is *2300.

    UPD: I think G1 is about *2600.

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

https://mirror.codeforces.com/contest/2030/submission/286828473

I thought a little different for problem D but idk where it's going wrong. The basic intuition is the string should be of type R*L* (RRR...LLL). So, I stored the indices of L and R in two separate sets. If highest(SetR)<lowest(SetL) is true, answer to that query will be True. And if the array starts in correct order (1,2,3..) I neglect those indices, same as for ending (..n-2,n-1,n). I'm unable to understand why this approach isn't working?

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

Anybody solved F with Merge Sort Tree?

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

I'm not able to find the case where this code will fail. can anybody help here?

https://mirror.codeforces.com/contest/2030/submission/286836896

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

Thanks for the problems!

I think the difficulty from C to D was huge. From a few lines to a heavy implementation

Edit: well it seems it's much easier to implement than I thought .

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

Hello,Mike.

I'm using my friend's account,and w2y51c318 is my account.

In this contest,I used WrongAnswer_90 as my secondary account to take part in,and my two accounts:2w51y318c and WrongAnswer_90 was both banned.

I feel regreted to break the rules,and register a new account w2y51c318.I used it to participate in this contest and got rank 1.

I thought everything was in the past,but when I was enjoying today's contest,I got banned again.

I do not use any other account,and w2y51c318 is my only account now.I feel confused about being treated like this.I just wonder if you just mistakenly banned my account.

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

https://mirror.codeforces.com/contest/2030/submission/286859205 i really need some help with my code,i cant find where is wrong.problem D

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

Good start time!I don't need to stay up late!

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

wrong post

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

I received a notification about my solution for[problem:2030A][submission:286757203] being flagged for similarity to other users' solutions. I would like to clarify that the similarity might have occurred because a friend and I are part of the same training group and often practice together. While we did not copy each other's code, we may have developed a similar coding style due to our training sessions. I understand this could have caused the solutions to appear more similar than usual.

Please note that my submission was written independently, and I did not engage in any form of plagiarism or code sharing during the contest. I am happy to provide further details if necessary.

Thank you for your understanding, and I look forward to resolving this matter.

Best regards,

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

Hello,

I am writing to express concern and to appeal the recent decision on my submission (plvzfq-rit/286815457) for Problem 2030C, "A TRUE Battle," and sravani_k29/286809003. A system message was sent and notified me that my submission was flagged for being similar to sravani_k29's. While I do understand that this is being done in an effort to keep the competition fair and honest, I would like to humbly ask for your kind reconsideration in this matter.

Upon taking a closer look, it seems to me that my submission is similar to sravani_k29's since the problem seemed to be quite simple, and that we shared a common simple approach to solving it (considering the editorial for this problem). It does not also help that Python (the language we both used) lends itself to creating simple scripts. It is also unlikely that I have copied from sravani_k29 since I do not know them. In an attempt to add further proof to my claim, attached are screenshots of the digital scratch work (with date) I have made during the competition for this problem:

To explain my scratch work and thought process, after failing my first submission wherein I had falsely thought that there was a property based on the number of 1's and 0's, I decided to create a binary tree showing possible outcomes if one were to add a 0 or a 1 to the end of the parent string. From there, I had evaluated each possible case up to cases with length 4. Seeing that starting with 1 was conducive to Alice's success, I decided that it was a sufficient condition and went on to investigate other successes when the string started with 0. Lining them up in a column and evaluating them again, after some time, I saw that if the string were to end in a 1 or if it were to have a 11 inside it, then either would also be conducive to Alice's success. This then led me to my solution.

Hoping for your kind reconsideration,

Sincerely,

plvzfq-rit

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

Regarding the issue of my leaking code on a public platform, please take a look at this. https://mirror.codeforces.com/blog/entry/135438

→ Reply