cry's blog

Codeforces Round 965 (Div. 2)
By cry, 2 years ago, In English

Wazzup Codeforcers!

sum, satyam343, and I are extremely ecstatic to invite you to Codeforces Round 965 (Div. 2) on Aug/10/2024 17:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. 1 problem will have subtasks. This round will be rated for all participants with rating below 2100. We spent the most time cooking up this round than any other round, so it means a lot if you will participate.

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

Score Distribution: $$$500 - 750 - 1250 - 1500 - (1750 + 1750)$$$

UPD: We know there has been a lot of disapproval for problem C. We're sorry for it. Please view https://codeforces.me/blog/entry/132507

UPD: Editorial

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

Comments Comments (261)
| Write comment?
»
2 years ago, hide # |
← Rev. 5  
Vote: I like it +6 Vote: I do not like it

Wazzup guys! I encourage you to participate in CerealCodes for their Summer 2024 Contest.

What is CerealCodes?

Disclaimer: This round is not affiliated with CerealCodes.

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

As a first-time tester, I am proud to finally be able to write an "as a tester..." comment :)

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

As a tester.

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

As a tester,

🦧

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

🙈 🙉 🙊 🦍 🦧 🙈 🙈 🦍 🙊 🙊 🙊 🐒 🐒

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

As a tester, I cried because of how beautiful the problems are

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

As a tester, I will take the round for infinite delta.

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

I think I'm the first non-tester to send a messages!!! Can't wait for another cry round!!!

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

As a participant, I feel like the tasks will be very unpredictable.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -14 Vote: I do not like it

    skill issue

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

    what does having subtasks mean ? Will we get partial points for solving the subtasks? I am new to this concept, can anyone explain please

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +14 Vote: I do not like it

      its essentially 2 identical problems, except for some constraint or some important detail being changed, so that the 2nd version is harder than the first. sometimes you can just solve the harder version and submit the same code for both of the versions, but there are exceptions to that, for example this and this,

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

cry orz

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

This contest is the end of an era of Contest IDs with a 4-digit number beginning with 1. On to the 2xxx’s for IDs

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

Did anyone note "coordinatORZ"?

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

how Grandmaster become cyan over 1 year? I'm genuinely curious. I'm talking about the coordinator of this round satyam343. is this level of degeneration really something that could happen or just troll?

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

Monkey doesn't have any pants

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

WTF THATS ME

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

Did satyam343 sell his account or what

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

i will reach gm

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

As an expert participant, I hope to reach back to CM.

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

milind0110 sir Orz

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

first unrated div 2 for me :D

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

Score distribution?

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

Hopefully I get to add some blue to the green of my handle.

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

i hope one day i can proudly stand in the "Our testuwuers: " line owo

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

2 Min silence for those who judged the coordinator on his current rating

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

I'd be thrilled if i reach cyan after this round.

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

Wazzup

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -15 Vote: I do not like it

anyone miss my comments?

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

Good luck, hope its not math forces again

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

Good luck for everyone <3

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

what is the point distribution?

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

is it only me or codeforces is quite lagging recently

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

I see satyam343. I'm shaking. Please no counting maths problems this time. I hate those. Please satyam343 We believe in u.

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

    I hope you don't mind me using this comment in problem C. I just found it funny :p

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

Any specific reason for the contest to be of 3 hours? Also, eagerly waiting for the point distribution to be updated.

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

hope i can solve at least 4 problem XD XD XD

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

Hoping for delta 200++ round. been some time...

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

    May you good luck!

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

      Thanks !

      → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +7 Vote: I do not like it

      first two problems, solved in 5 minutes.

      C problem solved in 1 hour 53 minutes. .

      3 times understood the problem completely wrong. Feeling so stupid. should have read the the test cases first.

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

        how did u do C ?

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

          Hint 1 :

          We need to go greedy. If we apply 'k' addition, we will apply it on one single element. To deduce this, you can try few test cases on pen-paper. find the current median, try to delete elements from left of the median, or right of the median. There also, we need to check if the array is EVEN or ODD size array. So many IF-ELSE :| . you will always find this EXCEPT one edge case ( below described)

          Hint 2 : Edge case handling. 3 4 1 1 100 1 1 1

          In above input, it is best to pick 100 and delete it, and then take median of rest of the array. Sort the values, and pick the last value, and then see, what is the best median you can get from remaining N-1 elements. For that I used binary search.

          Now, we have to take the MAX() value from HINT-1 approach , and edge-case result.

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

