thanhchauns2's blog

Codeforces Round #963 (Div.2)
By thanhchauns2, 4 months ago, In English

Hello Codeforces!

$$$\newline$$$

Do you know that eating cheese can make you code faster than the running speed of a Tyrannosaurus REX?

It's been a while, today GlowCheese and I are delighted to invite you to participate in Codeforces Round 963 (Div. 2). This round will be rated for all participants with a rating lower than 2100.

Our round will start on Aug/04/2024 17:35 (Moscow time). You will be given 6 problems and 120 minutes to solve them.

This contest is brought to you by Code Mely, a Vietnamese community for Computer Science. Reach out to us here.

Special thanks to:

Score distribution: $$$500 - 1000 - 1500 - 2000 - 2750 - (2500 - 1000)$$$

Hope to see you in the final standings!

UPD1. Editorial is out!

UPD2. Congratulations to the winners:

Div.2:

  1. kkkksc03
  2. imwh
  3. _acsm_
  4. _wrpwrp
  5. rainboy

Div.1 + Div.2:

  1. A_G
  2. arvindf232
  3. Rubikun
  4. kkkksc03
  5. Sugar_fan
  • Vote: I like it
  • +522
  • Vote: I do not like it

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

As a tester, TrendBattles orz

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

As a participant, I am here before the testers.

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

As a tester, I was too busy doing last-minute testing that I run out of good pick-up lines for contribution pleadings.

Also, I wanna say a lot but the authorities will shut me dow-

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

As a tester, danghuyhau orz

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

Hello, I don't have much time to tell this but as a tester I've known quite some things. Specifically for problem D you can solve usingdajpoiiadaodald;/;

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

    Ahem... cough

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

      Yes my lord, as a tester I am programmed to prioritize security and integrity of Codeforces rounds, and problem spoiling heavily damages the experience and trust of the majority of round participants, which can be considered inappropriate, or even harmful to the Codeforces community as a whole. I can offer suggestions for alternative positive problem solving methods that can be practiced for enhancing one's ability to compete in such Codeforces rounds instead. Please let me know if you would like me to assist you with any further requests.

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

as a tester, danghuyhau orz

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

as a tester, danghuyhau orz

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

As a tester, I did nothing but still be mentioned.

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

As a participant,

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

As a testers, I tested all over the problems

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

Hope for reaching Master after after after this round.

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

As a participant, danghuyhau orz

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

Hope to reach master before i die !

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

    yo wtf

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

      What extension are you using to differentiate everyone’s comments in your image?

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

        I think everybody's just screen captioning one after another.

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

      yo wtf

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

    Imagine if one day your wish were granted, and codeforces permanently shut down the next day. You'd be immortal, but you probably wouldn't be immune to aging. That sounds like hell on Earth.

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

Hope to Solve 3 problems

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

As the tester, I tested.

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

    wooow impossible i don't believe that i didn't notice that testers test

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

orz

→ Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it -26 Vote: I do not like it

as a participant, bibimoni orz

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

Best wishes to my purple friends, hope they become orange!

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

As a tester

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

Seems that nobody like my joke

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

as a tester, i did literally nothing...

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

ngl it was the shittiest joke I've ever read

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
as the weakest tester who tested the round
→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why does the round number doesn't show up in cf contests page? image

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

Amaterasu!!!!!!

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

Hmm "GlowCheese and I are", not " GlowCheese and me are".

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

Watch your 6 homeboy I'm coming for your as-

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

Hoping for a top 7000 finish :'(

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

So cool!

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

As a Faze fan, I can confirm karrigan is the World No.1 IGL

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

Hope the best round! ^_^

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

Make you code? Shouldn't be make your code?

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

Hope to reach Pupil after this

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

As a participant, i'm on hopium :D

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

i want to be tester

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

as a participant i wish to be a tester someday.

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

As a tester, I currently have no contributions.

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

ORZ

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

    What is ORZ can you explain?

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

      orz, lowercase, looks like a guy bowing

      ORZ uppercase doesn't mean anything but people like to capitalize orz. If you want a capital version of orz, OTZ works.

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

oh my gad glow cheese round!!!!

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

As a participant, chikien2009 orz

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

Mely orz

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

