Muhammadali__'s blog

Codeforces Round 1062 (Div. 4)
By Muhammadali__, 13 months ago, In English

Assalamu alaykum, Codeforces!

We are extremely excited to invite you to first-ever-Uzbek contest Codeforces Round 1062 (Div. 4), which starts on Oct/28/2025 17:35 (Moscow time). You will be given $$$7$$$ problems and $$$2$$$ hours and $$$15$$$ minutes to solve them. We hope you will find the problems interesting.

The problems were authored by khba, Muhammadali__, JahonaliX, Nasa and Isamatdin.

The format of the event will be identical to Div. 3 rounds:

  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

We would like to exceptionally thank:

Good luck to everyone and enjoy the problems!

UPD: Editorial is out

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

Comments Comments (170)
| Write comment?
»
12 months ago, hide # |
 
Vote: I like it +43 Vote: I do not like it

Auto comment: topic has been updated by Muhammadali__ (previous revision, new revision, compare).

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

As an author, i hope you really enjoy it and get +ve delta <3

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +74 Vote: I do not like it

As an author, I have nothing to say except for the fact that all authors' ages are between 13 and 15.

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

upvote if you don't know where uzbekistan is on the map

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

Hope this round is free of cheaters

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

I hope that I solve all the problems within the time...

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

As a tester, I hope you all achieve your best performance. GLHF :)

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

orz!

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

i fell from spec to pupil last div2 just for this, hopefully getting a good perf :)

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

As a participant, I hope everyone gets a good +ve delta.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it -17 Vote: I do not like it

Walaikum Assalam! If you don't know about uzbek-famous food. Upvote

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

Wowee

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

hope I can get specialist this time.

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

Good Job

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have sacrificed a Div. 2 to do this officially, I hope this will be good :)

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

As an author, I did almost nothing.

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

As an author, thank you for your participation.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a (unrated)participant , I will solve problem-set from non-increasing order of difficulty

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

As a tester,I'm tester

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I'm really looking forward to this match.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it -23 Vote: I do not like it

As a tester, I solved all problems before the contest. I made a video. Don't miss it. It'll be published here.

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

I wish every Codeforces contest had at least one mandatory interactive problem.

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it -20 Vote: I do not like it

thanks for dislikes

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Owalykum assalam

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +12 Vote: I do not like it

As a VIP+ tester, I hope everyone to be VIP+ participant.

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +19 Vote: I do not like it

Omg! As a participant i wish you guys to get some +

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

Good luck everyone. :)

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

Hope Everyone gets positive delta:)

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

Timur once said JahonaliX is the strongest cper ever. Even though I wont participate, I am sure it will be a nice round.

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

وعليكم السلام I’m looking forward to enjoying this contest!

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

I never knew that there were no contests earlier organized by Uzbeks earlier. Iranians did something earlier. I guess central Asia is catching up. I hope cheaters don't spoil the round though.

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

As an author's friend, I hope everyone will enjoy the round

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a participant, I hope I can solve more problems than in any of my previous Div. 4 contests.

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

As a participant,i will try my best to solve all the problem though i am newbie and trying to improve myself.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Although I'm not the novice I used to be, I will still participate and miss the newbie I was back then

→ Reply
»
12 months ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

سَلَام

→ Reply
»
12 months ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

As a Codeforces User JahonaliX orz Nasa orz

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

Hope It will be a Great Contest for Beginners Inshallah

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The only bad thing(in my opinion) about be[user:__baozii]ing a tester is that you don't get to participate in the round.

Especially if you test a lot of rounds like cry and __baozii__ for example, they don't get to participate in as many rounds as other people. For some lazy people this is good but for goats like them this is bad since they don't get to feel the thrill of solving and competing

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

    Well it doesn’t really matter to me if I can’t participate in div2-4.

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

      Well, I know rating-wise they are pointless, but it's still fun, in an addictive way.

      If the problems are easy for you, then it's a race to see who solves them all faster, which is fun because every minute matters.

      But then again, you have been coding for a long time, and after so long, it's not the same thrill as always

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

Wish to go to Oita:)

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

Hoping for 7 out of 7 after the hacking phase ._.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I feel number of upvotes/downvotes proportional to +ve/-ve delta. Hope the community wishes good for me!!

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

why there is no testers < Expert?

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

As a tester, i tested

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

Is it just me or submissions are being "In queue" for real long?

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i see many ppl are doing G as chatgpt is solving it. G has more solves than F.

If you have cheated by solving G, congrats your account will be banned.

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

    Many people know dp, but not many people know trees man

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

    You can't convince me that G is harder than F. G is an obvious dp problem right from the beginning and the caveat is just to solve it iteratively with space optimization. F, on the other hand, needs some "smart" thinking (At least I didn't solve it in the contest).

    → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

