Pinely Round 3 (Div. 1 + Div. 2)
By TheScrasse, 12 months ago, In English

text Ciao, Codeforces! We're glad to invite you to take part in Pinely Round 3 (Div. 1 + Div. 2), which will start on Dec/23/2023 17:35 (Moscow time). You will be given 9 problems and 3 hours to solve them. One of the problems will be divided into two subtasks.

The problems were authored and prepared by me.

Spoiler

We would like to thank

Score distribution: $$$500 - 1000 - 1500 - 2000 - 2500 - (1500 + 1500) - 4000 - 6000 - 6000$$$

We hope you'll like the problemset!

Update 1: the editorial is here.

Update 2: congratulations to the winners!

Winners and first solves

This round is made possible with the support of Pinely!

Pinely is an algorithmic trading firm, with its main focus set on high-frequency and ultra-low-latency trading. They have offices in Amsterdam, Limassol, Singapore, and Shanghai and are open for job discussions. Pinely is a team of winners, awardees, and medalists of various competitions in respective fields such as ICPC, IMC, HITB PRO CTF, and Google HashCode, etc. They constantly face various challenges such as developing strategies for trading, optimizing trading systems to achieve the lowest latency reactions to various market events, and saving and processing large volumes of historical data.

You can find out more about Pinely on their website or from their employees registered here on Codeforces. If you want to join the Pinely team, please send your CV to [email protected] or fill in the form:

Apply

Prizes: top 30 contestants and 10 random contestants placed 31-100 will receive a branded Pinely hoodie :)

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

Comments Comments (223)
| Write comment?
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

so many testers

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

As a tester, I tested

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

    As a tester, I also tested.

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

    as a not tester, i haven't tested

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

      as a not tester, i also haven't tested

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

        as a not tester, i also haven't tested

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

          as a not obnoxious person, i stop this silly chain

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

            people here are too sensitive

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

              People here are insecure. They downvote on any criticism and I love it

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

          as a not tester, I also haven't tested

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

As a tester, I tested (not a copy of the previous comment).

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

As a tested, I tester

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

last two questions worth 6000 points each?!

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

Two 6000 problem vs rainboy

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

Let's try to guess what franv did, something they can only share after the round.

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

As a tester, I am not allowed to write anything about the problems which includes my opinion of the problems.

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

omg 6000 problem round

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

As a tester, anyone who dislikes this round will be sent straight to the guillotine!

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

As a tester

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

As a tester, I tested

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

As a participant, I will participate in this round.

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

As a tester, I might have tested.

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

i want hoodie

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

As a tester, I liked the problems.

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

Yay! after solving ABC, Now i have to sit for 2 hours staring at the ceiling instead of 1 ಥ‿ಥ

Edit: Story checks out

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

There are rumours that the round will be unrated because aryanc403 hasn't scheduled the post contest stream yet. Is it true?

Tagging his superfan VatsLakshya for confirmation.

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

    haha :D .Maybe I'm a fan though :)

    maybe it'll be rated because that means aryanc403 is preparing to reach red .

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

      It's a busy day :)
      Maybe a leetcode stream because it will be short.

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

The Round seems Nice, I hope I can enter it and finally reach Master.

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

As a tester I liked the problems

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

    As a solver (participate) i hope... i will also like the problem set. Hope i will became pupil after this round. :)

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

never seen 6000 for a problem > combined score of first 4

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

Clashing with LC Biweekly. Got to skip this one.

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

Is it rated?

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

franv for something that I can only share after the round;

What do you think about this?!

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

Hope not to become Master after this round XD

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

As a test, I attest to the testset being tested.

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

Hoping Positive Delta and reach Pupil or Specialist

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

Hope to solve at least 3 problems :)

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

    as you are pupil and your atleast 3 problems solving probability is $$$1/9$$$ in div-2 contests your current aim should be to make sure you solve 2 problems atleast in a moderate time so that you can give yourself more time to try $$$C$$$ during the contest to give yourself more chance

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

      Thanks for advice. What I wanted to say is to be able to solve C more frequently (I have solved it only once in div. 2 :p). Thinking that I can solve problem that that is very unlikely is encouraging me to try it harder. I guess that is the first step of becoming able to solve it, right?

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

        Like for me it's like targeting atleast 3 problems in div-2 contest which I must do but and save time for $$$D$$$ so that I can have more chance in it , to me : solving 4 = good contest , solving 3 = average contest , solving 2 = bad contest , I think my $$$ 4 3 2 $$$ should be replaced by $$$3 2 1$$$ in case of you , and yeah gl for today

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