As a GlowCheese fan, I will participate

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

will there be pics of the authors ?

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

sorry but... GlowCheese and *I =))

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

As a participant, hhoangcp orz

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

As a participant, khoad orz

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

I hope I can achieve green after this contest if I have time to participate.Good luck to everyone!

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

As a contestant, I wish i can change be master

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

Announcement with a meme at the beginning? Something new... (for me)

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

Still preparing cheese for the contest

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

As a participant , I hope everyone get an increase in rating after this contest ;)

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

Done eating 5 kg of cheese...

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

hope to solve C and get +ve delta

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

I think it will be Permutation_force :(:(

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

Do you know that eating cheese can make you code faster than the running speed of a Tyrannosaurus REX?

is it some kinda hint or wot??

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

Hoping you guys will make this contest fantastic

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

I hope I get a 1000+ rating after this contest (●'◡'●)

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

orz

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

GlowCheese, thanhchauns2 oooooorzzzzzzzzzzzzzzz

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

oh, Vietnamese contest!!!

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

Hope to reach Candidate Master after this contest

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

should increase rating at least by a bit

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

rating distribution when?

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

Hope to get 1250+ after this contest!

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

score distribution?

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

As a participant,

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

As a participant, I hope I'm not choking in this contest

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

I hope everything goes well. I can play as well as I should in this game.And....stO Akulyat Orz.

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

Hoping to reach pupil today

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

Score distribution ??

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

As not a tester, how to become tester?

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

As a Newbie, hope, I'll become Pupil.

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

CM go go?

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

I wish will turn green today :)

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

Will solve 5 problems today

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

newbie to codeforces. any advices?

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

wish work out E today.

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

hope for Salah7_a <3

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

great round!

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

good A B C, never again ^_^

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

may be problems are easy or difficult compare to other div2 round but i find it much difficult need to practice more

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

My dislike to this contest is addressed not to the authors, who did a great job, but to Akulyat, who completely fucked up problem difficulty estimation. Awful work as a contest coordinator.

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

    I'm sorry that the gap between C and D turned out to be that huge
    Based on the testers' performance C seemed harder and D easier, so we assumed that the gap was reasonable

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

      No luck. Unfortunately, it happens quite often to div2 rounds. Probably something is wrong with the way problems are being assessed.

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

    I think it is a bit harsh to blame the coordinator for that as the problem difficulty assessment is based on the testers feedback (and the tester pool seems diverse enough). It turned out that D was maybe a little bit on the hard side (but it still got around 600 solves in contest which is reasonable imo). The issue might be that C is "too easy" as it has 7k AC so the round feels speedforces for some contestants. However, I believe this is more of an issue with the div2 format rather than problem selection.

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

      Problem C is not "too easy". it has 7k AC out of which at-least 3k are cheated solutions.

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

SpeedForces!

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

I'm seeing a lot of people who were not even able to solve 3 problems in div3 or 2 in div2 in their past few contests have solved 1500-rated problem in this one. Are they suddenly becoming intelligent or what? If they are cheaters, will CF do something for them, or are they also silent like LC? I'm not aware of what CF does to catch them. Do anyone know, if they have a strong plag check or not?

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

casework orz

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

C and D are too far apart.

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

I was very mad...

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

Is D binary search?

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

    Yes.

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

      Dang, I kept getting WA and wasn't sure if it was correct. How does the check function work? I took all numbers greater than the one we're checking and did two pointers.

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

        I binary searched on the answer and verified with dp. I kept getting MLE and it would've probably TLEd but basically create a new array $$$b$$$, $$$b[i] = (a[i] >= mid ? 1:-1)$$$ and now you have to find the maximum sum of the elements outside the intervals where you placed $$$ n/k - (n mod k == 0) $$$ disjoint intervals on the array $$$b$$$. If that sum is greater than 0, the mid is valid.

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

I think problem C has extremely weak pretest,

I passed pretest it without binary search O(n * k)

even wrote hack myself but anyway I didn't hacked :)

UDP: it actually passed systest wtf I'm so lucky

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

    You don't even have to binary search, O(n+k) is possible, so yeah

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

    i think the main tests is a lot harder

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

    is binary search the intended solution? I solved it without binary search in O(n). At least I passed the pretests, I hope it doesn't FST.

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

    Uphacked as per your wish :)

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

