Блог пользователя thanhchauns2

Автор thanhchauns2, 3 месяца назад, По-английски

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
  • Проголосовать: нравится
  • +522
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

As a tester, TrendBattles orz

»
3 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

As a participant, I am here before the testers.

»
3 месяца назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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-

»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

As a tester, danghuyhau orz

»
3 месяца назад, # |
  Проголосовать: нравится +107 Проголосовать: не нравится

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;/;

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Ahem... cough

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +56 Проголосовать: не нравится

      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.

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

as a tester, danghuyhau orz

»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

as a tester, danghuyhau orz

»
3 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant,

Spoiler
»
3 месяца назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

As a testers, I tested all over the problems

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Hope for reaching Master after after after this round.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, danghuyhau orz

»
3 месяца назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Hope to reach master before i die !

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to Solve 3 problems

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

As the tester, I tested.

»
3 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

orz

»
3 месяца назад, # |
Rev. 4   Проголосовать: нравится -26 Проголосовать: не нравится

as a participant, bibimoni orz

Spoiler
»
3 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

As a tester

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

Seems that nobody like my joke

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

as a tester, i did literally nothing...

»
3 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

ngl it was the shittiest joke I've ever read

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
as the weakest tester who tested the round
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Amaterasu!!!!!!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping for a top 7000 finish :'(

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So cool!

»
3 месяца назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope the best round! ^_^

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to reach Pupil after this

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, i'm on hopium :D

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

i want to be tester

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

as a participant i wish to be a tester someday.

»
3 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

As a tester, I currently have no contributions.

»
3 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

ORZ

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    What is ORZ can you explain?

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

oh my gad glow cheese round!!!!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, chikien2009 orz

»
3 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Mely orz

»
3 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

As a GlowCheese fan, I will participate

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

will there be pics of the authors ?

»
3 месяца назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, hhoangcp orz

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, khoad orz

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

As a contestant, I wish i can change be master

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Still preparing cheese for the contest

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Done eating 5 kg of cheese...

Spoiler
»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

hope to solve C and get +ve delta

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think it will be Permutation_force :(:(

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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??

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
spoiler
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping you guys will make this contest fantastic

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

orz

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

GlowCheese, thanhchauns2 oooooorzzzzzzzzzzzzzzz

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

oh, Vietnamese contest!!!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to reach Candidate Master after this contest

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

should increase rating at least by a bit

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

rating distribution when?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to get 1250+ after this contest!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

score distribution?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

As a participant,

confidential
»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping to reach pupil today

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Score distribution ??

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

As not a tester, how to become tester?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

CM go go?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wish will turn green today :)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will solve 5 problems today

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

newbie to codeforces. any advices?

»
3 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

wish work out E today.

»
3 месяца назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

hope for Salah7_a <3

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great round!

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

good A B C, never again ^_^

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +61 Проголосовать: не нравится

    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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

SpeedForces!

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

casework orz

»
3 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

C and D are too far apart.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I was very mad...

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is D binary search?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Thank you for the great animations in F!

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

F2 = F1 + CF710D

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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; }

} ~~~~~

»
3 месяца назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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)

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
    Hint 1
    Hint 2
    Hint 3
  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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 :)

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Damnnn thats actually cool

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone explain B and C solution

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How C?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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}$$$.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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; }

    } ~~~~~

»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

f44a1f8643196544cd31ab9501e3e62f .

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is idea B?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

mathforces :(

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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]).

»
3 месяца назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
3 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why are some submissions skipped

»
3 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Cheaters must be stopped before it runs into Cheatforces

»
3 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

274418415

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

Link of editorial don't work

update : it is working now : )

»
3 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.me/contest/1993/submission/274429127 this code runs for 10^16 how? MikeMirzayanov thanhchauns2

»
3 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

You are not allowed to view the requested page

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

B, D, and E are great problems <3

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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...

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a random dude, phungthienphuoc orz :)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    .

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I hate Median

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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....

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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