Xiaohuba's blog

By Xiaohuba, 11 months ago, In English

Hello, Codeforces!

We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2025, we will hold 3 such rounds. The series results will take into account the best 2 participations out of 3.

On Nov/06/2025 17:35 (Moscow time) we will host Codeforces Global Round 30 (Div. 1 + Div. 2).

Codeforces Global Round 30 marks the second round in the 2025 series of Codeforces Global Rounds. These rounds are open and rated for everyone.

The prizes for this round are as follows:

  • The top 30 participants will receive a t-shirt.
  • 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.

The prizes for the 3-round series in 2025:

  • In each round, the top-100 participants get points according to the table.
  • A participant's final score will be the sum of the points they earned in their 2 highest-placing rounds.
  • The top 20 participants across the series will receive sweatshirts and placement certificates.

We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2025!

The 8 problems were authored and prepared by our 8 authors: 244mhq, cmk666, Daniel777, JoesSR, Link_Cut_qwq, NetSpeed1, zjy2008 and me. There is at least one interactive problem, so I strongly urge you to read the guide if you are unfamiliar with the format.

We would also like to thank:

Round Information:

  • Duration: 180 minutes.
  • Number of problems: 8 problems with 1 subtask.
  • Score distribution: 500 + 750 + 1500 + 1750 + 2250 + (2500 + 1500) + 3500 + 5500

GL & HF!

UPD:

Congrats to the winners!

  1. Otomachi_Una
  2. Kevin114514
  3. dXqwq
  4. ksun48
  5. VivaciousAubergine
  6. qiuzx
  7. strapple
  8. hos.lyric
  9. Radewoosh
  10. StarSilk
  11. tourist
  12. maroonrk
  13. potato167
  14. Nachia
  15. BurnedChicken

First Solves:

A: Away_in_the_heavens
B: ksun48
C: Depressed_sad_boy
D: ksun48
E: Kevin114514
F1: Otomachi_Una
F2: Otomachi_Una
G: qiuzx
H: rainboy

UPD2.

Editorial

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

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

It seems this round will be amazing!

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

As a tester,I think this round will be fantastic

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

As a tester, I think the problems are interesting.

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

As a tester, this is my second time testing a Global Round.

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

As a tester, I can't win a t-shirt in this contest.

  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it -54 Vote: I do not like it

    as a participant, even if you didnt test, you wouldn't be able to win the t-shirt LLoooooLL

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

As a tester,I really recommend this round.

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

As a tester, I hope you have fun!

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

As an author, I hope everyone enjoys this round!

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

As a tester, the problems are nice and I encourage you to participate.

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

As a non-tester, I cannot say anything about this round!! But as a participant, I hope what everyone else does, a +ve delta!!

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

as a random i think it will be amazing

»
11 months ago, hide # |
← Rev. 2  
Vote: I like it -61 Vote: I do not like it

interested

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

As a tester who forgot to test earlier, I think the problems are nice.

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

As a participant, participating in global round is a part of participant's routine

»
11 months ago, hide # |
← Rev. 3  
Vote: I like it +63 Vote: I do not like it

As a tester, I'll be able to sleep early today.

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

can we participate unrated in this contest? not able to see any such option

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

Hoping for a great round !!! and also reaching back to expert!

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

orz

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

I'm from future and I ensure guest_ducbao_ will decrease rating

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

As a participant, i will try to do 3 tasks

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

Hope the judges work well.

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

As a participant, I wish that only worthy people could solve G xddd..

Global Round 29
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Are hacks disabled for some of the problems like few of the last contests ?

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

It seems this round will be amazing

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

can anybody helo me? I ask question after i cannot find any solution. It becomes frequently. So i can solve and write code after reading questions. Is tehre some tips and tricks maybe strategies that u can solve question easily with them. As when u see statement u already know how to this question tip.

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

A vivid example of why we should remove hacking rewards

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