As a participant , I live.

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

Question to Pinely HR team:

Is it possible to work remotely in the company?

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

    I doubt a quant firm would let anyone work remotely for IP reason lol. They take it very seriously.

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

Can't wait trying to solve 4 problems glhf everyone

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

Hope to become Grandmaster to achieve my goals for 2023......

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

New Year, high ratings!

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

Finally university exams are over and I can peacefully give contests on cf.

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

    for me they are this next week but still gonna do contest on cf peacefully

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

everyone good luck

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

am I going crazy or has the score distribution changed at least 3 times already, huh?

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

Wow

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

I hope I don't have to change my profile picture after this round

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

    you need not at least as long as "magic" is there :)

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

They have already changed the score distribution 3 times, i see now why coordinating this round is so hard.

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

I tested the round, and the problems are very enjoyable to work on.

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

3hours which mean i must stay up to almost 1:30am cuz im in China,i think i will give up thecontest

...a little sad

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

Thx to all the testers for their contribution!

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

is it rated？

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

sunsh1ne tester — good round

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

can i join the contest without rated

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

as a non-tester, give me contribution

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

Have a nice contest everyone

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

As a participant, i registered

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

queueforces

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

Is it contest rated?

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

Amazing mathforces round """""""""""""iam really enjoying it"""""""""""""""""""

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

is it only for me or pinned song on problem D is actually Desert Ruins by eliteLAQ??? as a participant, i was violently destroyed by problem B, as a fe2 fan i like pinned song on problem D

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

Really great soundtracks provided for each problem.

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

A tiny bit too easy contest.

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

Now what did franv do?

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

How to solve $$$F$$$ in at least some polynomial time?

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

Nice contest, did ABC quickly, was close to solving D, but didn't had enough time...

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

WTF E ?

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

In problem D, when we are doing operations on x and want to make it to tar. Then won't there be cases where we partition it into y, x+k-y, and then recursively do operations on both of them?

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

As a rhythm gamer, B was the easiest ever opportunity to beat xi.

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

any hint for F1?

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

    Notice how much can a[i] differ from a[i-1]. Then do casework

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

      Can you give a hint for what to do after this?

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

Can someone please explain D?

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

    Imagine you have to change a[i] to an array of same value x and using p operations. So you have this expression: a[i] + p*k = (p+1)*x -> a[i] — k = (p+1)*(x-k). This expression happen when a[i]-k divided by x-k. Using gcd and greedy, you can get x-k = (+-)gcd(array(a))(minus or plus based on a[i]-k)

    Split 3 case: All a[i] < k, all a[i] > k, at least 1 a[i] = k.

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

      Won't there be case where I split a[i] into y and a[i]+k-y and recursively do operations on both y and a[i]+k-y to get x?

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

Wow, what a round! First time solving div1+2 F, and first time actually using all 3 hrs, not just solving something and then staring at the screen

Thank you for an amazing contest!

I suppose DEF were really cool, though didn't solve E much

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

Super cool DEF. I just dont get why my F2 doesn't work when the solution is almost the same as F1 :(

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

    Can you explain your D solution?

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