As a contestant want to be Master, i wish i can be Master in this round

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

cry orz

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it
Excuse me
→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +15 Vote: I do not like it

    There is no such rule or guideline that the score should be equal to estimated problem rating. It's just that they tend to be similar, but they don't necessarily need to be like that. Score distribution tends to be more exponential than problem rating, and therefore we sometimes have problems of 250 points and 6000 points depending on relative difficulty difference of problems, which is pretty far from their problem rating. Also in Div. 1/2 separated rounds 1A is usually scored 500 points but they're as hard as *1500-rated problems.

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

thembululquaUwU

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

interesting score distribution；GL&HF

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

aaj speedforces hoga kya bc :D

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

As a tester, all the problems are very good and no problem will make you cry

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

At first glance the monkey looks like its showing middle fingers!

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

I thought this is a LeetCode contest after looking at these problem titles

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

unbalancedforces!

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

nice 2000 rating third lmao

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

what is this problem balancing

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

Did they accidentally give us a Div1 instead of Div2.

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

speedforces!

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

Horrible coordination, score dist. is shit.

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

problem rating: 800 800 2000 .... so on. Just let me reach pupil pls..

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

as a Newbie, Pupil, Specialist and new experts the contest duration was 20 minutes or less

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

If you can't make a div 2 round just dont.

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

i am not giving the contest currently but this guy is streaming and giving out the solution for the contest

can you do something about this

i can rarely solve 3rd in div 2 this mf is giving them away

mf madarchod https://www.youtube.com/watch?v=dDZyHLJVHaM

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

Is it just me or there is a problem with same solution to problem B on Codeforces? Also,you liked your social credits joke?Now you have earned your negative credit from me.Hope you liked it.

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

bad contest problem c was too hard for normal div 2

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

    I feel like it is okay, but requires a lot of time to implement, if one doesn't know certain tricks. I'd like to have a full day on it, breaks included, not just 2 hours ;D ...and still not sure my idea would work, maybe this is all just a ramble of a low-skill.

    Of course, given the amount of people who solved, 1250 on rating distribution doesn't make any sense. Looking forward to the editorial...

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +33 Vote: I do not like it

if you can't offer normal div2 problems, please don't do it

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

    I personally didn't like their Div 3 either. "Counting is fun", huh. But math guys will argue.

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

DIV2 C ???

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

Contest too hard, me sed. Back to newbie here I go.

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

I've just become Specialist last Div. 4 Round. Again, I'll be Pupil, or even Newbie.

What Div.2 C??? Wish not this again.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +7 Vote: I do not like it
    The comment removed because of Codeforces rules violation
    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    One's demise is another one's triumph. Someone would have the rating. Maybe one specialist guy, who solved A and B fast enough (not me though, 0:11 A). Let's cheer for them this time.

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

When participants like neal , aryanc403 got stuck on 3rd problem How am I going to get motivation to solve that .

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

Really only 1250 points for problem C?? should be 1500 considering difficulty!

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

Too much harder than Div.2 before!

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

stupid contest

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

Man the C was so hard it took my soul with it .

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

Gonna need a 3 mo break from cp after this

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

E1 is just B(altic)OI 2022 islands on array instead of tree.

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

wtf is that C?

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

problem C score should be at least 1750 imo

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

Can someone please explain, why in in 4th sample Bessi loses if she starts at 2nd and 3rd islands?

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

Median again.

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

    this problem C crush my soul, I can solve it if b was all 1. But not like this

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

      Came back after skimming others thoughts/code. splitting array a into b=0 and b=1 only actually help... Well, need to take a hit and learn tho

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

:(

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

Why do I get WA4 in D? 275609322

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

May be, i am noob or C is a bad problem xD

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

satyam343 bro played with the emotions of his biggest fan lol!

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

https://qoj.ac/problem/3511

Problem E1, E2 was on JOISC.

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

    what's this site? qoj? thank you. (there is no intro in their website)

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

One more median problem and I am killing myself :D

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +13 Vote: I do not like it

С sucks. Its true rating seems to be pretty higher than it's stated. Can't imagine what was on contest creators' mind when making this distribution

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

C solution:

Consider two cases:

I) Greedily choose the largest number that has its $$$b = 1$$$ and spend all your $$$k$$$ on it.