Upvote if u did B with Random :)

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

    I found B a bit tricky !! but didn't use random....

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

      how u come to the conclusion n > 100 , then consecutive will give even remainder ?

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

        oh, 100 is not the correct bound.. it should be around 32 .. like (1 << 32 > 1e9 ) ... but I just typed whatever I typed fast

        observation

        1. 2 even numbers — then they are the answer pair
        1. if 2 odd numbers x and y and y < 2x... this pair forms the answer

        so if we don't find evens .. then if every number is odd and is more than 2 times then it can't increase more than 32 times as it will grow bigger than 1e9... because it is given that numbers are strictly increasing .. so after 32 odd numbers you will find the pair

        PS .. consecutive after sorting coz I want y < 2x .. they will become neighbor after sorting.

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

Thanks for the visualizers! I found them to be quite helpful during the contest.

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

is problem B really just checking each possible pairs or would that result in TLE?

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

    you can prove there must be an answer at arround 30 or 40 numbers.

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

    Problem B:

    If you have two even numbers $$$x \lt y$$$ in the list, $$$y \mod x$$$ is even so it's done.

    Assume all numbers are odd. If you find two adjacent numbers $$$x \lt y$$$ such that $$$2x \gt y$$$, you're done because $$$y \mod x = y-x$$$ which is even.

    Note that if $$$2x \gt y$$$ never occurs, then each number must be at least twice the previous one. This sequence would quickly exceed the $$$10^9$$$ limit, so you only need to brute force the first ~35 numbers. Because of this, even if you write the $$$O(n^2)$$$ solution it will quickly find the answer.

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

https://codeforces.me/contest/2164/submission/347775781

this is my code for question B this actually worked , i heard from others that there brute force worked on this but this code is more fun because i used random two indexes for checking(atmost n*100) random index genration was done and yup it's accepted

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

Why I find B>C>D. D is just implementation. C reminds me to read the question carefully because I misread the problem for half an hour. B is half guessforces and half mathematical intuition, which I’m unfortunately kinda missing.

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

    sorry, but exponentials/logarithms is as basic as math can get though

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

    Yes B was horrible, D was just implantation base think in reverse direction of string

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

    please share idea for D

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

      Go from reverse index of t to s;

      You can only select indexes <= of the current index of t. We just iterate from reverse, making sure to only assign indexes continuously to the left.

      The reasoning is: If any of the mapping cross, we are in trouble because, its like you are stretching string s to the right a bit and overlapping some parts, once a part is lost you can't get it back.

      Once you have this mapping, its just the matter of sorting the biggest distance a crossing needs to cover, say adbc and aaad, here the 'd' needs to go to the right most part, we maintain a map<int, vector> and iterate from biggest distance to smallest distance and when iterating, append all of map[distance-1].push_back(map[distance] elements),

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

        hmm thanks for sharing your idea...

        I had similar idea, but I guess I couldn't figure when the case is invalid .. like the stretching thing you mention

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

          Gotcha, yes whenever you can't go about assigning an index of t to index of s without crossing, we go sad.

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

      Here is how to find $$$s'$$$ from a $$$s$$$ that moves closer towards $$$t$$$:

      Spoiler
      prev filling

      You can just keep doing these steps until $$$s$$$ becomes $$$t$$$.

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

        thanks for this ... I will try to read and understand it tomorrow !!!

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

          I wrote an even simpler solution that does not require the $$$prev$$$ array: https://codeforces.me/contest/2164/submission/347788909

          The idea is that suppose we want to know where $$$t[n-1]$$$ comes from, we find the right-most instance of the char $$$t[n-1]$$$ in $$$s$$$. Suppose that happens to be $$$s[j]$$$. Now, $$$t[n-2]$$$ can only come from any position $$$\le \min(j, n-2)$$$. So, we find the corresponding char in $$$s$$$ for $$$t[n-2]$$$, and so on.

          If there is no such $$$s[j]$$$ from where $$$t[i]$$$ can come from, then the transformation is just not possible. Similarly, if $$$i-j \gt k$$$, then that means a char moves more than $$$k$$$ steps to the right, from $$$j$$$ to $$$i$$$, to transform $$$s$$$ into $$$t$$$. Therefore, that is an impossible transformation too. This impossible case can be detected in the first transformation from $$$s$$$ to $$$s'$$$. If it is possible, then just iterate while $$$s \ne t$$$.

          Iteration step: for any $$$i$$$ from $$$n-1$$$ to $$$0$$$, if the corresponding $$$j \ne i$$$, then we move the $$$s[j]$$$ one step to the right, so it can reach the index $$$i$$$, eventually. Therefore, we can assign $$$s'[j+1] := s[j]$$$. Rest all the positions in $$$s'$$$, that are left unmodified in this step, can be simply copied from $$$s$$$. Therefore, just initialize $$$s' := s$$$ before doing this step of iteration from $$$n-1$$$ to $$$0$$$.

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

            great, thanks again ..

            I found this one simpler to understand.

            I will try to upsolve over the weekend

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