how to solve B!I'm so sad!

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

    check for k= 2 ^(i) where 1<=i<=60

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

      wait why does that work

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

        think in terms of binary number

        iterate from least significant to right significant

        possible case: 1.all the elements have same bit 2.both 0 and 1 bits are present

        if for ith bit second case arises then remainder will be 0 and 1 only for k=2^(i)

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

        For k = 2^i, it is checking whether there are elements differing on (i-1)th bit. If we take first bit where (i-1)th bits are different then previous (i-2) bits are same, so we will be having two numbers 0 and 2^(i-1)

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

          Can't the mod value also be (2^i)-1 and (2^(i-1))-1?

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

      I get it! it's easily solved by converting to binary.but why can we think of binary?

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

    I come up with a solution that passed all my test cases, but it's giving me a Wrong Answer (WA) on test case 2. I'm unsure about the underlying idea, but here's what I have so far: if there are both odd and even numbers in the set, then the answer is 2. However, if all numbers are either odd or even, then the answer is the gcd( all the numbers) multiplied by 2. This is the best solution I could come up with after about 2 hours of thinking and trying, but it seems to be incorrect.

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

      according to you, for the case:

      3 5 7

      gcd = 1.. then multiplied by 2, which is 2.

      3%2, 5%2, 7%2 = 1,1,1 which doesn't satisfy the problem requirements

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

        when (gcd==1) I made it 2 and then multiplied by 2 which is 4

        which will work in this case and any other case I could think of

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

      if all are odd then it has one number like 7 , 15 , 21 then ans is 2 and mod value is 1 1 1 , not satisfy the condition

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

how to predict rating change?

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

    you can use an extension named Carrot, it shows some predicted ratings on the standing page.

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

so hard(sad)

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

Fun round, thanks mister TheScrasse

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

Thank you for the great contest.

I really liked H, and I'm curious to know how to implement the checker for this.

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

    I think you can maintain BST for each odd/even index.

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

    I wrote the checker. We use two treaps, one containing the even indices of the array and one containing the odd indices. To perform an operation we just cut the corresponding ranges from each treap and then swap them (odd indices become even and vice versa).

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

      I got it. Thank you for preparing the problem.

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

Really liked C and D, at first glance neither looks like a problem that can be solved in polynomial time but they result in really cool formulations.

Also, I don't know if I love or hate that you put a problem with an actual exponential solution right after it xD. Btw, is there any way to prove that the number of good masks is $$$\lt\lt 2^n$$$ for $$$n \leq 19$$$ other than just generating them?

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

Besides my newbie performance, the music attached to each problem were out of this world!!

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

What the hell with E?? Seven very similar submissions, five of them TLE on test 7??? Moving the array from inside the function to the outside gets AC???

What's the intended solution by the way? Only have $$$O(\frac {\sum n}n\cdot n^4\log n)$$$ solution.

-update: I actually know the solution for $$$n>=20$$$, but am seeking for a quicker solution for $$$n<20$$$.

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

    If n>=20 you can press every button. For n <= 19 I generated all the good masks (masks of pressed buttons that result in less than n/5 lamps turned on). It turns out that there aren't many such masks, so for every one of them you can check if it's valid (if it is consistent with every constraint from the input). So the complexity is something like O(1000 * m)

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

    There is a simple insight : if you pressed all buttons then only squares indexed lamps are on, which mean $$$\sqrt(n)$$$ lamps will be on. With small n you just brute force bitmask, large n you choose all.

    In my opinion, E's statement is too misleading and too unfair for newbie. I thought that if you push button a and button b, both require you to push some button v then you push it 2 times, which violate the rule. I waste a lot of time on that, only recognize in like 5 mins left, my solution failed on the last second due to some stupid bug. If you're experienced you will realize this problem is impossible and realize you misread something.

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

238568063 Can anyone tell me why this submission for B exceeds TL. I expect it to be $$$O(n^3\cdot log(n^3))$$$. Is it not ? Or is it not passing because there is no constraint on n over sum of all cases ? $$$n^3 = 10^6$$$ only. Shouldn't it pass ?

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

    Well, $$$t \cdot n^3 \log n^3 \le 500 \cdot 100^3 \log 100^3 \approx 6\,907\,755\,278$$$ which seems to be too many operations for one second.

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

      Thankyou for answering. So, in general we always have to account for the number of tests per sample ? I had this misconception that multi-test thing is only to speed up judging-times and the TL is adjusted and set the same way it would be for a single-test per sample scenario.

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

        Not quite.

        Let's say your time complexity per test case is $$$O(n)$$$ and there are $$$t$$$ test cases. This means that wosrt total time complexity is $$$O(tn)$$$ for the maximum allowed values $$$n$$$ and $$$t$$$.

        If the problem statement gurantees that "sum of $$$n$$$ is at most $$$N$$$", then the total time complexity is at most $$$O(N)$$$. In this case, it often doesn't matter how many test cases there are per input file.

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

          I see. I shouldn't have ignored the line in the statement, that clearly said that there is no constraint on the number of tests. Thankyou.

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

    sir t= 500 , n = 100 then n^3 * t = 5*10^8 , so n^3log(n^3) take more than 1 second

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

      Hmm understood. Thanks a lot.

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