II) Binary search on the largest $$$\operatorname{median}(a)$$$ you can make by the given $$$k$$$, then calculate the answer for this case.

The answer of the problem would be the maximus answer of two cases described above.

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

i hate your biggest fan.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
from collections import *
for _ in range(int(input())):
  x,y,k=[int(i) for i in input().split()]
  x_sum=x*k
  y_sum=y*k
  if k%2==0:
    print(0,0)
    k-=1
  c=1
  while k>1:
    print(-c,-c)
    print(c,c)
    c+=1
    k-=2
  print(x_sum,y_sum)

why this not working for A

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

5 4
7 5 2 5 4
0 0 1 0 1

13

???

Why in problem C 4th example it's 13 ?

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

    You spent all 4 op on 4 then you get: 2 5 5 7 8. The answer=8+5=13

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

    Apply operation on the last element 4th times it becomes 8. Removing last element the median will be 5. So 5 + 8 = 13

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

    If you use all your operations on a[4] (initally 4), it will become 8.

    The rest of the array is [7, 5, 2, 5]. Median is 5. So, answer is at least 13.

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

    pick 4 and spend k = 4 on it. The median is 5 (2, 5, 5, 7). So answer is 4 + 4 + 5 = 13

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

After this contest, I will never look at score distribution again.

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

Nice, well-balanced contest. Also felt like "real" competitive programming (too many contests feel like math these days).

Well maybe B-C gap is a bit too large but C-D-E1-E2 is well-balanced imho

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

Oh my God, I only have 15 minutes to do problem E1, and because I was in such a rush, I didn't realize that the complexity of my code is $$$O(n*log^3n)$$$. Maybe if I convert the segment tree to a sparse table, I'll get AC.

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

    $$$O(n * log^2n * log \max)$$$ passes with iterative segment tree

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

      Maybe my implementation is bad because I wrote around 100 lines in a very rushed time (< 10mins). Unlucky for me this time.

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

    I also had the same complexity and did not realize it at first. I ended up adding a bunch of heuristics and it passed pretests in 2 seconds (out of 4), still may fail systests though. I am not sure if those heuristics improved asymptotics. I kept segment tree.

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

worst contest i ever participated in. i acidentally sent my solution where arrays were too small and i got RTE on test 5 and i placed 6000 instead of 3000 because of that. its a skill issue, but still crazy

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

    Messed up with output on A, found it's failed on 1 pretest only after ten minutes :D Kinda feel the same...

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

If this is the level at which C is going to come i don't think i will ever reach expert

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

Almost submitted C, found the error in the last minute but had 5 secs left to submit..

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

I was ready to solve C before the 1 hour mark, maybe even solve D and get back to expert. Let's just say I was too naive hahaha

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

    as someone who did that, it would place you closer to CM in ratings.

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

      Oh wow, yeah... this Div2 is so broken, some past few contests I solved A. B, C too slowly and couldn't get D, my final placement for those contests is lower than this one where I only solved A and B lmao. Codeforces contests can be really random sometimes...

      → Reply
»
2 years ago, hide # |
 
Vote: I like it +58 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can't do C :(

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

Has anyone observed in the last 20 min, that accepted submission in C increased by 50% from 1K to 2K?

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

Felt like this div2 had 2 As and 4Es....

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

Yaaaay I solved C lol! I'm so happy!

Just choose one of two options:

  1. Greedily choose the largest a with b = 1 and use all k on it.
  2. Use all k to make median as big as possible (binary search).

max(ans1, ans2) is the answer.

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

Happy to solve C, get the logic in 20 min but take an hour to complete code.

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

Interesting round. The solutions end up being so simple you almost feel ashamed for spending so much time on the problem lol.

Also, C might be more difficult than what I've seen in the previous rounds.

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

What were all these testers doing?

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

C was a long implementation, atleast for the approach that I thought T_T

imho C shouldn't be this long implementation based problem, but other than that cool round, infact I love how C boils down to a simple solution

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

terrible contest, i dont really see your balance setting on Problem C. Maybe you need more preparation on testing your problem. BIG DISAPPOINTMENT

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

use 15 minutes to think about C and use 2 hours to code and debug it

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

