jampm's blog

Codeforces Round 978 (Div. 2)
By jampm, 2 months ago, In English

Hola, Codeforces!

We're glad to invite you to take part in Codeforces Round 978 (Div. 2), which will start on Oct/13/2024 22:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Some problems will be divided into subtasks.

This round is based on day two of the Mexican Olympiad in Informatics (OMI) 2024.

Please note the unusual starting time.

The team of writers is conformed by JuanPabloAmezcua, SebR, Marckess, and myself. We have spent a ton of effort setting the round as well as the Olympiad, we hope you enjoy it.

(This is our logo, cookie points if you can guess the names of the two characters in it)

The team would like to thank:

Score distribution: 750 + 1000 + 1750 + (1750 + 2000) + (2250 + 1000)

We wish you happy coding and good luck to all participants!

Winners Div 1:

  1. tourist
  2. ecnerwala
  3. neal
  4. maspy
  5. 244mhq

Winners Div 2:

  1. tko919
  2. thanos_2
  3. moonpole
  4. vgoofficial
  5. hashman

First solve for each problem:

UPD 1: We have added new testers and score distribution.

UPD 2: There is at least one interactive problem, so please read the guide for interactive problems if you are unfamiliar with them.

UPD 3: The editorial is ready. Congratulations to the winners and first solves for each problem!

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

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

As a problem setter, I hope you enjoy the problems ;)

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

as a writer, i want to go to sleep

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

There were 6 days gap before 14th october and have 4 days gap till 19th october . I am wondering why 2 contests are going to be arranged in the same day!!!

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

Wow. After more than 2 years of him dreaming about it (and me scamming him), the time finally came for jampm to become a Codeforces problem setter. I'm so proud of him and happy I could help with testing.

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

    You did scam me hahaha. I met some of your students and they asked me for an editorial of a problem I gave you LOL (you had my consent to scam though :).I wish we can do a round together eventually bro, thank you for always being such a cool and supportive friend :))

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

jampm round orz

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

Contest start at 03:35am in China.Can't participate o(╥﹏╥)o

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

    sleep early and get up on time o(╥﹏╥)o

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

    It is a nice time actually. Although you might not be used to waking up early

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

Mordecai and Rigby

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

The contest will start at 01:35AM(at such a nostalgic time) in Bangladesh. Wish to become specialist at least.

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

Are unusual starting times and late score distributions a recent trend?

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

Thanks for bringing finaly the problems of the Mexican Olympiad in Informatics to codeforces jampm , JuanPabloAmezcua, SebR , Marckess and all the ones who contributed to the proyect.

Hope you enjoy the round!

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

Expert this round ? lezgo

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

2AM in Vietnam and still participates :) I'm taking part in ICPC Vietnamese southern 2024 contest 12 hours before this round, what a busy schedule.

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

As a tester, I really liked the problems!

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

Finally a better time :)

What is the score distribution by the way?

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

"T" AND "C" ARE THE TWO CHARACTERS IN POSTER..

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

As a participant who read tester's comments i think it will be a good round ;)

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

"This is our logo, cookie points if you can guess the names of the two characters in it"

I know really well one of them is Karel but who is the other one? I have some clues but not sure. Now can I have real cookies?

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

    Did you say “cookies”?

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

Omg JuanPabloAmezcua Round

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

Why contest at odd times becoming common these days?

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

    Because Olympiads usually happen this period

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

As a tester, I tested after the announcement was post :pensive:

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

As a tester, I can say the problems are interesting to solve and highly recommend you to participate.

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

Whatever happens, I am not missing tomorrow's contest! I already feel so bad for missing last two contests.

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

bad starting time for Chinese.

Because it's bed starting time for Chinese.

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

As A participant...

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

contest start at 2:35am in Vietnam...i cant participate:(

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

3:35 for UTC+8. I need to sleep early and get up early to participate in :)

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

Won't mind changing the sleep schedule to get to specialist! (Someone who already sleeps at 4Am)

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

Finally a Mexican round ❤️. Muchas felicidades al COMI y todo el equipo detrás porque siempre ponen problemas muy chidos en las OMI's, y sé que implica mucho esfuerzo. ಥ⁠‿⁠ಥ

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

Can the round starting time be extended? I think many asians will agree.

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

    But many south/north americans will disagree.

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

Does Mexicans have their own judge site for practicing problems?

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

    It's like an Latin-American site that have problems in spanish, mostly we use it for introductory problems and contests (Omega Up)

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