In problem E is it possible to quickly calculate the number of lamps that will be turned on after n operations? Or does the solution not require this?

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

    in E

    if(n >= 20) then sqrt(n) <= n/5 if you turn on all of the lamps the numbers of lamps that's on is sqrt(n) which is 1*1,2*2,3*3,4*4,5*5,...n*n

    what remain for u is what if n < 20 solve this with brute force

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

please can some one tell me is there any prerequisite for B & C or is it pure observation i don't wan spoiler. Thanks!

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

Approach to solve C? Anyone please!

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

    See,I can bet you are wondering if i sort both l and r in ascending order then taking the difference would work, but here is one case after which you can solve it by yourself,

    n=4 l=1,6,11,18 r=7,12,19,24 c=1,2,3,4

    It is already sorted, now if you take diff then it would look like this diff=6,6,8,6 Now,you will multiply the largest diff with smallest cost,so the score will be score= (4*6)+(3*6)+(2*6)+(1*8)=62

    but if you place a r[i] which is just greater than l[i],then the score would be less, start placing those r[i] from behind because its always possible to have the r[k] for those l[k] where k<i, It's the basic intuition.

    l=1,6,11,18 r=24,7,12,19 (start placing from behind)

    diff would look like this, diff=23,1,1,1

    now,if you calculate the score it would be score=(1*23)+(2*1)+(3*1)+(4*1)=32 only which is less than 62. So,insert all elements of r in multiset and use lower bound and erase after every iteration.

    I hope it makes sense to you.

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

      Thanks man, I had just the same approach just couldn't implement it:(

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

        It's totally fine,do upsolve to increase your confidence.

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

Bad contest,Bad problems, thanks for wasting our time.

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

Problem D is very cool))

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

One of the best contests I've ever had

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

For some reason, I wasn't able to view problems on main or mirror (mirror said something like "This problem doesn't have a statement"). Strangely, this message was shown only on the first 4 problems (I was able to view E atleast) on mirror, while on main I wasn't able to load anything at all. This happened for the first 10 minutes.

I tried opening CF on incognito and it worked fine, so I disabled uBlock and CF-predictor and only then was I able to load the problems.

Can anyone make sense of this?

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

Great round!

Appreciated the reference to 1656C - Make Equal With Mod.

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

Thank you for the nice problems! To me, the round was fun.

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

Kavi orz!

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

is the contest rated?

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

Can anyone hack my O(T*2^N*N) solution for E? https://codeforces.net/contest/1909/submission/238581537

The strategy is simple: Backtrack all possible combinations from switch 1 to n, not pressing first for each. Check if it violates any rule every time we press a switch (for smaller numbers, check if it's already pressed, and for larger numbers, set a must-press flag for that switch). Print the answer immediately if we find any solution.

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

    Thank you, it's uphacked now.

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

      Where do you see that it's uphacked? I believe that it's my hack, though it still shows me accepted on your solution and hack as pending
      On my machine your code works about 10s:

      igorjan {0} 1909 % clang++ -std=c++20 -DONLINE_JUDGE -Ofast 238581537.cpp -o 238581537
igorjan {0} 1909 % time ./238581537 < E.in > E.out
./238581537 < E.in > E.out  9,86s user 0,00s system 99% cpu 9,867 total
      Testgen
      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Right after you submitted the hack, I got a message from System that it's hacked, so I think my solution already got TLE. Perhaps there's some issue while it's being tested on the testers' solutions? (probably a tester's code also got hacked with it?)

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

In problem B how come the answer is gcd of differences between the numbers multiplied by two ? gcd would give the number which would make entire of the array same , but how come it being divided by two is the ans?

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

    since when we divide all of them by gcd, each are either even or odd, giving 2 distinct remainders

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

When will the rating changes applied?

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

FOR C QUESTION WHY THIS IS WRONG

sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); sort(v3.rbegin(),v3.rend());

for(int i=0;i<n;i++)
{
    int d=v2[i]-v1[i];
    c[i]=d;
}
sort(c.begin(),c.end());
int sum=0;
for(int i=0;i<n;i++)
{
    int a=c[i]*v3[i];
    sum+=a;
}
cout<<sum<<endl;
→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try this

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

    I had the same question for more than 1 hour. But later I understood why it failed!

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

somewhat got very lucky 238563505

and saved rating.. 😙

thank you

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

In my opinion, B was harder than C.(The gap is not big though)

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

    as a fake cm, i brick c

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

      been ridin with you since you were just a pupil, gotta give props to your hustle and the realness in your grind. Keep killin it!

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

after the rating update , magic changes got reversed

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

The most miserable thing is not that you cannot do problem E, but you realized that you can press all the buttons when n >= 20 in the last 5 minutes of contest.

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

My screencast and editorial (both in English and Russian)

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

Typically on rounds it seems that the easy problems are not always that fun / interesting, that was not the case this time! thanks to the authors of abc :)

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