Can anyone tell how binary search can be used to find the max median in C?

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

    Possibly use the same idea as the problem D of the last contest.

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

    OK... so here is the my idea for the whole C...

    1) Sort the array $$$a$$$(Try binding with $$$b$$$ to make coding easier);

    2) Assume the index of median of $$$a$$$ is $$$i_{mid}$$$, the median of $$$a$$$ is $$$median(a)=MED(a)$$$.

    When no operation can be done($$$k=0$$$), the answer should be $$$max(a)+MED(a)$$$;This can be shown that:

    2a) Choose the last element, we get the score $$$p_{max}=max(a)+MED(a)$$$;

    2b) At index $$$i \lt =i_{mid}$$$,we select $$$a_i \lt =MED(a)$$$ and delete it , the median may change to the $$$a_{i_{mid+1}}$$$. But after all the answer will be $$$a_i+a_{i_{mid}+1}$$$. Since $$$a_i \lt =MED(a)$$$ and $$$a_{i_{mid+1}} \lt =max(a)$$$, This is not the answer;

    2c) At index $$$i \gt =i_{mid}$$$, deletion won't change $$$MED(a)$$$, so $$$p_i=a_i+MED \lt =p_{max}$$$;

    3) Then we are allowed to do operation. Obviously the answer will just get larger. Since the answer is contributed by two parts: one element and one median, the intuition is that:

    3a) we increase the element;

    3b) we increae the median;

    3c) we increase both the element and median;

    4) Assume after optimal operation, the final array become $$$a^\prime$$$.Then we find that:

    4a) 3c) will never be the optimal solution.(Little hard to find tho...). From $$$p_{max}=max(a^\prime)+MED(a^\prime)$$$, we know that if we increase the $$$max(a^\prime)$$$ by 1, $$$p_{max}$$$ will also increase by 1. At the same time there is no assurance that increase some element in the array $$$a$$$ will change $$$MED$$$ (if changed, increase at most 1). Just to make it clear that increase the $$$max(a^\prime)$$$ is more effective.

    4b) So if we only change the $$$max(a^\prime)$$$, we bet all the operation on it. This can be done by increase one available element in $$$a$$$ to $$$a+k$$$ and calculate the answer with $$$O(n)$$$ or even $$$O(1)$$$;

    4c) if we only change $$$MED$$$, $$$max(a^\prime)=max(a)$$$ will be fixed and won't change ever.

    Then all we need to do is to find the maximum reachable $$$MED$$$ in the $$$n-1$$$ size $$$a[:-1]$$$ within $$$k$$$ operations.

    One possible solution is that Binary search the $$$MED$$$ through this way:

    Given the target $$$MED$$$, we iter through the $$$n-1$$$ elements and count all the element smaller than $$$MED$$$ while recording the operation needed if the element can be changed to $$$MED$$$. After the iteration if we find there are more than $$$int(n/2)$$$ elements smaller than $$$MED$$$, then we should use the operation to decrease the number until less than $$$int(n/2)$$$.

    Obviously we should change the largest element as possible to reduce the operation needed.

    Finally if $$$op \gt k$$$ or $$$cnt$$$ can't be reduced to $$$int(n/2)$$$, $$$MED$$$ is unreachable. Otherwise reachable.

    Wish my explaination could help you. If my solution is wrong just hack it..

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

Whoever created C deserves capital punishment

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +9 Vote: I do not like it

Didn't solve C, too difficult for me (`o`)=3

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

Please let us know if an author is indian. I will skip contests which have indian authors. PS : I'm Not tryna be racist, but indian authors like too much maths and observational trick problems.

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

finally get true purpose of the author posting ape pic

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

Most imbalanced and disappointing round ever...

Any idea for Problem — C

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

    key observation:

    if b[i] = 1 then there is no difference between in action (increasing value itself vs increasing median) so we take a[i] + k + (median after remove a[i])

    if b[i] = 0 then we need to take a[i] + (median after remove a[i] then use k operations to maximize the median) and it can be shown in case of b[i] = 0 we only need to consider one case where a[i] is max

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

      Thanks for the good observation, even so after this we have to solve median problem by using k to divide accumulation result of binary search on (a[i] having b[i]==1) to have the final answer though

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

cool round FST on A :)

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