Thank you for the great animations in F!

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

Ordered sets got TLE in D, I suppose BIT is the intended solution? Didn't have time to implement at the end

UPD: nvm, in worst case for values $$$k$$$ close to $$$n$$$ and all unique values of $$$a_i$$$ this approach is both quadratic time and memory, regardless of DS used ;c

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

the speed of solving B, C is normal or bcos of cheating?

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

    plenty of cheaters these days. Just compete with yourself, learn new concepts and upsolve. Dont bother too much about the rankings or ratings.

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

      seeing alot of people solve very fast/difficult problems (not normal) while u still didn't get it yet, not good feeling

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

F2 = F1 + CF710D

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

D is so hard that only 400 (unofficial excluded) solve it!

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

What a joke! 7500+ solved C — 500+ solved D

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

Is problem D DP? Whether to retain current element or not and then update median?

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

I really liked problem D, the fact that the $$$i$$$-th element of the resulting set must be in a position $$$j \equiv i (\mod k)$$$ is a really really cool invariant, and the resulting DP to check if a median is achievable is really nice as well.

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

Can you tell me the mistake in the C problem. vector =vl rep=for loop I = cin<< ; ~~~~~ //this is the code ll solve() { ll n,k; I n>>k; vl arr(n); rep(i,n){ I arr[i]; } ll l=0,r=k; sort(arr.begin(),arr.end()); ll at=arr[0]; rep(i,n){ if((arr[i]-at)%(2*k)>=k){ r=min((arr[i]-at)%k,r); }else{ l=max((arr[i]-at)%(k),l); } } if(l>=r){ return -1; }else{ ll l2=0; if(((arr[n-1]-at)%(2*k))<k){ l2=(arr[n-1]-at)%k; } ll addd=0; if(l2>=l){ addd=0; }else{ addd=l-l2; } return arr[n-1]+addd; }

} ~~~~~

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

ARGHH i think i solved F2 but i was about 10 mins too slow

basically from (0,0) -> (a,b) -> it will visit some nodes [k = 1] -> (x,y) -> (a+x, b+y) -> more nodes [k = 2] -> (2x,2y)

it's a (0,0) if it's a multiple of (2w,2h) or x'%2w = 0 AND y'%2h = 0

let W = 2w, H = 2h

let's say you're working with some coordinate (u,v) -> it's a (0,0) iff (u-kx)%W = 0, (v-ky)%H = 0

kx%W = u

ky%H = v

if gcd(x,W) not 1 then kx%W = -u eqv to k(x/gcd)%(H/gcd) = (-u/gcd) (same for the y case)

solve for k for each one (assuming there is a solution) -> k = u*lcm(H,W) + w -> then just check how many k exists between [1..k]

repeat for each coordinate (there can only be at most 10^6 of them)

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

In D, I tried doing binary search and converting the arrays into 1s and 0s based on if element >= mid. Now we basically need to choose more 1s and 0s. What do we do beyond this? I though of dp but thats n*k

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

    In your states, if you try to minimize the number of remaining $$$0$$$, you don't need to remember how much elements you've taken (you will have to take at least $$$n \bmod k$$$ and there is no point in taking more). You just need to remember if you took at least one element in the case $$$k$$$ divides $$$n$$$. So you have $$$2n$$$ states.

    I think it's a cool observation, congrats to the problem author :)

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

      Damnnn thats actually cool

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

      That is probably sufficient to pass, but FYI it can be optimized to a linear DP with $$$n$$$ states. We want to pick, sequentially, an element that is in a index with 1 mod k, 2 mod k, ..., n mod k (using 1-indexed and considering the case where n mod k!=0). The problem arises only when we "wrap around" and start taking 1 mod k, 2 mod k, ..., n mod k, ..., 0, 1 mod k and start taking more than the limit. This can be avoided by simply preventing the transition from 0 to 1 mod k and instead setting dp[i]=(a[i]>=x) for every index $$$i\equiv1 \pmod{k}$$$. Sub

      P.S. It's even possible to optimize it to $$$k$$$ states.

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