why do O(n^2) even work for problem B ;/ ?

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

For problem C, the input format is like

b1 b2 ... bm

c1 c2 ... cm

But by accident, my first code 347700877 received the input like

b1 c1 b2 c2 ... bm cm

Surprisingly I got all 5 examples correct, so I got a wa. Is it intended? :)

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

Why I have TL in C, but when I add in always cycle:

if((clock() - start) / CLOCKS_PER_SEC > 1) cout << "^_^";

I don't get WA

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

figured out D with 30 seconds left

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

What a ride it was!

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

How to do F? :(

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

    I was desperate when realizing F only had "math" tag but not "dp". I spent yrs trying to come up with some dp stuff.

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

I considered the pairs of indexes (i, i-1), (i, i-2), (i, i-3) in B, and it passed all the pretests. What the hell? And now i got fst bruh

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

Why my solution of E doesn't work. First, add all the edge weight as the base weight, and we can only consider the valid vertex with odd degree. Then we use union find to merge the vertex to blocks, if one edge doesn't have any edge in the latter position with weight smaller than it, then we can pair all the odd vertex within the block.

However this solution keep falling at pretest 2 and I don't know the reason why.

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

    counterexample: a component with four odd vertices joined early by edges of weight 100; later a single edge of weight 1 appears elsewhere; when the graph becomes connected, only one pair can use cost 1 at the ancestor, the other still pays 100 (true extra = 101), while your rule would charge 2.

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

I request that my solution to B be rejudged.

I got skipped, but considering it's a simple brute force(Could not have been simpler), I think I deserve a rejudge

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

    Your first submission for B got skipped not because of plagiarism, but because you resubmitted for the same problem during the contest. Only the last submission for a problem is considered and previous ones are skipped.

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

Reaching LGM is no longer a dream.

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

Why is my submission for problem C not being added to the System test queue? The status still shows "pretests passed," but the score for this problem is not in the rankings.

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

I didn't read the statement of C carefully and thought killing a monster with Ci > 0 would get a new sword with damage = Ci, not max(x, Ci). I find under such condition the problem seems too complicated. So I wonder if correct solution still exists under such condition.

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

    I think my solution should work for that case as well. It tries to use the weakest sword, and then transform it into the strongest sword possible (using this sword for killing). It processes swords in ascending order, then adds all the monsters that it can kill in a ready queue. Now, if the ready queue has a monster with non-zero $$$c$$$, then it will exchange the sword with the largest achievable $$$c$$$. Then the process repeats. Therefore, if the sword was exchanged for a weaker sword, then it will be processed on the next iteration. This greedy approach should work.

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

      I have a similar idea, but don't know what to do when the current sword was exchanged for a weaker sword. Suppose sword with value X now changes to Y(Y < X), since all the monsters with Bi <= X were already added into the queue, how to do with this Y sword exactly?. In my idea, I use a priority queue to maintain the monsters that were added, and I put the monster with the highest Ci on the top. Now X becomes Y, if Y < X, do I have to search in the queue to find the highest Ci among those monsters with Bi <= Y, and continue this process? Seems very difficult for STL or simple data structure to do this.

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

        Hah, I missed that :)

        It almost seemed too easy.

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

          haha it's fine. Luckiy I realized I misread the statement during the contest otherwise I am not blue anymore lol

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

For B brute force seems to be working perfectly fine, which is a little disappointing tbh.

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

May this day Be The day?

»
11 months ago, hide # |
 
