Блог пользователя FetFot

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

مرحبا, 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!

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

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

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

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

ah yes! uncles round

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

why am I very excited ? ^-^

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

omg Syrian round wtf is electricity and peace

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

first syrian contest

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

Love These Photos <3

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

As a tester , the judges are my uncles.

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

i love this photo alot

»
14 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится +98 Проголосовать: не нравится

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
»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +43 Проголосовать: не нравится

Good Luck Have Fun <3

»
14 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится +59 Проголосовать: не нравится

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.

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

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

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

As a not-tester, i am sad

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

hoping +ve delta...

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

As a commenter I am exited.

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

As a tester, I'm here. Hoorah!

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

I am excited to participate

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

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

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

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.

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

We are proud of you

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

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

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

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

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

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

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

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

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

A big salute to all Syrians

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

yay our heros, i am very excited to participant

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

as a tester, MISSION ACCOMPLISHED

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

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

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

AS a Ahmad,I am excited to participate

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

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

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

Wow contest by only CMs/Masters

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

first syrian contest

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

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

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

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

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

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

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

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

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

as a tester, great problems are waiting for you GLHF

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

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

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

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

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

up me to Expert please.

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

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

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

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

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

'Al3a contest!!

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

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?

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

    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.

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

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

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

score distribution pls

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

exited to attend

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

thank you for making contest

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

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

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

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

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

Aahh got confused with the timing..

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится
As a contestant , :
»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

SYRIAN CONTEST!!!

super excited, hope we all get a +ve delta

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

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

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

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

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

Syria is proud of you guys

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

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

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

Let’s see if I can retain the Specialist title

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

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

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

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

C was a huge pain

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

guys please give a hint on solving B idk

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

anyone else who struggled implementing D2

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

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

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

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

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

Someone please explain B

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

    you mean question or the approach ?

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

    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.

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

    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.

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

    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

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

    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 )

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

Took me too long to visualize the idea of A

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

literally constructiveforces

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

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

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

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.

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

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

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

      Both of them have solutions with relatively easy implementations.

      ApraCadabra's solution for E
      FzArK's solution for D2
»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

man i hate E good q tho

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

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

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

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

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

    nope

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

    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.

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

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

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

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

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

worst round ever exist...

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

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?

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

    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.

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

    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

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

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!

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

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.

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

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.

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

    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"

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

      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.

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

    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

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

C was a great problem

I mean it is outside the box

thank you guys

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

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 ?

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

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

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

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

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

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

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

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

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

        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.

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

      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

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

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.

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

Why doesn't my solution for D work ? solution

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

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

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

Wow!

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

Nice round, I enjoyed it

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

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!

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

contest too hard

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

Screencast with commentary

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

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

[deleted]

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

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

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

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.

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

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?

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

    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

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

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

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

      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

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

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

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

    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.

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

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

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

i got CM, therefore the round was awesome

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

Просто решение задачи B

https://mirror.codeforces.com/blog/entry/140166

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

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

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

As I guessed it was a great contest

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

Thanks for such a great contest!

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

Editorial isn't loading

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

problem C was surely beautiful :)

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

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

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

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

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

Problem C is beautiful

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

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.