can anyone tell why this failed, this is hurting my brain 274401938

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

    Take the case {1,2,10}
    If you have to make two moves why not make it on the largest even element and in that way you can take all other element in one move

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

    you need to run backward 1 more time cause there are some case where running backwards have smaller moves

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

    Oh okay, i get it now, when we need to perform 2 operation of swapping then we will do it on the max even number, this would nullify the need for (+=2 moves ) for rest of even, hence atmost we will repeat only one move

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

    Think in this example: 1 2 6 Your code gives answer=4 but the answer is at most number of evens+1, because you could turn the greatest even number into an odd number and it would be bigger than the rest of evens. If the greatest odd is less than the greatest even you can turn the greatest even into odd in 2 moves, otherwise it will take only 1 move.

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

anyone explain B and C solution

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

How C?

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

    Denote $$$\text{ans} = \max(a_i)$$$, iterate all lights and find the next $$$x \ge a_i$$$ that the light in question will be on, then assign $$$x$$$ to $$$\text{ans}$$$. Check if $$$\max(a_i) + k < \text{ans}$$$.

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

    I tried using this and its giving a slight wrong answer in the test case of +1 in some test , i dont know why. ~~~~~ ll solve() { ll n,k; I n>>k; vl arr(n); rep(i,n){ I arr[i]; } ll l=0,r=k; sort(arr.begin(),arr.end()); ll at=arr[0]; rep(i,n){ if((arr[i]-at)%(2*k)>=k){ r=min((arr[i]-at)%k,r); }else{ l=max((arr[i]-at)%(k),l); } } if(l>=r){ return -1; }else{ ll l2=0; if(((arr[n-1]-at)%(2*k))<k){ l2=(arr[n-1]-at)%k; } ll addd=0; if(l2>=l){ addd=0; }else{ addd=l-l2; } return arr[n-1]+addd; }

    } ~~~~~

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

f44a1f8643196544cd31ab9501e3e62f .

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

I couldn't finish C but I was thinking of segment tree with range update... was thinking of sorting input, use smallest value to find all start points until its greater than largest element. Use lower_bound to find where each element is compared to the ranges of the smallest element. Determine the offset of this value to the nearest first element start ranges

eg 

            4 3
            3 4 8 9

            3: 3,4,5 9,10,11
            4: 4,5,6 10,11,12
            8: 8,9,10
            9: 9,10,11
            
            compared to 3 nearest active range
            4 is +1, nearest start was 3
            8 is -1, nearest start was 9
            9 is 0, nearest start was 9

if the min offset and max offset diff was >= k, then it was probably invalid. Could only think of inserting all of first element's active ranges using segtree range updates then do the same for all following elements, then query which time appear n times. Not sure what i'm talking or thinking about anymore, fairly new to CF this was tough

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

What is idea B?

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

    Except for when all elements are even at first, the common parity of every final array is odd.

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

    if parity of any two num is different then can only be solved by making every element odd..rest think yourself

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

mathforces :(

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

    A-D din't need any crazy math.(I don't know about the other problems) :)

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

A: sum(c)(max(0, cnt(c)-a)) for 'A'<=c<='D'.

B: Assume there are both odd and even numbers in a[i] (otherwise answer is trivially 0), because in each operation we can reduce count of odd numbers by at most 1 in each operation, and when there's only 1 odd number we can't change its parity, we need to change all numbers to odd. So we can add the greatest odd number to smallest even number repeatedly, until there's no even number. If we can do this, the answer is (count of even numbers). Otherwise, we can add the greatest even number to an odd number, and add this odd number to all even numbers, then answer is (count of even numbers)+1.

C: Let A = max(a[i]), the number of lights turned on will change with period 2*k after A minutes, and the answer cannot be small than A, so we only need to check range [A, A+2*k-1] using prefix sums.

D: Let's find the answer by binary search. So for certain M we need to change a[i] to 1 when a[i]<M or 0 otherwise. Then we need to choose some remaining indexes {i0=0, i1, i2, ..., i_r, i_(r+1)=n+1} where i_(j+1)-i_j-1 is multiple of k (0<=j<=r), and sum(a[i_j]) is minimized. We can solve this by dp: let dp[i] = the minimum sum if we let i_r=i. Then we have dp[0]=0, dp[i]=a[i]+min(0<=j<i, j%k==(i-1)%k)(dp[j]), the minimum valid sum is min(1<=i<=n, i%k==n%k)(dp[i]).

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