I wish you all best luck and wishes thank you for your efforts and goodluck for everyone

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

I hope i will be specialist after this round.

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

during the contest all of Asia and east of the Europe are slipping then who is awake to compete?

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

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

    Contest is based on Mexican OI. Who do you think?

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

      they could start the contest 2 or 3 hours earlier so the most of countries that are good in IOI can participate in the contest and wtf so many people cried and down voted my comment did I say something bad?

      and contests like this are an unfair way to increase rating of the participants in some countries

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

        yes, mexico should shift its OI to cater to non-mexican participants.

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

          Who cares about IO this was a rated contest for any div2 if they want to participate in day time in Mexico they could release it as a gym

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

            fym "who cares about OI" this is literally a mexican contest, they have no obligation to release it as a div2 contest but they did. if you want to participate in the contest at daytime take a virtual.

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

Where are the point values?

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

    dunno, probably they havent decided on some of the problems yet(?

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

Is this contest IOI formatting?

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

I received an e-mail a few hours back, saying that the round starts on Sunday, October, 13, 2024 19:35 (UTC). Please resolve the discrepancy, if any. Thanks!

Nvm, it was a misinterpretation on my part :-/

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

01:35 am ??? nah man i will drop dead by the time it gets started.

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

Nice but why does the timing of the competitions continue getting weird and weird

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

Score distribution?

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

In China,the time is 3:35.Even in Russian time, it is still 22:35.Is it free time for Russians?

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

Score distribution ??

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

1:35 in Bangladesh.

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

Reveal the score distribution please..

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

Zzz

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

Won't be able to participate due to the timing T_T Anyway good luck to all of ya who'll be participating...

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

I hope i remain a specialist after this round.

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

Bad timing for Indians.

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

I think this is the first round in the history of Codeforces when there will be no cheaters because time is unusual. (At Night)

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

im in UTC +7, i mean i need to take a sleep then open laptop in mid night to join :)

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

Won't be able to participate because of timing.

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

god bless this round, let there be a 2-minute delay

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

Today's contest starts at 1:30 am in Bangladesh :3

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

OK...Good Night

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

glhf

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

can't i register in between the contest?

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

less than 7000 people made a submission lol. i wonder why

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

How to solve B??

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

    ye — kept getting TLE

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

    $$$answer = max(a_{max}, \sum^n_{i = 1}{\lceil \frac{a_i}{x} \rceil})$$$

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

      but why though?

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

        The $$$a_{max}$$$ part is obvious, however the second part is pure guesswork. I had already given up on the contest but wanted to submit this solution just on the off 0.01% chance that it is correct.

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

        You can easily put all $$$a_i$$$ in priority queue to solve it. Consider that we always pop first $$$m$$$ types. For each type we minus $$$1$$$ and push in queue. After $$$k$$$ times, the rest types are less than m. We can get that the rest answer is the maximum for the rest. Following the steps, we can solve it with $$$ans = \max\left(a_{max}, \left\lceil \frac{\sum_{i=1}^n{a_i}}{m} \right\rceil\right)$$$

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

      The correct formula is: $$$answer = \max\left(a_{max}, \left\lceil \frac{\sum_{i=1}^n{a_i}}{x} \right\rceil\right)$$$

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

        I wonder, how did I get Accepted with a wrong formula, hmmmm?

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

Problem C is such a pointless DP exercise.

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

In D2, anyone knows how to use 3 operations when n=3? I writed tons of case work and can't solve it ;)

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

    I felt like D2 involves some graph theory. May be whenever there is some cycle detected, we have to stop...

    No Solid idea though. Just sharing my thoughts...

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

    Sorry for the delayed editorial, we (the team of writers) have also been hosting the Mexican Olympiad in informatics and monitoring both contest. Give us some minutes we'll finish it up.

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

    I think no, the number of all possible combinations of 3 players with 1 imposter is 12, while 3 operations will give you at most 8 different outcomes. You cannot make one to one mapping from the outcome to the three players.

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

    if in 2 queries you have no cycle -- there are still 3 possibilities for imposter, but only 1 query with 2 different outcomes left -> impossible

    if you have cycle in 2 queries and answers are different, one of them is imposter -> easy to see no rest query can give you who exactly is imposter (cause you know nothing about 3rd player)

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

Really loved the problems.

A-B-C are getting difficult day by day... It took me 1 hour to solve just ABC :|

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

how E1 is 2250 score huh

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