Vote: I like it -16 Vote: I do not like it
#include <bits/stdc++.h>
using namespace std;
void solve(){
 long long n; cin >> n;
 vector<long long> v(n);
 for(int i= 0;i < n;i++) cin >> v[i];
 vector<long long> odd,even;
 for(int i =0;i < n;i++){
  if(v[i]%2)odd.push_back(v[i]);
  else even.push_back(v[i]);
 }
 sort(even.begin(),even.end());
 if((int)even.size() >= 2){
  cout << even[0] << " " << even[1] << endl;
  return;
 }
 if((int)even.size() == 1){
   long long temp = even[0];
   for(auto x:odd){
    if(temp > x && ((temp%x) == 0 || (temp/x)%2 == 0)){
     cout << x << " " << temp << endl;
     return;
    }
   }
 }
 sort(odd.begin(),odd.end());
 for(int i =0;i < (int)odd.size();i++){
  long long t = odd[i];
  //i + 1 + odd.begin() upto odd
  long long j = 1;
  while(t < LLONG_MAX/j){
      t = t*j;
   auto it = lower_bound(odd.begin()+i+1,odd.end(),t);
   if(it == odd.end()){
      break;
   }
   else{
    long long pos = it - odd.begin();
    if((odd[pos]/odd[i])%2 == 1 || (odd[pos]%odd[i] == 0) ){
     cout << odd[i] << " " << odd[pos] << endl;
     return;
    }
   }
   j+=2;
  }
 }
 cout << -1 << endl;
}
int main(){
 int tt; cin >> tt;
 while(tt--){
  solve();
 }
 return 0;
}

why this solution giving wrong answer on test case number 5.

»
11 months ago, hide # |
← Rev. 2  
Vote: I like it -14 Vote: I do not like it

Great round! Learned a lot from the problems — thanks to the setters and testers for their hard work. Waiting for the next Global Round .

»
11 months ago, hide # |
← Rev. 2  
Vote: I like it -14 Vote: I do not like it

.

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

Loved the B problem!!

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

I think Problem B was far more difficult than Problem C. In the end, I just guessed my way through it, haha, guessforce.

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

Can anyone explain why it not work for C https://codeforces.me/contest/2164/submission/347841876

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

My submission: https://codeforces.me/contest/2164/submission/347867661

Can someone please help me understand why my code does not work?

The approach is about eliminating the maximum number of Stage 1 monsters using a segment-based approach. The idea is that I can eliminate the monster at index j if the minimum index I can start eliminating from is i.

mai is just the maximum sword power I can get while clearing all monsters in that segment.

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

As a tester, I'm a tester.

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

Great contest!

Thanks to authors

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

the first time I see two unrated testers

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

Day 2 of asking MikeMirzayanov to add the "Delete account" feature on a random blog.

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

Can someone explain approach for problem E.

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

.....

»
10 months ago, hide # |
 
Vote: I like it +42 Vote: I do not like it

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

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

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 2164 1 Otomachi_Una
2 2164 2 Kevin114514
3 2164 3 dXqwq
4 2164 4 ksun48
5 2164 5 VivaciousAubergine
6 2164 6 qiuzx
7 2164 7 strapple
8 2164 8 hos.lyric
9 2164 9 Radewoosh
10 2164 10 StarSilk
11 2164 11 tourist
12 2164 12 maroonrk
13 2164 13 potato167
14 2164 14 Nachia
15 2164 15 BurnedChicken
16 2164 16 JDScript0117
17 2164 17 _lbw_
18 2164 18 dsgrekova2
19 2164 19 Hamed_Ghaffari
20 2164 20 Petr
21 2164 21 zwezdinv
22 2164 22 jinqihao2026
23 2164 23 tiger2005
24 2164 24 permutation
25 2164 25 platter
26 2164 26 rin204
27 2164 27 Sulfox
28 2164 28 EasonTAO
29 2164 29 O_O_Zzz
30 2164 30 maspy
68 2164 68 tute7627
112 2164 112 risujiroh
118 2164 118 Akulyat
142 2164 142 Dinprosperity
143 2164 143 anmichi
151 2164 151 Network_Error
165 2164 164 Iron_china
184 2164 184 Xellos
230 2164 230 Andrew-13
235 2164 235 Zachary_Gao
303 2164 303 irmuun
339 2164 339 konbi
385 2164 384 ji_114514
395 2164 395 xxh1999
399 2164 399 LarrixAntofanin
404 2164 404 Nanani
432 2164 431 xly_tyty
444 2164 444 waste_
470 2164 470 trivialkid
472 2164 472 cherryk
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I HAVE ALREADY SOLVED EVERYTHING DONE