Pinely Round 4 (Div. 1 + Div. 2)
By ZhouShang2003, 7 weeks ago, In English

header Hello, Codeforces!

We are pleased to invite you to Pinely Round 4 (Div. 1 + Div. 2), which will start on 28.07.2024 17:35 (Московское время). The round will be rated for everyone.

You will be given 9 problems and 3 hours to solve them. There is at least one interactive problem, so please read the guide for interactive problems if you are unfamiliar with it.

The problems were authored and prepared by me.

We would like to thank:

We hope you will enjoy the round!

Score distribution: $$$250 - 500 - 1000 - 1500 - 2000 - 2500 - 3000 - 3500 - 4000$$$

The editorial is here.

Congratulations to the winners!

  1. tourist
  2. jqdai0815
  3. Radewoosh
  4. ksun48
  5. Rewinding
  6. hos.lyric
  7. jiangly
  8. Benq
  9. BurnedChicken
  10. Szoboszlai10

This round is made possible with the support of Pinely!

pine Pinely is a dynamic algorithmic trading firm with a presence in Singapore, the Netherlands, and Cyprus. We specialize in high-frequency and ultra-low latency trading. Our team of mathematicians, programmers, engineers, and computer scientists tackles everyday challenges like developing trading strategies, optimizing systems for minimal latency, saving and processing large volumes of historical data.

Working at Pinely demands exceptional C++ coding, algorithmic thinking, and mathematical intuition, attracting top talent, including winners and awardees of such competitions as ICPC, IMC, HITB PRO CTF, Google HashCode, etc.

Learn more about us on our website or find our employees on CF. To join our team, please send your CV to [email protected], even if you are not participating in the contest.

Prizes: The top 30 contestants will receive a branded plush pine tree!

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

»
6 weeks ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Hope I can get back to the blue in this round!

UPD: I will try again =)

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

Hoping for a good contest！

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

Hoping to lock in the day of the round! First this Codeforces round then Teamscode! Good luck to everyone on all of the contests!!!

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

First reaction: wow the plush pine tree is so lovely, but I can't reach the top 30 :(

Then, after some searching: omg it could be found in amazon.

pkbRMv9.png

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

As a tester, I tested the round.

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

    Did you get any compensation for no longer being able to compete for a plush pine tree?

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

Very nice round. I am a little bit upset because I tested so I could not participate officially.

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

    You can if you are Psychotic enough :D

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

      lmao

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

      Is that a reference to someone called "Psychotic" or what does that mean?

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

        I think it means you can't participate in the round unless you're insane :D

        upd. sorry check _inferno_'s comment for reference

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

        It is a reference to Dhruvil Kakadiya who was international master from India who used to set the questions and participated in the contests. This way he even got global rank 2 once (imagine an IM getting above many LGMs). His username was PsychoticD

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

As a participant, hope everybody good luck and win lots of pines!

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

    If the same comment was posted by some <= green, it would have 0 upvotes or maybe negative.

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

Hope I can reach pupil :)

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

Guys, scoring distrib pls pls pls

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

All the best Guys:)

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

As testers, jiangbowen and I tested the round.

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

    Why downvotes? Of course they are not the same person or Mike would have already banned one of them.

    Orz wmh.

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

    Why more downvotes? Orz wmh.

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

This round will contain some really challenging problems ig :)

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

As a participant, I will participate in the round.

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

potato

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

I really want to be a specialist, hope to get a positive delta :)

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

first contest as a pupil, hoping for specialist after this one!

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

Hope I can solve 4 problems!

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

Every time I see any Chinese coder from Zhou dynasty my mind reads Zhou Guanyu (avg F1 fan me :-))

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

    Hope the race gets over before 8pm tomorrow so i don't have to skip this contest :<

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

      Congrats to Russell and see you on the leaderboard :)

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

Scoring distribution when?

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

    do you mind explaining how you can benefit from scoring distribution? isn't the best strategy to always solve problems in order?

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

      For example, if D and E give same score or small difference and you don't like D you should probably read E to not waste time. Or generally just to see expected difficulty difference between problems.

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

I hope to learn more from this round of competition

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

Stop interactive problems :(

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

    Indeed, interactive problems are interesting:)

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