was it just me or B felt really hard. spent 1 hour 50 minutes on it and didnt proceed with anyything

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

Okay, who thought that C is a good enough for a div2 round? It is simply pointless implementation task.

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

    How did you solve it?

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

      consider i as the current index in the upper string and j in lower one , now there can only be 3 cases i exceeding j by 1 , j exceeding i by 1 or i and j being equal.. make 3 states of dp corresponding to one i and the three cases.. it will be an n*3 dp..

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

It's hard to undertand that more than 30 people made feedback and nobody noticed the huge difficulty of the problemset. Only 3 solved in problem D2 (tourist and rainboy getting WA), 26k registered users but only 7k could solve problem A, some people beeing about top1000 without beeing able to solve problem B. The problems were quite intersting (at least trying them), but completely unbalanced.

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

    I think the point distribution checks out. C is harder than a normal C, so it has 1750 points (more than usual), D1 is easier than normal D, so it has 1750 points (less than usual), D2 is worth 3750 points so it's harder than most D2F. B is oddly hard though.

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

      Agreed. B is very hard if one lacks attention.

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

        I think B is a problem that is very easy to overthink. I wasn't able to solve it, but the solution is the first idea I thought of (and rejected).

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

      A was difficulter that average A, not only by the really low AC, the time that took thus AC is a lot for an A too. B gives only 250 point more than A and it was quite difficult and C was annoying to implement but not that hard to see the DP. D2 could be harder than most D2, but... what the point of having 3 out of 7 problems that won't be solved by more than 30 people? Even red coders can't solved that problem, I feel it's not worth it a problemset like this. Maybe for a global could work better

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

        A is slightly harder than usual but fine. Hard A usually isn't a problem. C has annoying implementation, which is justified because it is worth more points.

        On your point that D2/E1/E2 aren't solvable for most people: just treat this round as a 5-problem round. Ignore D2 and E2 and it becomes a pretty normal round: ABCD are all doable and maybe E is slightly harder than usual. It's fine.

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

Problem B gave me new neurons.

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

C can be solved for 3 rows too!

Code courtesy of liympanda https://pastebin.com/mjcPwbAa

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

literally what is idea behind of C?

how to be good at problem like this, it's so hard

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

    us bro.

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

    C is a simple dp.. as we can't have 2 dimensions due to n being large to track both the first row pointer and second row pointer I just keep the first row pointer and the 2nd state being difference between first row and second row pointers.. The difference can never be more than 1 to be eligible for dividing districts.

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

can problem C be solved greedly ? DP was always at the back of my mind but I was too lazy to implement it(Maybe cuz am not very good at implementing quickly).

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

    idts, you've choices to make at each moment and that can't be decided greedily

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

wtf was wrong with B ;;

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

What is the proof behind answer in B?

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

    Suppose we have $$$C \geq \max a_i$$$ customers.

    Imagine a box with $$$C$$$ rows and $$$x$$$ columns. Filling up your box column by column is sufficient.

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

      and how do u know which car to put in which row?

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

        Fill up every column of your box from up to down. Because $$$C \geq \max a_i$$$, doing so ensures that you won't place two cars of same type into the same row.

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

          Thank you.. i tried with paper and pen using your approach.. It helped me upsolve this. First I did this below binary search that runs in nlog(1e16)

          bool isPossible(long long customersCnt) {
    if(customersCnt * fomo < totalCars) {
        return false; //as each CX can only buy maximum of fomo cars, even if everyone buys fomo cars we can't sell every car.
    }
    for(int i=0;i<models;i++) {
        if(customersCnt < carsCnt[i]) {
            return false; // I can't sell more than one same car to same CX
        }
    }
//true in every other case by placing cars in the order mentioned by mr_lolololol
    return true;
}

          Later I was able to easily convert this to O(n)

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

i will never recover from B's trauma

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

Felt like I'm giving a div 1 contest today

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

I'm still wondering why my binary search on the answer solution didn't work on problem B. Can we say that the minimum "mid" >= max(arr) and mid * x >= sum(arr) would suffice?

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

B made me feel empty.

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

In question C, 2nd test case, shouldn't the answer be 4?

We can divide it into 4 districts such that each one has 2 Js.

I wrote the solution but I didnt see test cases and now nothing makes sense,

Edit — I have to look for As and not Js. I am way too much sleep deprived, -_-

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

Why were A and B so hard? If they are going to be this hard, there should be more div 3 contests.

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

