FetFot's blog

By FetFot, 15 months ago, In English

مرحبا, Codeforces!

Translation: Hello, Codeforces!

We are super excited to invite you to participate in Codeforces Round 1007 (Div. 2), which will be held on Friday, February 28, 2025 at 17:35.

This round will be rated for all participants with rating below $$$2100$$$. Participants with higher ratings are encouraged to participate out of the competition.

You will be presented with $$$6$$$ or $$$7$$$ problems and $$$2$$$ hours and $$$15$$$ minutes to solve them. The problems are authored and prepared by Al-Merreikh, ApraCadabra, FetFot, limbo16, MOUFLESS, and Vectors_Master.

We would like to thank everyone who made this round possible:

The score distribution will be as follows:

$$$ 500 - 1000 - 1500 - (1750 + 1250) - 2500 - 3000 $$$

We hope you will find a non-empty subset of problems to be interesting. Good luck, have fun and see you in the standings on Friday!

Let's continue the series of announcements with a photo of the authors. We only managed to find one photo with three of us, another with two, and one with just a single person. Enjoy figuring out who’s who!

UPD: Congratulations to the winners!

All participants:

  1. ksun48
  2. maspy
  3. potato167
  4. jiangly
  5. RGB_ICPC4

Rated only:

  1. RGB_ICPC4
  2. lequoctran181
  3. LifeWillChange
  4. VaVshchuck
  5. ToffeeLong

UPD: Editorial has been posted. Check it out!

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

| Write comment?
»
15 months ago, hide # |
Rev. 3  
Vote: I like it -29 Vote: I do not like it

As a live tester, i want everyone to have a huge positive delta ._.

»
15 months ago, hide # |
Rev. 2  
Vote: I like it +112 Vote: I do not like it

ah yes! uncles round

»
15 months ago, hide # |
 
Vote: I like it +53 Vote: I do not like it

why am I very excited ? ^-^

»
15 months ago, hide # |
 
Vote: I like it +56 Vote: I do not like it

omg Syrian round wtf is electricity and peace

»
15 months ago, hide # |
 
Vote: I like it +45 Vote: I do not like it

first syrian contest

»
15 months ago, hide # |
 
Vote: I like it +72 Vote: I do not like it

Love These Photos <3

»
15 months ago, hide # |
 
Vote: I like it +87 Vote: I do not like it

As a tester , the judges are my uncles.

»
15 months ago, hide # |
Rev. 2  
Vote: I like it +11 Vote: I do not like it

i love this photo alot

»
15 months ago, hide # |
Rev. 3  
Vote: I like it +98 Vote: I do not like it

As a tester, I hope you do not face any ZaiBug while solving the problems.

If anyone is intrested to see one of the testers
»
15 months ago, hide # |
 
Vote: I like it +43 Vote: I do not like it

Good Luck Have Fun <3

»
15 months ago, hide # |
Rev. 3  
Vote: I like it +59 Vote: I do not like it

As a tester, I don't know what to write, so I'll tell you that 1+1=2 is a true statement. Please keep this in mind while doing the contest.

»
15 months ago, hide # |
 
Vote: I like it +77 Vote: I do not like it

As a tester, I've waited all my life to write this as a tester comment so now as a tester

Wait for it

Enjoy

»
15 months ago, hide # |
 
Vote: I like it +47 Vote: I do not like it

As a not-tester, i am sad

»
15 months ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

hoping +ve delta...

»
15 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

As a commenter I am exited.

»
15 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

As a tester, I'm here. Hoorah!

»
15 months ago, hide # |
 
Vote: I like it +46 Vote: I do not like it

I am excited to participate

»
15 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I've never been so excited for a round before. The first Syrian contest. Hopefully the beginning of an era.

»
15 months ago, hide # |
Rev. 4  
Vote: I like it +11 Vote: I do not like it

OH WOWWWWWWWW.

Finally, the Syrian Contest, I hope it will be enjoyable. Thank you to those who contributed to its success.

hack

Pictures of uncles

In the first picture, ApraCadabra, MOUFLESS, and FzArK, from left to right.

As for the second picture, Vectors_Master is on the left and limbo16 is on the right.