I have a question There is an indicators array of size n and corresponding profit array of size n. We have to select indicators in such a way that their bitwise or is <= k while maximising the profit. n<=1e5 k<=2^30 indicators[i]<=1e9 profit[i]<=1e9 Can someone provide an algo?

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

    isn't it just, we take out the indicators which have only those bits set which are set in k and then add all the profit? since its bitwise or it should always work

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

      No, because the bitwise or can be smaller than k also, so not all bits will match

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

        isn't that what you want? you wrote bitwise or <= k

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

          No, I want the profit to be maximised say k is 1111 in binary then may happen na that an indicator is 1111 but its profit is less than that of three other indicators which are 1,11,111

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

            you can take all the indicators. for e.g. here you can take all

            $$$ 1_2 | 11_2 | 111_2 | 1111_2 = 1111_2 $$$
            → Reply
»
6 weeks ago, # |
  Vote: I like it -56 Vote: I do not like it

speedforces loading...

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

Hoping to become green after this round

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

nob nob

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

tourist will win this round : )

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

Too difficult for me :(

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

Staring at D for 2 straight hours

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

Why so many boring detail Problems ???????
There's no interesting idea in A-F !!!
ARE YOU CREATING CHINESE COLLEGE ENTRANCE EXAM'S MATH PROBLEMS ?????

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

the best guess I made in C is that the best next step is x = sum of array / size of array

it seems to work but I'm getting wrong on test 2 so it's maybe not optimal

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

    It doesn't work the best is actually x = max(array) / 2

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

      I just hope that someone can tell us why and not just like most of the time where it's just a pure guessing

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

        Intuition is that you keep halving the biggest number — because smallest cannot become than x -, meaning that eventually everything will become 0 (as long as parity is equal and you choose ceil(max/2)). It will also take log2(initial max) steps.

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

    I did the same :(

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

Can someone please tell me what is wrong with this solution for problem E. If the graph is bipartite I play as Bob and just greedily color the graph, otherwise I play as Alice and spam "1 2"?

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

    your solution is mostly correct but when you play as bob the greedy is a bit more complicated

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

      Can you elaborate?

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

        let S1 be the nodes that you will color 1, S2 be the nodes that you color 2

        what would you do once you color all nodes in S1 (or S2)

        if you just fill S1 with 1 or 3 then S2 would be a really chaotic mess of 2s and 3s that might fail (and vice versa)

        to be more specific, once you color all the nodes of S1 then alice could just keep sending "1 3" and if S1 contains any nodes that's colored 3 then that's WA

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

          Yeah, but the hardest case is if the interactor only plays the same 2 numbers, if it plays the third, even easier. I colored it in the same way you check a graph for bipartiteness. I can't think of a counterexample

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

            then you could just pick all the first numbers into S1 and all the 2nd numbers into S2

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

    you should've spammed "1 3" I think

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

I hate constructives so much now

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

To continue the streak of "unconventional solutions", now with today's D:

  • If $$$n \le 6$$$, copy sample outputs.
  • If $$$n > 6$$$, output 1 2 3 4 1 2 3 4 ...
→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Did you mean problem D?

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

      Edited, hehe. I think I was absolutely drunk~

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

    it was really just that?

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

      Yes. I actually came up with a proof (sorta) before doing that.

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

        If you don't mind, can you please share?

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

          Nodes $$$u$$$ and $$$v$$$ if sharing the same parity will have an edge only when $$$u \oplus v = 2$$$. The remaining edges are always from one parity to another, i.e. virtually bipartite graphs. For large enough $$$n$$$, each parity will need $$$2$$$ colors, and thus maximum colors should only be $$$4$$$. $$$n = 6$$$ already reaches $$$4$$$ as most optimal ones, therefore all $$$n > 6$$$ should do the same.

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

    my solution was:

    observe that odd verticies will only connect with even verticies

    with the exception of u^v = 2 -> just alternate between a and a+2

    tho there's the edge case of n = 3

    so turns out the output still ends up as 1 2 3 4 1 2 3 4 1 2 3 4 ...

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

Pretty much the same problem as E: 1503B - 3-Coloring though it's probably just a coincidence.

Regardless, I really enjoyed the round!

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

D is the worst problem I've ever seen in my life.

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

Here's my thought process for C: Absolute Zero.

$$$10^9 < 2^{30}$$$. Therefore, either the constraints are bluffing and the optimal number of moves is very small (like 3-5), or the solution involves some binary searching like idea (where you keep on trimming the range in half).

Even if the constraints are a bluff, let's explore the binary search idea. If they want you to trim the range in half, what happens when you select the midpoint of $$$[0, 10^9]$$$ as the first $$$x$$$. Notice that every point can be at a distance of $$$mid$$$ on either side. Therefore, the maximum array element has been reduced by at least half. If you repeat this process 30 times by taking midpoint of $$$[0, max]$$$ (and let's do it 39 times instead just to be sure), then at the end, the array would contain identical elements. So you can use the last operation to subtract that identical element to convert it to zero.

Code

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

How to solve problem D?

The rough approach for E and F felt way more obvious to me, I've got zero intuition for D after trying it for 30+ mins.

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

    The only odd cycles in the graph must include pairs $$$(n, n + 2)$$$ where $$$n \oplus (n + 2) = 2$$$. So, removing just these edges, the graph is bipartite with the two sides being the parities. Then, we can 2-color each parity since the only edges between vertices of same parity are those of the first kind. This gives a 4 coloring for all $$$n\ge 6$$$.

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

      Oh wow, that's actually a really cool solution. I completely missed the importance of 2 being the only even prime even though I analyzed cycles for edges of 2 and 3...

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

    D is one of those problems (that I hate) where the solution is really simple but 99% of coders are unable to prove the greedy algorithm. For $$$n\leq6$$$ we copy the sample solutions. For $$$n\geq7$$$, we take the periodic sequence $$$1, 2, 3, 4, 1, 2, 3, 4, \dots$$$.

    PS can someone share the solution for E?

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

    The solution is very simple and stupid. I also wandered in incorrect direction for some time.

    1 2 3 4 1 2 3 4 1 2 ...

    $$$a \oplus (a + 4k) = \dots 00$$$ which is divisible by $$$4$$$ and hence not prime.

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

D much harder than E??? I stare D at 90min, while I spend 15min solving E.

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

    D > E, F in my opinion, the starting point for E (non-bipartite are definitely winnable for Alice) / F (answer is always yes for arrays with $$$\gt 63$$$ elements for $$$a_i \leq 10^9$$$) is fairly obvious to me.

    But I just spent ~30 mins working out cases and trying random stuff on D with no luck.

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

    D makes me feel stupid. It's so simple but somehow I used 1h.

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

[deleted]

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

how it feels to have no idea what the solution for D is after 2 hours of solving it:

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

F: Ancient Japanese knowledge is now blooming...
UTPC2011-G

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

Why is k = 1 and k = min(n,m) allowed in the input for G? It's just more stupid casework...

EDIT: Looking back i was just salty. The problem is fine, my code was just impossible to debug. Just recoded it today and it worked relatively quickly

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

    I have no casework in my solution. I actually had two WA2 from trying casework on K = N

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

Few samples for harder problems!

Problem E has only two samples with $$$n=m$$$, so when I made a mistake in my code(it plays $$$m$$$ rounds instead of $$$n$$$), it passed the samples and got wrong answer on test $$$2$$$! Spent two minutes staring it out.

Problem F,G both have only one sample??

For problem F, here's one similar problem (similar trick) on luogu, and it's in one of the recent contests.

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

For problem E, can anyone explain why 273228602 fails on Test case 1 (second test), even if my output matches for second test matches with the output given in the problem statement.

Code Link

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

Can someone give me a hint for D (not the solution)

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

hey Tourist why you so smart,

the way you solve problem is just pure art.

How are you so fast

You come first, I come last.

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

Problem E is a repeated problem Original Problem

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it +11 Vote: I do not like it

    I think the idea is just a somewhat intuitive approach that keeps popping up for this kind of problem. For example, this problem is an even earlier problem I set that uses the same key idea.

    At the time I came up with it, I hadn't seen any problem use this approach before, but since then I've seen multiple other problems use the exact same idea of "3-colour bipartite colouring with restrictions on when / how many times you can use a given colour".

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

n=1 on E was hell to debug for 2 hours, this is the worst i've tilted since this round lmao

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

ConstructiveForces

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

A<B<C<E<F<D ???

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

    A<D<B<C<E<F. Thus averaging out to intending difficulty.

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

GuessTrickForces :(

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

Thank you for the round!

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

what was C? and why am i getting WA in this

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

    In this case: 1 1 0 Your code would output 1 0 but the correct answer is 0.

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

      nvm figured it out.

      Any clue on why taking average of all the unique elements does not work at each iteration for subtracting doesn't work?

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

Poor experience

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

Feeling quite retarded , not able to get old form back. That's the thing with CP... if we stop practising. Performing in contest is a different skill. Anyways CP is best.

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

G is a great challenge to the player's guessing ability. But I don't like it. ()(())

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

This Round is the worst round i have ever seen

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

Where is $$$998244353$$$? X(

The fact that both H and I are solvable surprised me a lot. Strange feeling. Thanks for the preparing the round!

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

Thanks for the round! Maybe the best round in this year!

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

I really hate problem of D kind

guess until get it right

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

interesting constructives early on.

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

can some one tell the reason for problem C approach or what is your thinking process

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

    Think of a set of points with different height, and you are trying to draw a line in between them. If you drew perfectly and mirror the points below that line (which is literally this problem), you'll see that the maximum height difference between any two points will be halved.

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

      How do you know that if it is going to converge to 0 ?

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

        We can quickly halven until the maximum height difference being at most $$$1$$$ (never going to take more than $$$40$$$ times). If it is $$$1$$$, it won't converge (drawing a line between two consecutive height is invalid as we're only allowed integers). Otherwise, it will.

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

          Can you tell me how we can think like this during contest.

          I simply guessed subtract sum(arr)/size(arr) as it was giving correct output for given samples and also, for most of the testcases this guess was correct but got WA on testcase 2

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

            Refer to my root comment, that was how I envisioned the problem. Absolute values on differences feel like a mirror and/or interrupting borderline to me, so that idea just comes naturally (also perhaps given the fact I used to learn basic linear regressions before, so the imagery was engraved).

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

              Taking 1st and 2nd max element each time and doing operations each time with the average of both, will it work in 40 operations? Or will it work ever irrespective of number of operations?

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

                0 0 5e8 ... 5e8 1e9 1e9

                This test will make you loop indefinitely.

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

    In the last step you will have all elements equal in the array.

    So , we need to make atleast two different elements equal at each step (and complete within 40 steps). So we select two distinct elements , decrease the whole array with their average. Since we take absolute values both chosen elements will become equal by this operation.

    In this way in 40 steps we can make all elements =0 , if possible.

    However all elements must be of same parity initialy in the array. (Think about it yourself).

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

humorous problem D

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

Thanks for speedforces and cool problem G, enjoyed the round!

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

A sample test with $$$\min(n,m)=k<\max(n,m)$$$ wouldn't hurt in G. Very silly bug.

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

ZhouShang2003 Is there any issue with problem E? I was getting WA in pretest1 but now it is accepted?

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

is there some bugs in judging system of prob E? Somehow my E become AC after the contest ?

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

    Same for me

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

      I just spent 45 minutes crying and finding for a bug in vain, feeling completely meaningless

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

        when does it get ac ?

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

          idk, when I was crying after the contest, it suddenly became AC somewhen

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

            can u check my code plz ? i also cried tho its regular event xD

            nb: I commented my soln below 2/3 comments

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

    Same here :/

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

Human intelligence round

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

    if you feel so, then problem D makes me Idiot of the century.

    I went to color the graph greedily, and messed up.

    To get constructive, I built a graph for n = 20,

    Spoiler

    Then I started colouring the graph greedily.

    1. What I mean is, I gave color-1 to node 1.
    2. Then I went to node-2, and checked. I can't give color-1 to node-2, because, node-1 and node-2 are connected.

    3. Then I went to node 3, and node-3 is connected to node-1 ( we are checking colors from node 1 to node (i-1)). So, I assigned node-3, also color-2.

    And this is where I went wrong :( . I was getting answer 36, for n=2054. and was trying to find pattern here :( .

    Honestly, kind of demotivating D problem.

    I know that any planar graph is 4 colorable, but this is no planar graph :( .

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

Is upsolving restricted now??

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

if you submit a wrong solution for a task and you never submit a correct one, will you still get the penalty?

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

    no i think you will only get penalty if any of your solution gets accepted after some wrong submissions

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

why it is wrong ?

idea: odd cycle: alice else
even level fill by 0 and odd level fill by 1. if any level full others level fill by 3.

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

    try this case:

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

      I updated my soln. can you check again plz ? this soln handle of case n=1 ig

      thanks btw

      upd: got it. thanks

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

E was amazing!

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

nice contest

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

This round wins the "Cutest prizes" title

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

construct, construct, construct...

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

Can anyone help me find out why my 273201975 on 1991E - Coloring Game received a WA verdict, Checker comment is "wrong answer Integer 3 violates the range [1, 1] (test case 19)" :)

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

    Your code can't handle the case when there is only one vertice. Try this:

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

Update: I figured it out with the coordinators. It seems that most people affected by this are already taken cared of, it is just that most code ends in WA and I got hit with TLE so it was missed.

ZhouShang2003 I am having the same issue in problem E.

TLE during contest (50+ of them) AC after contest, codes identical.

TLE code in contest: 273157246, AC code resubmission 273253391. Please check that the code are identical.

Please look into the situation,

Far more importantly, please clarify what made the differences and so I can avoid running into it again: If the interactors or test case 1 had been changed between the contest and after systest.

Plus please consider un-rating the affected people. I lost at least 30 minutes and all my momentum and mood, (in fact I think I would have gotten at least a moderate positive delta without this).

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

    https://codeforces.net/blog/entry/124418

    arvindf232 = bruhopen (= FastFreeTask)

    I see, you certainly have the right to be unrated.

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

      Clearly I made no attempts to hide that, when I link my submissions from main. Though, I think it is the right time to make a quick comment why I choose to use alt even well aware of the single account policy.

      It is a combination of a few things:

      Firstly, codeforces have nonzero incentive for staying at >=3000 rating that is LGM. You can say that no one cares about ranks and colours but it is there, and I do care, and I believe many do. In fact I care about it a lot. Everything that follows will seem nonsense if you don’t believe 3000 is something meaningful, so please bear with me

      (It is the only final goal of CP, if you don’t count dethroning tourist etc.)

      After my second ICPC world finals, I decided that I have to focus on my studies. If my studies do not work out, I basically have to quit CP for a decently long time, even if not, I cannot train for CP seriously competitively for two years or so.

      My current rating in this retirement state is somewhere between 2900 and 3100, I don’t know because I did not play enough rounds. A safe bet would be 2950 now.

      At my prime, this would be closer to 3100, so there is less risk of losing LGM — and if I lose it I do deserve it, by either a very bad round or just not actually maintaining a good skill above 3000. I am fine with losing it if I am currently seriously looking for improvements in CP, that just means an impactful lesson (I did lost it a few times across the 3 accounts). However, I don’t want to lose it just because I cannot spend time to maintain the same level of “not rusty”, especially when I have proven I can hold it with ease when not in rust.

      Therefore the idea is simple: I just play on bruhopen when I am in “retirement state” and on this account when I am serious and aiming for improvements and even higher ranks. I just keep the two records separate, which they really should be. I wouldn’t hesitate to play on an “unrated” option if there is one, which is supposingly being implemented but it is not happening yet.

      This is the current reason why I chose to play on bruhopen. This was very different from the reasons I play on FastFreeTask in the past, those reasons do actually seriously violate the spirit of the blog so I stopped doing that.

      I think the harm done to the community by this action is within manageable magnitude, for the following reasons:

      I am actually not top 50:if I were comfortably top 50, I would be far away from the 3000 line that I don’t have to worry about it. There shouldn’t be much impact on the rating list you see on the right.

      I only talk and play on unrated round on my main account( this one). The above is an unfortunate exception because I need to signify it was this account that I had an in-contest submissson. I am not trying to hide the fact that I have multiple accounts, it is just not actually useful information for anyone so there is no reason to bring it up.

      In terms of rating dist(arvindf232,bruhopen) is actually very likely within 100. It is simply unfortunate that this difference cross the 3000 barrier that makes it an issue for myself.

      (Plus the usernames are cool ok? My main name have to stay serious but I definitely want to use other names)

      Therefore I will stop using alts altogether when i can be 3200 at my prime = not losing LGM even when rusty = firmly step into top 50, but that day will have to wait because I don’t have time to train on CP.

      Finally I didn’t actually care about rating, rating on this account is inconsequential (cool if it hits 3000 though), and unrating it is just a consolation (recalculate submission time for E and remove 30 minutes of penalty for F and G, I am already at +50 delta, not counting the impact of momentum and losing opportunity to do H). It is just that rightful requests should be made.

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

When will roll back happen?

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

273306239 this submission i have made but was giving constant tle but as soon as i converted it in c++ was giving an accepted solution(but how is this possible)...this is the converted code --->273310051

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

How did you make D's checker?

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

    asking me??

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

    You can use xor convolution to check each colour, so the time complexity is $$$c n \log n $$$, where $$$c = 4$$$ is the number of colours.

    A naive checking in n * number of primes would be $$$4 * 10^9$$$ roughly (2e4 primes less than 2e5), it is possible that this is fast enough as is.

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

Sorry for the coincides but i don't know about that the same code exists or already submitted but i have not copy any code of the problem 1991C this is just a coincidence i don't violate any rule of the contest and the codeforces so pls give my rating back and consider my solution for the contest.

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

Sorry for the coincides but i don't know about that I don't no zhe ID is others but i have not copy any code of the problem 1991C and 1991B this is just a coincidence i don't violate any rule of the contest and the codeforces so pls give my rating back and consider my solution for the contest.

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

    Do you mind explaining why did you put 11 unwanted for loops in this Submission

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

    Because I know that I mixed up the code, submitting it again would lead to skipped, so I naively thought it could be done this way.

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

I'm sorry for logging into a computer with an incorrect account, which led to both submissions being skipped. However, these two codes were indeed submitted by the same person, and there was no intention to use someone else's code. I hope to be forgiven for this mistake![user:GoymyGo]

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

Hello Codeforces Team,

I would like to clarify that the solution I submitted for problem 1991C (solution 273214346) was developed entirely independently. I had no intention of violating the rules. The similarity with other solutions may have been an unintended coincidence due to similar approaches to solving the problem.

I have not shared my code publicly, nor have I used any common sources with other users. If there was any mistake on my part regarding the privacy settings on code-sharing platforms, I was unaware of it and will be careful to avoid this in the future.

My name is SagedRyan, and I did not use ideone.com. I swear that I did not leak any solutions or cheat in any way. I promise that such unintended mistakes will not happen again. It is possible that the other person may have followed my solutions, resulting in a code match, which is beyond my control.

If you have any suggestions or additional steps I can take to clarify this situation, I would be grateful.

Thank you for your understanding.

Best regards,

amendment I spoke to him to understand how this happened and he explained to me that he did not mean that and would have his own different way He also clarified in a comment

I ask you not to skip my solutions, return my solutions as they were, and do not deprive me of points for things beyond my control. SagedRyan

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

Hello Codeforces Team, The person who owns the account SgedRyan apologized to me. He told me about the problem that happened because of me. I actually follow his account and match his code. I matched his code because I liked the way he wrote it and I did not mean to harm him. So there was a similarity in the code. I am sorry. I promise you that I will fix that and I will have my own way of writing.

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

Could anyone explain what happened to the rating changes from this contest? On profiles of contestants, ratings are updated, but in the "rating" tab, they aren't, even though they used to be at some point. Colors are updated everywhere, including the rating tab (which leads to strange situations like mine, where the rating tab shows me as a pupil with a rating of 682). Thanks in advance.

EDIT: The ratings on the ratings tab are back, ignore this now

EDIT 2: And they're gone again. Really confused now.

EDIT 3: About 5 minutes ago, the rating changes were applied on the ratings tab again, and now they, again, aren't. What? (also, not going to bother with edits anymore when the situation changes as often as it does)

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

D is interesting... took my 2 Memory limit and 1 TLE to figured it out.. Thx

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

greedy round. but it's so intersting!

→ Reply