I solved problem B with binary search.

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

    I'm still wondering why my binary search on the answer solution didn't work on problem B. Can we say that the minimum "mid" >= max(arr) and mid * x >= sum(arr) would suffice? Is this what you did?

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

What is the solution of D1 ?

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

    my solution was to group all people in groups of 3(ill explain how i handle if n%3!=0). so for each group of 3 you query 1,2 2,3 3,1 . and then lets say the type of the 1st guy is 0. then the type of 2nd guy and 3rd guy is fixed. and then you can check if the 3rd query contradicts the type of the 1st and 3rd guy. if this happens then you know that the impostor is one of these 3 guys, and you can basically brute force the solution. and if n%3==1 and we dont find an impostor then its the n-th guy for sure, and if n%3==2 you can just check both with the first guy, since we know the 1st guy isn't an impostor and find out which one is the impostor. this works in n+ 2 queries at worst. there is a simpler solution that ive seen though

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

    Consider comparing two players with each other (ask each other about the other one). If the results of the queries are the same, then both are either knights or knaves. If the results are different, then one of them is the impostor. To find out which one is the impostor, compare them with a third player. So now, you can compare player 1 with player 2, then player 3 with player 4, etc. until you find the impostor. Submission

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

    u can make groups of 2 people, u make they answer query about the other, in this groups of 2 if the answer are different then the impostor is one of them (u use n queries or n+1 and reduce the impostor to 2 candidates) then u pick one of those 2 and make a group of 2 with a third one, if the answer are differents then u have the impostor, otherwise the impostor was the other.

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

    Thanks. Got it.

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

C is the worst dp problem i have ever seen

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

    Maybe It's a div3 D or div4 E , nonetheless you need to get used to implementation to tackle such:)

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

B = guessing the answer and hoping it's correct.

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

    not really. It's simple maths trick, it took me more than 20 minutes to prove this trick with pen and paper. Not everyone guesses. Guesses won't get you far.

    Only mathematical proofs and intuitions will.

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

      can you explain your proof?

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

      how did you prove that trick, like i used that trick in an earlier problem where i was not able to come up with it so this time i knew after sometime what do but still i am not able to prove it

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

        Try thinking this way,

        0) N < K : This is very easy to understand. If the salesperson can convince to buy 'K' distinct items, then no matter what, we can Never sell 'K' items to the same customers ( since N < K ) . In this case, it is easy to see, ans is just Max of an array ( Because, everytime we will sell as many as possible items to the customer ).

        1) N == K : Here also, similar logic like above. answer will be Max of an Array.

        2) N >= K : This is crucial and tricky part. Implement Greedy logic on the sample test case [ 2 , 2, 3 , 3, 5 , 5, 5, ] for K = 4 . It is easy to see that, it is optimal to sell the items, which has the highest frequency. Everytime we pick top 4 elements from this array, and reduce their values by '1' and then again sort the array. After 2 operations, we will get this [ 2 , 2 , 2 , 2 , 3 , 3 , 3 ].

        This is where I got the intuition. CONSIDER A SORTED MULTI-SET, WHERE WE ARE ALWAYS REDUCING 1 from TOP K ITEMS. How many operations it will take, to make the set empty ?

        Every time we reduce 1 from top K member, the sorted set will sort itself and pick the optimal 'K' values in next time. This way, you are ALWAYS REMOVING 'K' ITEMS from the set ( except for the last time, where you will remove remaining (SumOfArray % K ) items ). So

        answer = (SumOfArray / K ) + (SumOfArray % K > 0 ? 1 : 0)

        There is small edge case required, when the there is very large number in array, and we need to reduce that number every operation. To tackle this edge case, just take answer = max(answer, maxOfArray)

        This is how I approached the solution.

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

          I tried to brute force this problem using Multiset just like you said.

          but i took the $$$x$$$ biggest elements and substracted them from the smallest one and then reinserted the new values to the multiset and repeat

          why didn't this work ?

          285732512

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

            It won't work

            Counter Test Case : 

            1