As for the last picture, I don't know him, but I think he's Al-Merreikh.

»
15 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

We are proud of you

»
15 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

As a Shaitan, if moon sighting tomorrow, I can't participate but mindflux.

»
15 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

As a contestant, I’m sure the contest will be great!

»
15 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

As a tester: I want to say don't miss this round :)

»
15 months ago, hide # |
 
Vote: I like it +60 Vote: I do not like it

As author of one of the problems, I want money contribution

»
15 months ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

A big salute to all Syrians

»
15 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

yay our heros, i am very excited to participant

»
15 months ago, hide # |
 
Vote: I like it +45 Vote: I do not like it

as a tester, MISSION ACCOMPLISHED

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The person in the third picture is not in the first picture.

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

AS a Ahmad,I am excited to participate

»
15 months ago, hide # |
 
Vote: I like it +54 Vote: I do not like it

As a tester, I found the problems very interesting and cool

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Wow contest by only CMs/Masters

»
15 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

first syrian contest

»
15 months ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

https://mirror.codeforces.com/contest/2070/submission/308193387 Can someone tell a failing test case for this greedy approach?

»
15 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Женя крутейший

»
15 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Uh, I wish I knew programming and codes to participate, but I am just a slow snail.

»
15 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Al-Merreikh is the reason i am here , thank you coach

»
15 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

as a tester, great problems are waiting for you GLHF

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a Aleppon, I assure you that the Halawatueljubn is Alepponian

»
15 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

From Egypt and the pyramids to all parts of the world (أحبكم جميعا.) Translation: I love you all.

»
15 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

up me to Expert please.

»
15 months ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

As a tester, don't miss the great problems!

»
15 months ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

As a tester I demand the authors to invite us testers to a restaurant

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

'Al3a contest!!

»
15 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Why have there been no weekend contests for the past two weeks, despite having 3-4 contests? Especially, why were two Educational Rounds scheduled consecutively instead of saving one for next week, where there seems to be no contest—or at least for a Saturday/Sunday?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    I completely agree with this concern. Weekend contests are ideal for many participants, especially students and working professionals who may not have time during weekdays. Scheduling two Educational Rounds back-to-back while leaving the upcoming weekend empty seems like a missed opportunity for better contest distribution. It would have been more balanced to spread them out, ensuring that those who prefer weekend contests still have something to look forward to. Hopefully, future contest scheduling considers this to maintain engagement and fairness for all participants.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    there should be contests on weekends as well, if possible, it's tough giving contests right after work

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

score distribution pls

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

exited to attend

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

thank you for making contest

»
15 months ago, hide # |
 
Vote: I like it +52 Vote: I do not like it

As an author, I hope you enjoy participating from anywhere in the world (except for one place).

»
15 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

As a tester, I wish I was a contestant! Have fun!

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Aahh got confused with the timing..

»
15 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it
As a contestant , :
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

SYRIAN CONTEST!!!

super excited, hope we all get a +ve delta

»
15 months ago, hide # |
Rev. 2  
Vote: I like it +8 Vote: I do not like it

As an unrated participant, I wish It was rated for me!!

»
15 months ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

As a tester, i enjoyed solving the problems and i think you will too.

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Syria is proud of you guys

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Are problems in a Syrian contest written from right to left?

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Let’s see if I can retain the Specialist title

»
15 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

How to solve problem $$$D1$$$ ?