for c : The formula used to adjust the installation times and determine when each room's light will be on is:

$$$adjustedtime[i]$$$ $$$=$$$ $$$a[i]+k×$$$ $$$⌈ \dfrac{maxa−a[i]}{k} ⌉$$$

Where:

$$$a[i]$$$ is the installation time for the $$$i-th$$$ room.

$$$k$$$ is the interval at which the light toggles.

$$$maxa$$$ is the maximum installation time among all rooms.

$$$⌈x⌉$$$ denotes the ceiling function, which rounds $$$x$$$ up to the nearest integer.

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

D is somehow similar to https://codeforces.net/problemset/problem/1486/D

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

E: Thinkless $$$O((n+1)^2(m+1)^2 (2^n+2^m))$$$ cooked me (I need one more optimization to get AC)
btw, in this kind of problems, why not limit $$$t \le 10$$$ (small constant) or use single test, instead of complicated bound for one input?

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

    Single test leads to having too many tests. Since the resources are limited, it leads to worse coverage.
    If we do $$$t \le 10$$$, then we can have $$$10$$$ large tests or $$$10$$$ small tests, meanwhile we want to have just a couple of big tests (otherwise the complexity would be multiplied by $$$t$$$) or lots of small tests (for better coverage)

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

      TBH, $$$\sum (n^2+m^2) \le 500$$$ seems very heuristic and I think it's difficult to determine which complexity is acceptable.
      This problem is D2E, so the limit of #tests isn't have to tight I guess.

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

        The limit was set in such a way so as not to let determine the complexity based on it

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

Is judging cooked? Some early submissions are stuck in queue (including my A)

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

    i think so i have same issue with problem B still in queue

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

    same, all problems i passed pretest are in queue

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

any idea why it doesn't work for B ? https://codeforces.net/contest/1993/submission/274399672

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

    1

    3

    1 20 40

    your code returns 4

    correct answer is 3

    1 20 40 -> 41 20 40 -> 41 61 40 -> 41 61 101

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

      Thanks, should've either 1) hardcoded the answer in case i find the bigger one and just subtracted from the number of evens the ones i ve already cleared and made it +1 2) when i add a bigger number take it from the end so it is bigger than anything in the middle

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

why are some submissions skipped

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

Cheaters must be stopped before it runs into Cheatforces

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

Problem C by 7k+ people. It's a sure shot cheating case. Please do look at it :)

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

    Either that or just really weak pretests on C (lots of O(nk) sols passed)

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

      I do agree that the pretest were weak, but still 7k+ is huge. I saw several almost same solutions, so ig it was leaked.

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

Can anyone tell why O(N*K) working for problem c https://codeforces.net/contest/1993/submission/274391283

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

Problem D: Find error in my logic, it is giving WA (176th number) on test case 2

274418415

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

Hey everyone

can someone please tell me why my solution for Problem B — Parity and Sum is WA on test case 2

My c++ solution:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

// Code By VibhuGodson
int main ()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll>evn;
        ll mxod=-1;
        ll x;
        for(ll i=0;i<n;i++){
            cin>>x;
            if(x%2) mxod=max(mxod,x);
            else evn.push_back(x);
        }
        sort(evn.begin(),evn.end());
        ll ans=0;
        if(evn.size()==0 or evn.size()==n){
            cout<<ans<<endl;
            continue;
        }
        for(auto&i:evn){
            if(i>mxod){
                mxod=2*i+mxod;
                ans+=2;
            }else{
                mxod = i+mxod;
                ans++;
            }
        }
        // cout<<"---------------";
        cout<<ans<<endl;
    }
    return 0;
}

I think the intution is same as per the editorial

my submission

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

    whenever you would do ans+=2, you can just break and print out the amount of even numbers+1, because if that ever happens, then its optimal for it to happen to the biggest even element, after which you will always be able to just do it in 1 step. i hope i explained it well

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

    Consider this case :

    4 ----> 2 6 10 1

    according to your code answer will come 5, but answer is 4 1 + 10 = 11, 11 + 10 = 21, 21 + 6 = 27, 27 + 2 = 29

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

      Sorry I didn't get it why ans will be 4 (I think you're missing updating 4, we just updated 1,10,6 and 2)

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