5 3
3 3 3 3 3

            Reason : You are taking k largest elements and then subtract the minimum one from all those

            but the optimal way is to subtract 1 from each and now perform with modified k largest elements from the array.

            I hope it is clear. If not, then try to dry run the test I have given, you'll get it.

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

              READ AGAIN , what I have written.

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

                OK ok got it ! I haven't read your comment. Thanks for sharing

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

          Thankyou, I was able to get the intuition behind this.

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

          Ohk got it thank you

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

          @ papa-ka-para

          CONSIDER A SORTED MULTI-SET, WHERE WE ARE ALWAYS REDUCING 1 from TOP K ITEMS. How many operations it will take, to make the set empty ?

          why did you not brute force it? i did in 285718545

          what possibly went wrong?

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

            If your bruteforce is passing then test cases are weak. The values are from 1 to 10^9. BF solution shouldn't pass.

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

              no it is not passing. i was wondering why so I asked. Why though? isn't it like <= 10*(n) with n<=5e5 ?

              it is failing on some test case and i do not know what is wrong in doing this BF

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

      plz provide the proof, i cant think of it at this time

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

    B's easily provable, that's why it's B

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

    Video editorial by adaptatron
    Their video is for x=2 but same arguments hold here.

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

    I think this is a well known trick. i have solved something similar before, and I think it's not that hard to come up with the quick solution.

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

      Yeah, it is well known, nevertheless I haven't seen a well known proof (other different form the greedy algorithm: always taking first $$$x$$$ greatest elements) xd I almost solve it but I missed the lower bound $$$max_{1 \leq i \leq n} (a_i)$$$ part.

      I hope to see a good editorial with a proper proof for this kind of problems.

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

        TLDR : just fill stuff cyclically, and it can be proven to be good

        We want to prove that ans = max(ceil(sum / k), max(a[i])) is achieveable. Consider "ans" number of boxes (0 — indexed) each with capacity x

        We do the following process : 

        p = 0
for i from 1 to n : 
   for j from 1 to a[i]: 
      put(type i in box p) 
      p = (p + 1) % ans

        This will always provide a valid arrangement. Why?

        1) First condition : No box will have more than x things, well this is obviously true because ans >= sum / k, and we fill stuff cyclically

        2) Second condition : no two things of same type end up in one box Proof by contradiction : assume that two things end up in same box, then it means that wherever we started filling type t, we returned back to it after cycling through everybody else. Therefore, a[t] > ans, but ans >= max(a). Contradiction

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

    just binary search on the answer

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

    Donno Why So many people are complaining about b. It is simple either we need max(arr) number of customers or total/k which ever is maximum. simple to prove it.

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

    Binary search always works here , if u get to this point(how to check for BS), mathematical formula makes much sense(and provable!)

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