First time to AK a live contest in codeforces ^_^

Thank you so much for this contest guys <3

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

Why n=8000 and timelimit is only 1s in problem G?

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good contest

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For E, does something like keeping a priority queue of ranges where we can insert teleports not work? basically, at every iteration pick the longest range and place a teleport at the furthest position in that range (in the middle if the range is between two friends), and push the range with size one less than the old range. I kept getting WA on #2 for this would love to hear your guys thoughts on this.

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

    I did exactly this idea with a priority queue. Maybe you can check my solution? It's not a really pretty solution though lol, but it works.

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

    I did Binary Search for E. But couldn't solve D. Why does brute force work for D?

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

      the product of 1st 30 primes is greater than 1e18, so any number smaller than 1e18 wont contain all of these primes, and so iterating first few primes will surely result in gcd=1, with atleast one element from array.

      → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why are submissions still N/A, i want to do some hacking :(

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

I love the contest

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

At least I think we should have a G2 with $$$n\le 2\cdot10^5$$$....

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anybody help me with E? I tried 3 times using binary_search but somehow it's wrong

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve 2167E - khba Loves to Sleep!, 2167F - Tree, TREE!!! and 2167G - Mukhammadali and the Smooth Array ?

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

    E — Binary search on ans, I found it similar to Aggressive Cows, but messed up a bit, so wasted a lot of time there.

    F — You need to understand the pattern. Basically, you need to calculate how much each node contribute to the final answer. You can do that by going through each adjacent node of a particular node.

    G — DP, something like longest increasing subsequence. I found it easy to think like what if instead of removing the elements and minimizing the sum, we keep the elements and maximize the sum. Recurrence: dp[i] = c[i]+max(dp[j]) where 0<=j<i && a[j]<=a[i].

    Couldn't get the time to solve F and G in the contest though.

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

      Why is this solution not working?

      Spoiler
      → Reply
      • »
        »
        »
        »
        12 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        It's not right for you to be so greedy. For instance, if the i-th element must be chosen and there exists a j > i such that a[j] > a[i], it's possible that c[j] is very small but a[j] is extremely large, which would lead to a higher cost for selecting subsequent elements.

        Here is a set of samples for you.

        1 5 3 10 2 100 4 66 33 1 1 45

        The answer is 35.

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

great round, my friends all love it.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone give hints in E problem?

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

    binary search on maximal distance + modeling of possible positions with the given distance

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

    If it is possible to place $$$k$$$ teleports, it is possible to place $$$k-1$$$ teleports too. You can assume a distance and check if you can put k teleports maintaining that distance.

    → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i have got 2 correct my rating doesn't increase why?

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest. Submitted D within 25 minutes but got wrong answer 4 times and later saw the constraints and changed int to long long. Dammm I spend one hour because of my silly mistake and bloated the opportunity to be in top 5k.

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

    I submitted D within 13 minutes but because of the queue it took over 15 minutes to check, it turned out I didnt switch int to long long, so I just wasted all that time

    → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think G would've been a more interesting problem if the constraints were higher.

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

Excellent problems.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For problem D, it was stated that the value of aᵢ can be up to 10¹⁸, but on test case 4 I got a Wrong Answer because there was a value greater than 10¹⁸.

I tried to use brute force with x values up to 20, which means calculating up to 19! and that’s where the value jumps from 10¹⁸ to 10¹⁹, which shouldn’t be allowed according to the problem constraints.

If I’m wrong, please correct me.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Does Binary Search work for D? (I've read that some people brute forced it and it passed the pretests) But if anyone has solved it with BS can you please share your solution so that I can get an idea?

→ Reply
»
12 months ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

My Code for Que E without using binary search.

void solve() {
   ll n,x,m,k,sum1=0LL,sum2=0LL;
   string s,s1; char c,p;
    cin>>n>>k>>x;
    vi a(n);
    get(a,n);
    srt(a);
    ll back=0;
    priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,less<>>pq;
    if(a[0]!=0){
      ll fr=a[0];
       ll gap=fr-back;
       ll pos=0;
       pq.push({gap,pos,1});
    }
    back=a[0];
    for(ll i=1;i<n;i++){
        ll fr=a[i];
        ll gap=fr-back;
        ll ok=gap%2;
        gap/=2;
        ll pos=back+gap;
         pq.push({gap,pos,0});
        if(ok) pq.push({gap,pos+1,1});
         else pq.push({gap,pos,1});
        back=a[i];
    }
    if(a[n-1]!=x){
      ll fr=x;
       ll gap=fr-back;
       ll pos=x;
       pq.push({gap,pos,0});
    }
   // yes;
    set<ll>ans;
    while(ans.size()<k){
        while(!pq.empty()){
            tuple<ll,ll,ll>t;
            t=pq.top();
            pq.pop();
            ll pos=get<1>(t);
            ll ok=get<2>(t);
            ans.insert(pos);
            if(ans.size()>=k) break;
            if(ok) pos++;
            else pos--;
            pq.push({get<0>(t)-1,pos,ok});
        }
        if(ans.size()>=k) break;
    }
 out(ans);
}

First sort all friend positions, then consider every empty gap — before the first friend, between each pair of friends, and after the last friend. Each gap’s middle point (or two middle points if the gap is odd) gives the position where a teleport can be placed to maximize the minimum distance to any friend. These candidate positions are pushed into a max-heap along with their gap size. From each middle, you can expand both directions: forward (ok = 1) or backward (ok = 0) — this allows gradual filling outward from the widest spaces. For special cases, if 0 is not among the friends, you only move forward from 0 → a[0]; if the last friend’s position a[n-1] is less than x, you only move backward from x → a[n-1], since there’s no friend beyond the boundary. Then you repeatedly pop the largest gap from the heap, place a teleport at its position, move one step in the indicated direction, decrease the gap, and push it back. This process fills the biggest empty regions first, ensuring teleports are spread out to maximize the time before the first friend reaches one.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

in queue

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

O(n + log(x) * log(n)) solution for E: 346394011

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

when will we have editorial?

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem E was comparatively difficult than F G.

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

why does bruteforcing upto first 100 primes work for the problem D. Also can anyone tell the minimum no of primes we need to check for bruteforcing ?

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

    Because any number <= 10^18 can be divisible by at most the primes <= 47 (their product ≈ 6.1×(10^17)), the smallest coprime must be a prime <= 53, so checking the first 16 primes up to 53 always suffice.

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

    let’s look at multiplying primes: 2 × 3 × 5 × 7 × 11 × …

    • For gcd(2, y) to be greater than 1, y must be divisible by 2.
    • For gcd(2 × 3, y) to be greater than 1, y must be divisible by 2 × 3.
    • For gcd(2 × 3 × 5, y) to be greater than 1, y must be divisible by 2 × 3 × 5. and so on.

    In other words, for consecutive pairs where gcd(x, y) > 1 to keep appearing, the product of consecutive primes must keep growing.

    So, you only need to check up to the first prime z where 2 × 3 × 5 × 7 × … × z >= 1e18.

    → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi, everyone!. I participated yesterday and successfully solved 6 out of 7 problems, but still I have not been rated in this contest. I qualify in fourth division with rating less than 1400. I am new to codeforces so would like to know if I missed something?

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

    I like how it takes you half an hour to solve C, 20 mins to solve B, but you take 5 mins to solve G.

    → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem G should come before Problem E, even though its constraints have been increased to 1e5.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I play this round but still did not get the new rank , is it rated ?

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

I sincerely hope, you guys will remove all alt accounts and cheaters from the standings.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What could be the estimated rating of Problem F according to you guys?

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

I received a notice regarding similarity for submission 346336538 for problem 2167E. I want to clarify that I wrote my code myself locally in IntelliJ IDEA on 28 Oct 2025 — the file was created at 20:58 and compiled at 21:56, as shown in my project history. I did not share or copy any code. I have the original IntelliJ project with timestamps and Local History available for verification. I have taken screenshots which show timestamps for my project file proving that I wrote the code myself and made several changes in it over and over again to ensure it was working on all given sample testcases. I can send them privately

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

Thanks for contest. Problem [problem:4022A] is the best.

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

maksad?

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello, I have received a plagiarism warning for my submission [346324720] on problem 2167D. I want to clarify that I did not copy or share any code during the contest. The other participant and I study at the same university, and we learned similar coding approaches in our programming course. That might be the reason why our codes look similar. It was not intentional, and I will be more careful in future contests. Please review the situation again. Thank you.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

great contest

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

I received the plagiarism warning for submission 346333219 for problem 2167F.

I would like to clarify that the parts of my solution which coincide with other submissions come from a standard, publicly available reference and were not copied from any other contestant.

My Source is a publicly avaibable book: Advanced Data Structures for Olympiad — Papangkorn Apinyanon.

You can find the exact implementation and explanation on page 15 of the PDF: https://me.papangkorn.com/advdsoi.pdf

This is a standard code that I learnt it from this book and used my own variation for standard DFS subtree-size computation and the common loop pattern over tree edges used to compute pair contributions (subtree size s[u], n — s[u], and the conditions checking >= k). My submission follows this standard template that might be the reason for the coinciding code. The algorithm and the code structure are textbook-level and widely used in competitive programming for tree subtree counting tasks. I didn’t publish or share my code on any public platform. I request you to reconsider my code and remove Contest violation from my Codeforces account.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i love questions especially b. May be nezuko from ds and mikasa from aot? i love anime and i think this questions are really interesting

→ Reply