I struggled so much on B when all people did it in less than 5 minutes it took 30 minutes how are you guys able to guess this thing in a seconds ? can you tell me what did you think when reading the problem

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

FST on A, whyyyy?

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

i think i can understand the meaning of cry now lol

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

Submitted C in last few seconds,I have even no time to check it:(

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

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

Cry made me cry today

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

Hi, can somebody please explain why my submission gets WA? 275619036

When I change the line

int lo=0,hi=1e18;

to 

int lo=0,hi=1e10;

I get accepted, but I don't see why that would cause problems? (I define int as long long)

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    I think the variable used to be overflowing.

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

    a better way to get a hi value without any overflow problems. create a function $$$ f(x) $$$ which return true if x is a valid option in binary search or not. (you cannot create it if you want but it looks cooler and nicer). then do this

    int lo = 0, hi = 1;
// f(x) is of form 0000011111 then do the following
while(!f(hi)) hi *= 2;
// f(x) is of form 111110000 then do the following
while(f(hi)) hi *= 2;

    This ensures we get a valid hi value without running into overflows

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

cry definately made me cry lol....Didn't expected to get back to pupil after grinding 1600 rated problems rigorously for past one month.....

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

This code

This code of mine was wrong so I resubmitted because this code fails for: 1 10 0 20

Don't know how this code later got accepted. Please check into this.

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

The number of correct submissions going from ~1000 to 2000+ in the last 20 minutes totally not suspicious?

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

hard C.

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

Do we have editorial for this?

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

Aside from the difficult C, I think the description for E was also a little too complicated. I mean, this kind of problem would be much more understandable if the legend has a more reasonable story behind it, rather than using all the mathematical formulas to be extremely formal.

For example, this problem can be easily modeled as each $$$a_i$$$ denoting a power of the $$$i$$$-th character and it can absorb either the $$$i-1$$$-th or the $$$i+1$$$-th character's power if the $$$i$$$-th one has greater or equal power. Then the question is to simply find all the ones that can possibly survive to the end. In this way it's easy to reason why this process has to happen, and is much more simple than explaining this process with an array and a set.

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

275593102 Why does it fail? (Problem A)

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

I got destroyed by this contest. Still I must admit that problems were interesting.Thank you for the round.

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

I really hate it when it gives pretests passed but wrong answer later,just demolished my rank.

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

"All wars is deception" Sun Tzu, The Art of War

and ofc... "Whatever you do, never reveal all your secrets in a Youtube video.. you fool!" Sun Tzu, The Art of War

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

That C was something...

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

So many W5 in A.

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

Can someone help me why 275686807 is failing on test 15 ? I'm trying to remove each element. If the removed element corresponds to b[i] = 1 then adding k to the removed element. And if b[i] is 0 at that index then binary searching on the median to maximize it with k.

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

How beautiful the problems are.

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

satyam343 sum cry

Could you guys consider reviewing my C solution once again please? While I saw the similarities and won't deny their existence, you can check my unofficial submissions to see the Binary Search on answer codes I have been writing before which also match the syntax used in that particular program. The only difference is using auto instead of my normal loop (which I had used a day before on some spoj and leetcode problems). Rest is just similar logic for binary search because that's how I have been writing binary search till now.

I have been accused for similar submission in this one particular problem before too however that's not the actual case since it's just the nature of the problem that gave similarities.

The template used is unique to me as well. Also, I have never got any skipped solution before this (never cheated before) and you can see my rating graph also looks normal with certain ups and downs unlike those of cheaters who go straight up. There have been contests where I have solved just 1 problem due to poor temperament as well which wouldn't be the case if I cheated my way through here. I am aware of the fact that past records don't really prove that a person can't cheat in future but they might help you confirm if my growth is organic. I'd request you to review it again in an unbiased way (Not calling you biased but from what I have observed people on this platform jump to conclusion too quick once someone is accused, not realising the difference between accused and convict).

I am also ready if you decide to get my account banned if genuinely found guilty. Another thing I would like to bring to your notice is that solution got a lot of similar submissions. Now while this might seem an evidence for the counter, I would want you guys to notice that only 2000 people solved it in the contest. So was it like 60-70% people cheated in that? And if it leaked at mass scale then why did it have just 2000 submissions while other leaked codes have 10k+? Again not a statement just an open ended question.

→ Reply