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

header Hello, Codeforces!

We are pleased to invite you to Pinely Round 4 (Div. 1 + Div. 2), which will start on Jul/28/2024 17:35 (Moscow time). 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!

  • Проголосовать: нравится
  • +527
  • Проголосовать: не нравится

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

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

UPD: I will try again =)

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

Hoping for a good contest!

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

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

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

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

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

As a tester, I tested the round.

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

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

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

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

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

    You can if you are Psychotic enough :D

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

      lmao

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

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

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

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

        upd. sorry check _inferno_'s comment for reference

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

        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

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

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

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

Hope I can reach pupil :)

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

Guys, scoring distrib pls pls pls

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

All the best Guys:)

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

As testers, jiangbowen and I tested the round.

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

This round will contain some really challenging problems ig :)

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

As a participant, I will participate in the round.

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

potato

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

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

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

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

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

Hope I can solve 4 problems!

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

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

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

Scoring distribution when?

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

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

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

      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.

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

I hope to learn more from this round of competition

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

Stop interactive problems :(

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

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?

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

    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

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

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

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

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

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

          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

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

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

            $$$ 1_2 | 11_2 | 111_2 | 1111_2 = 1111_2 $$$
»
4 месяца назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

speedforces loading...

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

Hoping to become green after this round

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

nob nob

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

пон, надеюсь, решу много SergeevAmogus

Пон

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

tourist will win this round : )

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

Too difficult for me :(

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

Staring at D for 2 straight hours

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

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

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

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

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

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

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

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

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

        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.

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

    I did the same :(

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

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

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

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

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

      Can you elaborate?

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

        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

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

          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

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

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

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

    you should've spammed "1 3" I think

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

I hate constructives so much now

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

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 ...
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Did you mean problem D?

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

    it was really just that?

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

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

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

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

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

          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.

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

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

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

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

Regardless, I really enjoyed the round!

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

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

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

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

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

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.

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

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

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

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

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

    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?

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

    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.

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

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

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

    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.

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

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

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

[deleted]

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

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

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

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

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

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

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

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.

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

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

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

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

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

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.

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

Problem E is a repeated problem Original Problem

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

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

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

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

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

ConstructiveForces

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

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

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

GuessTrickForces :(

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

Thank you for the round!

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

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

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

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

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

      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?

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

Poor experience

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

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.

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

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

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

This Round is the worst round i have ever seen

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

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!

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

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

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

I really hate problem of D kind

guess until get it right

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

interesting constructives early on.

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

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

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

    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.

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

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

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

        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.

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

          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

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

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

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

              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?

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

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

                This test will make you loop indefinitely.

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

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

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

humorous problem D

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

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

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

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

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

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

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

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

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

Human intelligence round

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

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

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

Is upsolving restricted now??

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

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

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

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

»
4 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
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.

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

E was amazing!

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

nice contest

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

This round wins the "Cutest prizes" title

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

construct, construct, construct...

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

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

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

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

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

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

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

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

    arvindf232 = bruhopen (= FastFreeTask)

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

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

      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.

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

When will roll back happen?

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

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

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

How did you make D's checker?

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

    asking me??

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

    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.

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

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.

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

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.

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

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

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

    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.

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

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]

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

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

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

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.

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

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)

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

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

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

greedy round. but it's so intersting!