thanhchauns2's blog

Codeforces Round #963 (Div.2)
By thanhchauns2, 6 weeks 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

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

As a tester, TrendBattles orz

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

As a participant, I am here before the testers.

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

As a tester, danghuyhau orz

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Ahem... cough

    → Reply
    • »
      »
      »
      6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

as a tester, danghuyhau orz

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

as a tester, danghuyhau orz

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

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

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

As a participant,

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

As a testers, I tested all over the problems

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

Hope for reaching Master after after after this round.

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

As a participant, danghuyhau orz

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

Hope to reach master before i die !

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

    yo wtf

    → Reply
    • »
      »
      »
      5 weeks 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
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

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

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

      yo wtf

      → Reply
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to Solve 3 problems

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

As the tester, I tested.

→ Reply
  • »
    »
    5 weeks 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
»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

orz

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

as a participant, bibimoni orz

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

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

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

As a tester

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

Seems that nobody like my joke

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

as a tester, i did literally nothing...

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

ngl it was the shittiest joke I've ever read

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
as the weakest tester who tested the round
→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Amaterasu!!!!!!

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

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

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

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

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

Hoping for a top 7000 finish :'(

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

So cool!

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope the best round! ^_^

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

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

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

Hope to reach Pupil after this

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

As a participant, i'm on hopium :D

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

i want to be tester

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

as a participant i wish to be a tester someday.

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

As a tester, I currently have no contributions.

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

ORZ

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

    What is ORZ can you explain?

    → Reply
    • »
      »
      »
      5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

oh my gad glow cheese round!!!!

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

As a participant, chikien2009 orz

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

Mely orz

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

As a GlowCheese fan, I will participate

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

will there be pics of the authors ?

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

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

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

As a participant, hhoangcp orz

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

As a participant, khoad orz

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

As a contestant, I wish i can change be master

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

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

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

Still preparing cheese for the contest

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Done eating 5 kg of cheese...

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

hope to solve C and get +ve delta

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

I think it will be Permutation_force :(:(

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
spoiler
→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping you guys will make this contest fantastic

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

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

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

orz

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

GlowCheese, thanhchauns2 oooooorzzzzzzzzzzzzzzz

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

oh, Vietnamese contest!!!

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

Hope to reach Candidate Master after this contest

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

should increase rating at least by a bit

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

rating distribution when?

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

Hope to get 1250+ after this contest!

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

score distribution?

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

As a participant,

confidential
→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to reach pupil today

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

Score distribution ??

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

As not a tester, how to become tester?

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

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

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

CM go go?

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

I wish will turn green today :)

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

Will solve 5 problems today

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

newbie to codeforces. any advices?

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

wish work out E today.

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

hope for Salah7_a <3

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

great round!

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

good A B C, never again ^_^

→ Reply
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

SpeedForces!

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

casework orz

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

C and D are too far apart.

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

I was very mad...

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

Is D binary search?

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

    Yes.

    → Reply
    • »
      »
      »
      5 weeks 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
      • »
        »
        »
        »
        5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think the main tests is a lot harder

    → Reply
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Uphacked as per your wish :)

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

Thank you for the great animations in F!

→ Reply
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

F2 = F1 + CF710D

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

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

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

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

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    → Reply
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damnnn thats actually cool

      → Reply
    • »
      »
      »
      5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone explain B and C solution

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

How C?

→ Reply
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

f44a1f8643196544cd31ab9501e3e62f .

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is idea B?

→ Reply
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

mathforces :(

→ Reply
  • »
    »
    5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
      • »
        »
        »
        »
        5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same, all problems i passed pretest are in queue

    → Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why are some submissions skipped

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

Cheaters must be stopped before it runs into Cheatforces

→ Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's Gcc optimization

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

    it gets compiler optimized...

    → Reply
    • »
      »
      »
      5 weeks 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
      • »
        »
        »
        »
        5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does it work, i can't understand.

    → Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      still 2 pupils having lgm perf just screams alt accounts

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

B, D, and E are great problems <3

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a random dude, phungthienphuoc orz :)

→ Reply
»
5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I hate Median

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
4 weeks 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