I tried a lot to figure out how to solve this problem but couldn't find a solution :(

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    hint
    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Can you give me another hint ?

      I understood this hint, but I don't know how to get a solution upon it :(

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        If (l / 2) is odd and greater than n, then a[l] will be the xor of every element of a and a bunch of repeated numbers which doesn't contribute. So a[l] will be just the xor of all elements of a.

        What if l / 2 is even?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    me too I even thought about Lagrangian interpolation. Bad contest for me:(

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    well notice that an adjacent pair (even,odd) will have the same value this was the main idea ig cuz then they cancel out each other so just have to look at the first n elements and how many times are they included in the formation of the l-th element i checked this by continuously dividing by 2 until i reach either an odd element or <=n;

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      What is going to happen if you stopped on an odd element ?

      Can you explain your idea a little bit more, please ?

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        sure say L=38; then the value is a[1]^...a[19] and we know that a[16]=a[17],a[18]=[19]; thus such pairs are cancelled out in case you arrive at an odd number and the answer is XOR of the first n elements in the case where L/2 is even the answer is XOR of first n elements and a[L/2] we continue this to find a[L/2]

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

C was a huge pain

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    C has too many accepted submissions because there is a lot of cheater again :/

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    is it just me, or is this like a 1900 rated problem... I had to just intuite my entire way through it and still could not solve it in time.

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      it looks like 1900 since it uses tree, but after solving it, i'll guess it's 1400-1500

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I was saying cuz I generally solve tree/dfs/dp problems pretty quickly and easily. This was just a pain in the ass.

    • »
      »
      »
      15 months ago, hide # ^ |
      Rev. 5  
      Vote: I like it 0 Vote: I do not like it

      I think it IS a tricky problem. At least 1600+

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

guys please give a hint on solving B idk

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    i think you can store all n numbers in set and then for i till n : run whole set check if (sum till now + no in set forms perfect square if it does skip it otherwise add it and break the loop ) if u cant add a number wihout forming a perfect sqaure output -1:

»
15 months ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

anyone else who struggled implementing D2

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Actually I struggled finding the right answer, not even implementing it.

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      finding the right answer took me about 15 minutes after D1 but it took me an entire hour to implement

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    same bro, spent at least 40 minutes implementing it and still couldn’t get it right

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

missed l<=n for D1 got 5 WA's cuz of that -___-

»
15 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Problem C was fun! Who else solved by sorting by distance to the ending node?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    could you explain your thought process? I struggled the entire time with C.

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      print out the dfs_order from st to en, remember do not dfs into the path. So all the order will be looped into the path thus lead to en without fail.

      Print -1 is absolutely bait, we always have the answer.

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I knew it ! was trying to find a counter example couldnt. Implementation completed as soon as contest ended but good problem

        • »
          »
          »
          »
          »
          15 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I got blind spot and can't find the bug in time of contest, I realize I need to dfs again for every nodes in the path from st to en, so that all the node is used.

          What a hindsight, I just need 5 more mintues...

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Can you explain in detail by what you mean from print out the dfs_order from st to en, remember do not dfs into the path

        • »
          »
          »
          »
          »
          15 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          it means the time of dfs when you reach the node, you might need to learn the time_in and time_out of nodes when we dfs on trees. (Euler tour dfs or something)

        • »
          »
          »
          »
          »
          15 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          might want to check out my code for easier understanding: 308390550

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      First thought was what is the maximum possible distance away from the end, it will be (n — 1) the graph connecting i & i-1 from 1..n.

      Next thought was how can I "waste" the unused moves before the final descent towards the landing. My thought was the nodes furthest away from the target we can dispose of and each node moving closer to the target will bring us 1 step closer. It can be proven that the end node can always be last in the permutation, and second last can be a node thats distance 1 away etc. etc.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I did, not sure why it works :(

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it +8 Vote: I do not like it

      I think if you start from furthest away with distance D, your mouse will always be at distance d<=D, with last d=0 then your mouse will be at end node.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    me, but i gave priority_queue to do the sorting.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    for every node just print from leaf to root(sort according to depth), so that after moving the mouse will never be at a higher pos than cheese and therefore will remain at root when this ends

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    wow that was based idea, I over complicated this...

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Someone please explain B

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    you mean question or the approach ?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    one solution would be by maintaining a running sum while constructing the permutation from 1 to n. For each index i, before adding i to the current sum s, check if s + i is a perfect square using a square checking function (which computes the integer square root and verifies if the square equals the number). If s + i is a perfect square, swap i with i+1 by pushing i+1 first into the permutation and then i, and update the sum accordingly (s += i + (i+1)), then increment i by an extra step to skip the next index, ensuring that the prefix sum that would have been a perfect square is avoided. The key observation here is that two consecutive prefix sums cannot both be perfect squares, so by swapping the two numbers, I ensure that s + i+1 (after the swap) does not become a perfect square. If the total sum of numbers 1 through n is itself a perfect square, then no valid permutation exists, so I output -1.

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I was trying to do the same , if sum + i is a perfect square I swap it with previous element I got a WA can u tell me what I am missing 308332179 ?

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        if your sum+i is sqaure does it matter if u swap (a[i-1],a[i])? total sum will be sum right

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        bro if you swap with a value before it for cases when your current sum is a perfect square it won't bring any change to sum, therefore you swap a with a value in front of it, and it works because we need not even check for square for next sum as consecutive natural number sum can never be perfect squares

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        308325822 here you can check

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    There is no solution if the sum of 1 to N is a perfect square. Otherwise, construct the permutation by adding numbers i from 1 to N, swapping i-2 and i+2 if sum of 1 to i is a perfect square.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    brute force when n*(n+1) // 2 is a square number, they're -1 case. (I'll call this excluded set)

    else you always can swap p[i] and p[i+1] if i is in the excluded set. So the sum till i always +1 from the squared number. -> AC

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I actually generated answer till 10 using brute force, and luckily 1st permutation itself gave a clear pattern

    so we can figure out indices where it is not possible. you just swap at that indices

    example for 9

    start with 1,2,3,4,5,6,7,8,9

    it fails at 1, and 8 .. just swap it with nxt

    2,1,3,4,5,6,7,9,8

    I did this offline till 1000000 and then I can just print 1st n numbers from this as answer

    so when does it fail.. when sum of first n numbers is perfect square and actually thos are the indices where you need to swap ( I observed this later from the answer )

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Took me too long to visualize the idea of A

»
15 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

literally constructiveforces

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I was 5 minute away from submit the correct solution to problem C... so sad.

»
15 months ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

Task D2 and E are sh*t. I can come up with the idea within 2 seconds, and I need to code 1 hour to solve them. They shouldn't appear at a codeforces contest.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +16 Vote: I do not like it

    Or maybe I'm just too naive to come up with an idea which would be easy to implement.

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it +16 Vote: I do not like it

      Both of them have solutions with relatively easy implementations.

      ApraCadabra's solution for E
      FzArK's solution for D2
      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it +8 Vote: I do not like it

        I read the code and found my solutions are exactly the same with them. Maybe it's just I'm too naive to found an easy way to implement. Thank you.

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

man i hate E good q tho

»
15 months ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

this div2 round is much more diffcult than the one yersterday!

»
15 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Is D2 dp digit, which is calculating the number of integer from [l, r] having least significant bit equals to k?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    nope

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You can just solve for an entire range of values instead of one value (as in D1), in pretty much the same way. The key is to make use of the fact that $$$a[2i]=a[2i+1]$$$ with large enough $$$i$$$.

    So you have to if-else when it is large enough, also if-else the parity of each value (because they are calculated differently), and of course if-else edge cases where the value is close to $$$n$$$, or less than $$$n$$$ :P I'm not sure if there is a much neater solution.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It's a method similar to D1 only by recursion by passing a current interval.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    Yes, it can be solved with Digit Dp after realizing the fact that $$$a_{i}$$$ depends on the binary presentation of $$$i$$$.

    My solution
»
15 months ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

worst round ever exist...

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone give solution for B? n = {1, 8, 24}, will return a -1 and for the rest it will have a permutation. For the permutation, I did a prefix sum, and wherever I got sum being a perfect square, I did a swap. Can anyone give the correct logic?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    one solution would be by maintaining a running sum while constructing the permutation from 1 to n. For each index i, before adding i to the current sum s, check if s + i is a perfect square using a square checking function (which computes the integer square root and verifies if the square equals the number). If s + i is a perfect square, swap i with i+1 by pushing i+1 first into the permutation and then i, and update the sum accordingly (s += i + (i+1)), then increment i by an extra step to skip the next index, ensuring that the prefix sum that would have been a perfect square is avoided. The key observation here is that two consecutive prefix sums cannot both be perfect squares, so by swapping the two numbers, I ensure that s + i+1 (after the swap) does not become a perfect square. If the total sum of numbers 1 through n is itself a perfect square, then no valid permutation exists, so I output -1.

  • »
    »
    15 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    brute force when n*(n+1) // 2 is a square number, they're -1 case. (I'll call this excluded set)

    the set is ex = [1, 8, 49, 288, 1681, 9800, 57121, 332928]

    else you always can swap p[i] and p[i+1] if i is in the excluded set. So the sum till i always +1 from the squared number. -> AC

»
15 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Decent problems and quite clear and short problem statements!

  • A: good A problem, just a bit of thinking
  • B: balanced B problem, neat observation
  • C: kinda guessy problem, a more complex observation required
  • D: Unfortunately, I choked and couldn't figure the idea

Overall, the contest was OK. Good job!

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is there a way to solve E other than considering the two cases where the two vertices are distances one or two apart to handle the dependencies?

Maybe I solved it in a very stupid way, but the code turned out to be way too long and tedious.

»
15 months ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

Don't you think TheCodeOracle cheated?

His/Her submissions are full of long name functions.

If you check some of his/her submissions before, you will find he/she use 2 languages in one contest.

So, I think he/she cheated with AI.

If you don't agree with me, feel free to downvote.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    EricWan I think you are wrong because if he cheated then it's submission time gap is very less and also you can't judge only because of language change it is possible that you can change language in between contest because of your simplicity so I think your prediction is wrong and please remove his/her name form this comment "THANKS"

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Sorry, you may have misunderstood my meaning. I certainly agree that using multiple languages in a competition is normal, but using different languages in one problem may be problematic. 308128646 308146849

      And, in 308128646, I can find such a part of the code.

          if (!(cin >> t)) {
              cerr << "Input error: Invalid number of test cases\n";
              return 1;  
          }
      

      I can't find this code in his other submissions. Nobody will print such a long line "Input error: Invalid number of test cases" to DEBUG or get an Runtime Error in the contest.

      This is the code of him in problem A. 308317110

      #include <iostream>
      using namespace std;
      
      bool checkRemainder(long long num) {
          return (num % 3 == 1);
      }
      
      void process(long long k) {
          if (checkRemainder(k)) {
              cout << "YES" << endl;
          } else {
              cout << "NO" << endl;
          }
      }
      
      void solve() {
          int t;
          cin >> t;
      
          while (t--) {
              long long k;
              cin >> k;
              process(k);
          }
      }
      
      int main() {
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
      
          solve();
      
          return 0;
      }
      

      Function checkRemainder(long long) can't be the code he write before, so he write this function in the contest? I think no. In this function, he used only one line of code return (num % 3 == 1);, and used this funtion only one time. He is strong enough to solve D2, don't you think strange that he write a totolly useless function?

      More: His code in D1 and D2 is totolly different. 308369132 308381451

      Oh, I forgot to talk about "submission time gap". Everyone can manage it if he wants. You can't prove somebody is not a cheater from "submission time gap". If he used AI, he needs time to read the solution from AI and study about the logic of the code. If he don't do that, he maybe will get wrong answer, and this helps him to get a long "submission time gap".

      At last, if you disagree, feel free to downvote this comment, too.

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This is not the write way that you can judge anyone if he cheated then codeforces banned him/her. So do your work not involve in these unnecessary extra headache

»
15 months ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

C was a great problem

I mean it is outside the box

thank you guys

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi I just wanted to know the approach of Second Question. At that point I do understand that if sum of n natural number is Perfect square then the answer would be -1. But how to construct the permutation. Printing the integers in decreasing order is a viable and correct solution ?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    No, here's a counterexample.

    5 4 3 2 1

    The first two numbers sum up to 9, which is square.

»
15 months ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Cool round! Although I kind of overthought about C and solved it with a more complicated solution, I loved it a lot!

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    But how to solve C. I thought about it for a long time after solving D1 but I didn't have any idea!

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

      It looks like we can directly output vertices in the order of their distance to $$$en$$$. I haven’t fully understood why this is correct yet.

      My approach is to first construct the path from $$$st$$$ to $$$en$$$. Several sub-components are connected to the path. We run DFS on each of these components separately, from the node connecting to the path. Then, output the farther nodes first and the closer nodes later. This ensures that we will back to the path after traversing in each components. Finally, output the path from $$$st$$$ to $$$en$$$ to arrive $$$en$$$.

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Same approach here, but I can't submit/debug in time of contest, litterally 5 minutes too late.

      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Intuitively we can say that after exhausting all nodes at distance x or greater from en, the mouse will always be either at a distance of x or lower from en. The last node in permutation will always be en (whose distance from en is 0) and that will ensure that mouse ends up at en always.

    • »
      »
      »
      15 months ago, hide # ^ |
      Rev. 8  
      Vote: I like it +2 Vote: I do not like it

      Here is my solution.

      Steps:

      1. Set the root of the tree to $$$en$$$.

      2. Calculate the $$$\mathrm{depth}$$$ of all vertices.

      3. Let $$$p = [1, 2, ..., n]$$$.

      4. Sort $$$p$$$ such that $$$\mathrm{depth}[p[i]] \geq \mathrm{depth}[p[i + 1]]$$$ for all $$$1 \leq i \leq n - 1$$$.

      5. The answer is $$$p$$$.

      Proof:

      After the $$$i$$$-th step, if the mouse is at vertex $$$u$$$, then $$$\mathrm{depth}[u] \leq \mathrm{depth}[p[i]]$$$. This can be proven by mathematical induction.

      Thus, after the $$$n$$$-th step, we have $$$\mathrm{depth}[u] \leq \mathrm{depth}[p[n]] = \mathrm{depth}[en]$$$. Since $$$\mathrm{depth}[u] \geq \mathrm{depth}[en]$$$, it follows that $$$\mathrm{depth}[u] = \mathrm{depth}[en]$$$, meaning that $$$u = en$$$.

      Therefore, after all $$$n$$$ steps, the mouse will inevitably end up at the trap at vertex $$$en$$$.

      Code: 308391781

»
15 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

arnabmanna from meghnad saha institute of technology got top 100 rank overall and 11th rank within rated participants. His college name was written on his profile during the contest when I checked but he immediately removed it after the contest. I have mentioned it multiple contests before as well that some high rated coder is giving him solutions possibly 1_2_3_4_5_9 . I have mentioned previously that arnab was solving 1 problem in div2 in september 2024 and then in 1 week on october 6th 2024 he solves 4 problems in a div 2 round. This is just not possible. He also got 204th rank which means he solved it fast. Someone should complain about him to his college. He is in his 4th year of engineering and looking for jobs according to his linkedin.

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why doesn't my solution for D work ? solution

»
15 months ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

It's an amazing contest. Problem C is a crazy problem. I'm proud of you for your great job.

»
15 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Wow!

»
15 months ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Nice round, I enjoyed it

»
15 months ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

A problem I authored a few months ago and similar to today's D1 is problem G from SPbSU School Olympiad Selection, 2024-2025: statement, tutorial (in Russian). A shoutout to I_love_natalia for teaching me to solve it properly :)

Still, today's D1 & D2 took me a good while.

Thanks for the contest!

»
15 months ago, hide # |
Rev. 2  
Vote: I like it -27 Vote: I do not like it

contest too hard

»
15 months ago, hide # |
 
Vote: I like it +100 Vote: I do not like it

Screencast with commentary

Nice contest! Might be a bit hardcore for div2, but it's ok. Absolutely loved problem C.

»
15 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it
»
15 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

[deleted]

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Bruh... I solved D2 but apparently forgot a return statement... Visual Studio compiles that just fine so it works locally (and gives correct answer), but the server compiler gave WA1 (yes, not compilation error — wrong answer). I didn't even think this was possible...

»
15 months ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

C and D1 were really cool. I guessed the solution for C (sorting nodes in decreasing order of distance from $$$en$$$). After contest I came up with a neat proof for this solution.

Suppose the maximum distance of a node from $$$en$$$ is $$$d$$$, then according to our algorithm, we will first print all nodes with distance $$$d$$$, then all nodes with distance $$$d-1$$$, and so on till we print $$$en$$$ which is at distance $$$0$$$. We can prove the following statement using induction.

Statement: When we are printing nodes of distance $$$x$$$, the distance of mouse from $$$en$$$ will definitely be $$$\leq x$$$.

Proof by induction: This statement is obviously true for distance $$$d$$$, as that is the maximum distance. In addition to this, we can also conclude that if this statement is true for some distance $$$x+1$$$, then it will definitely be true for $$$x$$$ also (think why).

That completes the induction step, we can now say that this will hold for distance $$$0$$$ also, hence the mouse will be at $$$en$$$ at the end.

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think TL for problem F is too strict. I had to optimize many small parts of my code just to fit within TL. Or does anyone have a better approach than $$$O(nlog(n)log(10^9))$$$ complexity?

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Well, the complexity you wrote is correct. The author's (mine :P) solution works in around 3800 ms, but I decided to keep the tl at 6 seconds since I thought that my solution wasn't optimal enough and to prevent possible quadratic optimisations to pass. Honestly for me, it is very unexpected that many solutions with intended complexity got TL with 6 seconds threshold 0_0

  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Obviously it is if the author didn't mean to make those who's using segment tree to check TLE. I was lucky enough to accept it in the contest with 5999ms, and then got uphacked(308381510). But after removing some unnessasery iterations and simplifying a struct to an int, it got < 3000ms with the pretests and 4600+ms with the test#47(308395037).

    But as a fact, the segment tree wasn't the optimal option. If you read jiangly's code (308333069), you'll see the performance of Fenwick Tree(within 2 seconds).

    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it +21 Vote: I do not like it

      The thing is that my solution uses segment tree, and it is completely normal segment tree literally without any optimizations... Anyway we hope to publish editorial within one or two hours so you can check the code there

»
15 months ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

B is funny, I randomized numbers until it works and it worked

  • »
    »
    15 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it +16 Vote: I do not like it

    I did the same. It is probably related to IMO 2009 P6, which proved that for arbitrary $$$n$$$ distinct steps and arbitrary $$$n-1$$$ banned positions, the success probability is nonzero. In our problem, there are $$$\le c \cdot n$$$ banned positions with $$$c = 1/\sqrt{2} \lt 1$$$. I claim the limit probability is nonzero for any such $$$c \lt 1$$$, though I don't have a proof.

»
15 months ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

Solved B by randomly shuffling permutation and checking if its good: 308307060. Can it be hacked?

»
15 months ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

i got CM, therefore the round was awesome

»
15 months ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

All i wanna say that this was a cool contest. Great problems

»
15 months ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

As I guessed it was a great contest

»
15 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Thanks for such a great contest!

»
15 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Editorial isn't loading

»
15 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

problem C was surely beautiful :)

»
15 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

For problem C you could also root the three at 1 find with a dfs where et is,then mark all subtrees that contain that node.

Then we will use the following algorithm: ->we start in 1 we go in subtrees that do not contain the searched node when we reach a leaf we put that node and go back when we finished visiting subtrees that do not contain the node we are searching we are appending our node to the operations and go in the subtree that contains our searched node if it exists

This is my code that gets accepted:https://mirror.codeforces.com/contest/2071/submission/308395204

»
15 months ago, hide # |
Rev. 2  
Vote: I like it +11 Vote: I do not like it

dear all coordinator Sugar_fan this guy arnabmanna cheated in Codeforces Round 1007 (Div. 2) and got rank 11..he is now candidate master..i urge all coordiantor to look in this matter. for more details look at this blogs: https://mirror.codeforces.com/blog/entry/140217 his previous account Arnab_4

»
15 months ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Problem C is beautiful

»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Dear Codeforces Team,

Thank you for bringing this to my attention. I sincerely apologize if my solution has violated any rules, even unintentionally. I understand the importance of fair play and the integrity of the platform, and I truly regret any actions on my part that may have caused this issue.

If the similarity in my solution was due to any mistake like using a public IDE or sharing code by accident, I take full responsibility and will be more careful in the future. I assure you that I had no intention of copying or leaking my code, and I will make sure to follow all the rules strictly from now on.

Once again, I apologize for this situation and thank you for your understanding. Please let me know if there’s anything else I should clarify or address.