Link of editorial don't work

update : it is working now : )

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

The test of Problem C is too weak. Many people accept this problem with a solution which has time complexity of O(nk).

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

Thank you the authors and Code Mely for the awesome contest! I enjoyed it a lot!

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

I think the cases were too weak for problem B and C. Many submissions of O(n*k) for C are accepted and for problem B https://codeforces.net/contest/1993/submission/274429127 this code runs for 10^16 how? MikeMirzayanov thanhchauns2

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

    It's Gcc optimization

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

    it gets compiler optimized...

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

      Omg Dominater069 Orz. Can you please tell me more about this. I don't know what GCC optimisation is

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

        Those loops don't make any actual effect on anything, and the compiler can notice it just by analysing the code. So therefore it just entirely removes the loops so they become non-existent.

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

    Why does it work, i can't understand.

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

Can't open tutorial. I'm getting this error:

You are not allowed to view the requested page

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

I solved ABC under an hour as a 1000 rated. C definitely seemed easier than almost all Div 2s I’ve done.

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

2 pupils in top 5 beating all candidate masters sounds fishy. Moreover they aren't new accounts either. The guy at rank 1 had 10k rank in last contest and 8 in last to last. Don't you think it's too strange of a variation?

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

    that's because he tried the rainboy style solving in the reverse order

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

      still 2 pupils having lgm perf just screams alt accounts

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

B, D, and E are great problems <3

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

Problem C was not qualityfull at all whereas B was enough good

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

Thank you to the authors and coordinator for the nice problems!

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

D is a great problem, but F2's trick is trivial :(

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

    i think it'll be better if swap(E,F), E is much harder than F for me.

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

      Funny, while testing I keep baffling myself at "why don't people solve E? it's straightforward as heck".

      Actual contest seems to show the opposite of my opinion, heh...

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

As a random dude, phungthienphuoc orz :)

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

I wasn't able to solve D in contest because I didn't think in terms of binary search and then converting the array to binary and then solving it using DP.

Is it a known technique, which I am not aware of or are there more questions like this?

I want to solve them and learn as it isn't intuitive for me yet.

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

I think the data of problem C is a bit weak. I used the method of O(nk) with a little trick and then passed problem C.

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

    .

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

      Bruh, it is skipped because he submitted it again, and only the last submission is judged in the contest

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

      However, my newly submitted methods are all O (nk) in complexity, but with an optimization, such as removing duplicate elements

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

I hate Median

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

7k people solve C? That's impossible. I almost become expert, but I didn't solve C and get -80 scores, that really hurts : (

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

Anyone please tell my c ques passed in n*k loop. Is it correct or wrong.

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

I wrote a code earlier for light switches ques i made a approach of using arithmetic progression formula a+(n-1)d to get the n for every element and if it is even then i break the loop....it was working but there are large testcases where i dont know at what limit to break the loop to return -1...please help and tell if it is even possible to use this approach or is it only noobish...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //this is code

include <bits/stdc++.h>

using namespace std; typedef long long ll; typedef vectorvl; typedef vector vvl; int main() { ios::sync_with_stdio(false); cin.tie(0);

ll t;cin>>t; while(t--){ ll n,k; cin>>n>>k; vl v(n,0); ll maxi=0; for(int i=0;i<n;i++){ cin>>v[i]; maxi=max(maxi,v[i]);

}

    ll f=0;ll fin;
for(int i=maxi;i<=10000007;i++){
    f=0;
    for(auto num:v){
       ll res=((i-num)/k)+1;
       if(res<=0||res%2==0){
         f=1;
         break;
       }

    }

    if(f==0){
       fin=i;
       break;
    }
}

if(f==0)cout<<fin<<endl;
else cout<<-1<<endl;

}
} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ it works for input given but for last one it return 100 i don know why....

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

Greetings! I want to appeal against the cheating verdict received for my submission of problems A,B,C of this round. I received the skipped verdict for this submission. I haven't copied this code from any public source, and I have completely written it.And some of those people use different language and i sumbit before them . please check this problem

→ Reply