In que 2 I am getting WA for this block of code can someone please help me with this: int fans = -1; int st = 1; int end = 42; while(st<=end){ int mid = st; ll ans = 1ll << mid; set s; for(int i=0;i<n;i++){ s.insert((1ll*arr[i])%ans); } if(s.size()==2){ fans=ans; break; }else{ st++; } } cout<<fans<<endl; Thankyou in advance <3

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

Can someone tell me that why the time complexity doesn't exceed in Problem 2 , like there are 500 test cases each with n ranges from 2 to 100 and in one test case we go from 2^1 to 2^57 then total number of operations would be 500 * 100 * 57 ~ 2850000 ~ 2*10^6 . time constraint is 1s and in 1s max 10^6 operations can be done. and can any one give me advise what to do in such situations because i got this answer in the contest duration and i didn't code it because of this time complexity.

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

-

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

thanks for the round, problem D directly hit on my weak spot, but it is quite satisfying when I successfully upsolve it and it is very interesting :D

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

i got fooled by testing system since my solution had (1 >> j) and it violated the range of int but testing system said it was wrong answer. Anyways i didnt lose any rating and changed every 1 to 1ll and it worked. Fun problems, cool songs, i liked the round!

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

Thanks for the great round and the strong examples on D! I had trouble with $$$= 0$$$ and $$$< 0$$$ values and would have gotten a lot of WAs without the last two.

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

    I couldn't figure out them (the 3 corner cases) during the contest :(

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

If my solution is found copied and my submission are skipped then why has my rating deducted for that contest the rating should be skipped. You have first removed the points awarded for the contest and then also deducted some points.It should not happen as contest is skipped for me

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

Is there a handsome guy who can help me？ How to solve F1? I cant understand the tutorial。

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

I don't understand what is happening. How zh0ukangyang is the round winner and two first solves but had delta -3321?

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

Congratulations to hoodie winners! In a few weeks, you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_hoodies.py
randgen.cpp
List place Contest Rank Name
1 1909 1 maroonrk
2 1909 2 jiangly
3 1909 3 FastFreeTask
4 1909 4 ksun48
5 1909 5 ugly2333
6 1909 6 Um_nik
7 1909 7 cnnfls_csy
8 1909 8 maspy
9 1909 9 HaitangSuki
10 1909 10 MagicalFlower
11 1909 11 -Eternity-
12 1909 12 hos.lyric
13 1909 13 ecnerwala
14 1909 14 duality
15 1909 15 353cerega
16 1909 16 SSRS_
17 1909 17 cmll02
18 1909 18 asdsasd
19 1909 19 antontrygubO_o
20 1909 20 yosupo
21 1909 21 E869120
22 1909 22 Xylenox
23 1909 23 Radewoosh
24 1909 24 OnO
25 1909 25 orz
26 1909 26 alireza_kaviani
27 1909 27 Nachia
28 1909 28 Ormlis
29 1909 29 H_stove
30 1909 30 QwertyPi
31 1909 31 noimi
38 1909 38 PubabaOnO
43 1909 43 StarSilk
49 1909 49 Roundgod
50 1909 50 jjang36524
51 1909 51 CJ_xde_pt
54 1909 54 Kuroni
63 1909 63 BalintR
75 1909 75 Nyaan
100 1909 100 Never-Ever
→ Reply