Wrong Answer on pretest 2 for D2 :(

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

What was the problem with B..(am I wrong or they)??

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

How to solve B???

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

    its quite standard problem (most time you've seen of breaking into two groups) 

    cout <<1ll*max((sum+x-1)/x,mx) << endl;
    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://leetcode.com/problems/domino-and-tromino-tiling/description/ problem C looks much similar to this one, a DP exercise basically transformed to a new question!

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

Why did Problem B have the condition x <= 10?

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

    i got WA on pretest 2 by doing something with a vector of size x, so maybe its to trick people? if i saw x was up to 10^4 or smth, i wouldnt waste 2 attempts on that, so it could be just to confuse people

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

Can somebody help me with the Problem B, please? I don't understand, why I'm wrong. P.S. I know how to solve it correct, but I just so interested in reasons my "h2h" solution doesn't work.

https://mirror.codeforces.com/contest/2022/submission/285743640

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

My solution(285744957) for E2 using binary search to check when the answer is 0 got TLE. Is that a constant issue or did I write something wrong?

upd: It is a constant issue. I got accepted after removing some useless edges. See 285745386.

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

    This was the first solution I came up with when thinking about the problem. There's also a couple of alternative solutions. There's also a way of solving the problem online in $$$\mathcal{O}\left(n\log(n)\right)$$$.

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

    Mine (285739542) got TLE on Pretest 21 (technically only an E1 solution, but easy to make an E2 solution from it) — would also like to know if it's because of python or if there's a way to do it faster (in particular, I'm suspect of my test function, which is just a BFS looking for a cycle, and doesn't update anything).

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

What's the point of B? I've solve this problem at least twice before.

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

Thank you for the problemset! D2 is a very cool problem.

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

    Sorry for commenting on this thread, but could anyone pls clarify my doubt in D1?

    We know that if ask(i,j)!=ask(j,i) then one of them must be the impostor, However, I'm slightly confused as I queried on pairs that are distinct (i.e 1,n 2,n-1 and so on). Since the grader was adaptive, I declared j as impostor if ask(i,j)!=ask(j,i), since it's possible for any of them to be the impostor, and since the queries are independent of the previous ones.

    Why do we need to verify again which one is the impostor once we get the above condition?

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

    Can you explain your solution to D2?

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

      For $$$n=3$$$ you can find out on paper what is the best strategy, and it turns out $$$f(3)=4$$$. For all other $$$n$$$, I made a strategy such that $$$f(n)=n$$$. Basically you can always take person $$$1$$$ and $$$2$$$, do queries $$$1 2$$$ and $$$2 1$$$, this detects the impostor. If you detect it, do two more queries to find out which of the two it is. If not, you reduced to a subproblem of $$$n-2$$$ people, and used $$$2$$$ queries. For $$$n=5$$$ and $$$n=4$$$ you need to write a special case which does the querying in $$$n$$$ moves. For $$$n=5$$$ the main trick is first querying $$$1 2$$$,$$$2 3$$$ and $$$3 1$$$. This lets you notice if impostor is one of $$$1$$$,$$$2$$$ or $$$3$$$.

      Proof sketch of the lowerbound on $$$f(n)$$$: Lets look at the queries as directed edges that get added to a graph. If there are $$$n-1$$$ edges placed, then some node has indegree $$$0$$$, and some node has outdegree $$$0$$$ by pigeonhole.

      Case $$$1$$$: If there are two different nodes with either indegree $$$0$$$ or outdegree $$$0$$$, then there are still multiple options of where the impostor could be, so if we always gave queries that are consistent, never revealing the impostor, the player cannot know where the impostor should be.

      Case $$$2$$$: If the indegree $$$=0$$$ and outdegree $$$=0$$$ coincide, then the graph must look like a bunch of cycles and one isolated node. If we make sure that at the $$$n-1$$$'th query, if this query closes a cycle, and we would end up in Case $$$2$$$, we give an inconsistent answer now, such that the impostor is inside some cycle of $$$\geq 2$$$ nodes, then the player cannot know which of the nodes the impostor is in,

      This proves $$$n-1$$$ queries are not enough to know exactly where the impostor is. And we have a strategy for $$$n$$$ queries, that does find the impostor, except for $$$n=3$$$ which is a special case.

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

I can swear I saw something super similar to E1 before (possibly but not necessarily on codeforces) — might have been sum instead of xor but it was the same underlying task of either finding a contradiction or counting the unforced cells by merging row restrictions when they share at least a column, does anyone remember any similar problem? Also it's NOT the atcoder one (Grid Integers)

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

    Maybe Extending Set of Points? I found it very similar to this one.

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

    Found what I was thinking about: Tick, Tock !

    The condition here is being able to make all cells equal by adding 1 to either to an entire row or an entire column, which ends up being equivalent to each subgrid having equal sums of their opposite corners (a[i1][j1] + a[i2][j2] = a[i1][j2] + a[i2][j1]). Other than that it's the same idea — some cells are not occupied and we need to count the valid ways to fill them.

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

Can someone explain to me why my solution for problem b is wrong which case could give the wrong and ?285742700

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

Just solved B (literally by luck), This is the most problem that ever made me mad, I hope that the tutorial will show why this solution is valid

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

D1 is much easier than C (they should be swapped)

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

    I agree, but C is easy to think about but hard to code.

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

    Having a C2 as the hardest problem is rather strange

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

B looks like a standard Q. Have a gut feeling that I have seen it before as well.

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

I have seen that many people are solving problem B with the following approach :

Use Max Heap priority queue and take k largest elements from the array and then subtract minimum from all k, then push non zero elements into PQ, and continue until PQ is not empty. (Even I have tried this during the contest)

But this won't work. Let me Explain why.

Counter Test Case :

1
5 3
3 3 3 3 3

Reason : You are taking k largest elements and then subtracting the minimum one from all those

but the optimal way is to subtract 1 from each and now perform with modified k largest elements from the array. (But this will give TLE because arr[i] is up to 1e9).

I hope it is clear. If not, then try to dry run the test I have given, you'll get it.

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

    Thanks! Increasing my understanding of this question comment by comment

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

    Would subtracting (min — 1) work?

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

      nope.....the optimal way is to subtract 1 from each of min(k, remaining>0) largest then again choose k largest from remaining.

      but this approach will not work because Complexity will be high

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

    Thanks so much for the clear explanation.

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

Why constraint for D1 is n+69, not n+1 or n+2? Is it a kind of misleading to n+O(log(n)) solution?

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

This is just a joke!

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

I can do both maybe it will help here as well

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

First solve :)

→ Reply