dvb1r's blog

Codeforces Round 1103 (Div. 3) Editorial
By dvb1r, history, 3 months ago, translation, In English

2236A - Games on the Train

Idea: arsen1y

Tutorial
Solution (arsen1y)

2236B - Tatar TV Show

Idea: eyfxrby

Hint
Tutorial
Solution (eyfxrby)

2236C - Omsk Programmers

Idea: arsen1y

Hint
Tutorial
Solution (arsen1y)

2236D - Brand New Tatar TV Show

Idea: dvb1r

Hint 1
Hint 2
Tutorial
Solution (dvb1r)

2236E - Friendly Gifts

Idea: arsen1y

Hint 1
Hint 2
Tutorial
Solution (dvb1r)

2236F1 - Elections in Saransk (easy version)

Idea: eyfxrby

Hint 1
Hint 2
Tutorial
Solution

2236F2 - Elections in Saransk (hard version)

Idea: eyfxrby

Hint 1
Hint 2
Hint 3
Tutorial
Solution 1 (eyfxrby)
Solution 2 (Treks)

2236G - Criterion in Burlandia

Idea: dvb1r

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution 1 (dvb1r)
Solution 2 (Treks)
  • Vote: I like it
  • +126
  • Vote: I do not like it

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

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

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

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

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

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

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

G is beautiful

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

What's the solution2 for F2?

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

In F2 I tried to build up a DP solution, but all attempts ended up with too big complexity. I was exciting to see the tutorial. However, complexity in tutorial is:

O(A⋅log(ai)2⋅n)

I.e. 7 * 18 * 18 * 500'000 = 1'134'000'000. Looks too much, isn't it? I wish a constraint for n could be 100'000 instead of 500'000. With 500'000 the main skill to solve this problem is bravery :)

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

My video and text editorial for all problems is available here https://codeforces.me/blog/entry/154479

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

    Nice editorial! For problem D, I also found a great alternative solution in Python that achieves $$$O(N \log N)$$$ Time but optimizes the auxiliary space to $$$O(1)$$$ by processing the sorted array in a single reverse pass, avoiding the extra memory of a pair vector.

    Here is the breakdown for anyone interested:

    Core Idea:

    Instead of compressing the array beforehand, we can sort it and iterate backward (from the largest element to the smallest). We maintain the frequency (quantity) of the current maximum value on the fly.

    As we slide to the left:

    If the current maximum's count is even, Arseniy can pick it, and Egor wins by parity.

    If the count is odd, we check if we can bridge it with the next distinct smaller element. If the gap between them is <= k, Arseniy can pick that smaller element, forcing Egor to clear the maximums and win.

    If the gap is > k, this maximum block becomes a "dead end". Since it's odd and cannot be bridged, it's a losing state for Egor. We mentally discard it, reset our frequency counter, and treat the next distinct element as our new maximum.

    CODE IN PYTHON : ~~~~~ import sys input=sys.stdin.readline def solve(): 

    n,k=map(int,input().split()) 

arr=list(map(int,input().split())) 

arr.sort() 

quantity=1 

value=arr[n-1] 

for i in range(n-2,-1,-1): 
    if arr[i]==value: 
        quantity+=1 
    else: 
        if not quantity%2 or value-arr[i]<=k: 

            return "YES"          

        else: 

            value=arr[i] 

            quantity=1 

if quantity%2: 

    return "NO" 

else: 

    return "YES"

    t=int(input())

    for _ in range(t): 

    print(solve())

    ~~~~~

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

f2 is really nice implementation wise, tutorials for both f1 and f2 are great aswell, i just wish f2 would also include the proof for max(...)+v_pr(x)=summ(...).

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

    Look at number as a product of it's prime factors. E.g. 12 = 2 * 2 * 3. Concentrate on a single prime, e.g. on 2. So, for each number we should only know how many 2's it contains.

    LCM of several numbers will contain the amount of 2's equals to the biggest amount of 2's among these numbers. E.g. LCM(4, 8, 16, 2) = 16, here 16 = 2 * 2 * 2 * 2, i.e. contains 4 2's.

    The product of numbers contains the amount of 2's equal to the sum of amounts for each number. E.g. 4 * 8 * 16 * 2 = 2 ^ 10, i.e. 2 + 3 + 4 + 1 = 10.

    We must conform x * LCM(...) = product(...)

    let v(y) = amount of 2's in y. Thus we must conform v(x) + v(LCM(...)) = v(product(...)) As shown above, v(LCM(...)) = max amount of 2's and v(product(...)) = sum of amount of 2's.

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

    i think it is trivial

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

I am stuck as a newbie since long, please guide me on how can I improve ?

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

    Bro i saw your profile i am also stuck on newbie. But still i think i have some points on which you can improve if you want.

    1. you must do problem till at least 1200 rated you are only trying 800 ones you must increase your difficulty.
    2. you can also select div2 , div3 , edu. , and div1 + div2 in contest filter tab and try to do till B in (div2, edu.,div1 + div2) and till C in div3 in past contest. it will help to improve i think. 3.Once you get familiar you can increase difficulty and/or number of question in past contest.
    → Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    First, stop stressing about rating.

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

    hey bro , I am also new to codeforces , if u wanna pratice together we can ? I mean like we can share resources , help with problem approcah , cause i need some firend online or offline doest matter who can pratice with me on codeforces .

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

In my opinion problem F2 constraint should be lower it causes confusion whether the given solution will pass or not

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

Its so easy to overthink on E and go down a rabit hole which actually works.

My solution used DSU to find the good segments and a DP with some weird ass states. link here: https://codeforces.me/contest/2236/submission/378557786

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

Am I the only one who used a dp and fenwick tree on D?

Here is my submission 378392641

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

    Mee i used Dp with Deque But it Gave TLE after Pretests

    → Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    // https://codeforces.me/problemset/problem/2236/D 
// priyathama 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
    int n,k;
    cin >> n >> k; 
    vector<int> a(n);
    map<int,int> mp;
    vector<int> stones;
    for(int i=0;i<n;i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    for(auto &val:mp){
        stones.push_back(val.first);
    }
    /*
    My thought process During Contest And where i Complicated it 

    My thoughts 
    given range and we should find valid 
        so it is segementree we can also use dq 
        
    Mistake Once 
        traversed Forward 
    Mistake Two 
        A E D 
            Traversing BackWard is Correct 
    */
   n=stones.size();
   vector<int> dp(n);
    // dp[i] = 0  or 1 
    // if dp[i] == 0  that says if we start by removing ith index stone we will loose
    bool found=false;
    // this dq stores the indx of values <=x+k and it is a winning pos 
    // deque<int> dq;
    int latest=-1;
    for(int i=n-1;i>=0;i--){
        // while(dq.size() && stones[dq.front()]>stones[i]+k){
        //     dq.pop_front();
        // }
        // it is better to store the index which is the most latest
        // other wise it tles as k grow and deque grows 
        // so this is my mistake 
        // while()
        if(i+1<n){
            if(stones[i+1]-stones[i]>k){
                // this says if we pick ith stone 
                // then the other person cant pick then we win 
                if(mp[stones[i]]%2){
                    latest=i;
                    dp[i]=1;
                }
            }
        }else{
            if(mp[stones[i]]%2){
                latest=i;
                dp[i]=1;
            }
        }
        // other case if we remove this and the latest is <=x+k and that is 
        if(latest!=-1){
            if(stones[latest]>stones[i]+k){
                // we remove this and the opponent need any winning index but it is not there so we win
                if(mp[stones[i]]%2)
                    dp[i]=1;
            }
        }
    } 
    for(int i=0;i<n;i++){
        // cout << dp[i] << ' ';
        if(dp[i]==0){
            found=true;
        }
    }
    if(found){
        cout << "YES" ;
    }else{
        cout << "NO" ;
    }
    cout << '\n';
    }
}
    → Reply
»
3 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

In C, you can also simply put all variations of a through division in vector A, and all variations of b through division in vector B, that is: A = {a, a / x, a / x^2, a / x^3, ...} and B = {b, b / x, b / x^2, b / x^3, ...}. After that, brute force both vectors and find the pair which leads to optimal number of steps: i + j + diff(A[i], B[j]). Since a, b <= 1,000,000,000 and x >= 2, it is guaranteed that |A|, |B| <= 31.

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

F2 is great

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

In the editorial and solution of G, I couldn't get the "compressed tree" part. I think the Hint4, which states that, "Reduce the problem to a path of length at most 2∗log(A)" is signalling the same thing. Can someone please explain this part.

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

    The idea is that the compressed tree consists only of the vertices with nonzero masks (and the root). You can do this via DFS by keeping track of the lowest nonzero ancestor: the edges of the compressed tree are edges from each nonzero node (in the full tree) to its lowest nonzero ancestor. The level ancestor queries happen in the compressed tree.

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

Problem 2236D: Python O(N \log N)$$$ Time / O(1)$$$ Auxiliary Space Single-Pass Solution

This approach avoids allocating additional memory for a pair vector, which keeps the auxiliary space complexity at O(1). For those who simply want to look at the code and analyze it, I recommend skipping the explanation of the code’s logic, as it is intended for those who want to dissect and understand it. I do, however, encourage you to read it so that you can understand this logic.

EXPLANATION:

Hey coders! For those of you who are stuck, I’ve got a great alternative solution based on the same mathematical logic of parity. First, let’s take our array and sort it — complexity O(N \log N). You might ask, why? Because, remember, several numbers repeat themselves. The idea is to group them so we can count them and avoid misreporting the data, since the number of times a number repeats is very important. To make this as educational as possible, let’s use this example, which we’ll work through step by step:

N ->13 K -> 2

array -> 2223344477777

Let’s start by explaining the logic. Imagine if we only have one number that repeats an even number of times, e.g., 999999. If our famous Arseniy plays here, IT IS 100 PERCENT GUARANTEED that Egor will win no matter what position Dabir plays. Why? Let’s denote D as Dabir and E as Egor. Let’s show how the game plays out:

999D99 -> E99D99 -> ED9D99 -> EDED99 -> EDED9D -> EDDED“E”D BOOM Egor wins! Not surprising at all since the number is even!

Let’s take the case where the number is odd: 999.

D99 -> D9E -> D“D”E BOOM Dabir wins. The rule is that if it’s an odd number, then he can’t win.

But you’d say LOLLLL Pacific.exe thinks it’s an application in this case 223333 with K=5. If D plays D23333 and E plays DE3333, he still hasn’t won because he can still play 3 (K=5, so (3-2) < 5).

Guys, you’re right — you’ve won — but remember, we’ve sorted the array. This means that the maximum value in the array is guaranteed not to overlap with any other value. For example:

1122777 with K=2.

Are you telling me that if D takes the element 7, it can then take 2? REMEMBER, YOUNG CODERS: you can only take a number y such that y — x (our previous element, which here is 7 and we’ll denote as x) must be in the interval from 0 to K inclusive, i.e., 0 <= y — x <= K.

So we’ll focus on the maximums; let’s take this case: 1334444 with K =any value. If D plays a 4, then they’re forced to play only 4, and boom — the parity logic breaks down, guaranteeing that E wins. The problem is that if this number is odd, then he cannot play 4 because it is guaranteed to be a loss, as in the example 133444.

The idea is that we can still win by playing the term immediately before it; for example, if we play 13[3444] ->, this forms an even number, so he can win because D plays 3, and so on, and E wins. The only condition is that the previous term must be played first, because if the larger one is played, then this one can no longer be played, so we lose. So here it must satisfy 0 <= 4 — 3 <= K; in this case, it is indeed possible because K = 5.

So here it must satisfy 0 <= 4 — 3 <= K; in this case, that’s perfectly possible because $K = 5. However, if $4 — 3 > K, then it doesn’t work, and so choosing 4 would result in a dead block because it can’t be combined with another. We therefore remove this dead block and reapply (mentally) this logic by taking the other maximum, that is, the last element just before this maximum.

Let’s go back to the example mentioned at the very beginning:

N ->13 K -> 2

array -> 2223344477777

Let’s start the loop from the end, that is, from the last 7, down to the very first element, which is 2. If we go down from there to the first 4 from the end, we will have had 5 seven in total. If D plays here, it is guaranteed that E loses because it is odd. Is it possible to create an even block with the element before it? That is, 2223344[4,7,7,7,7,7]? No, because 7-4 > 2, so it’s impossible to play in the 7 zone — it’s fatal — so we mentally remove it.

And let’s apply the same logic to 4: we count the number of 4s — boom, it’s odd because there are 3 fours. If it had been even, we could simply win by playing 4. The question is: is it possible to combine it with the element before it to form an even zone that’s also valid? Let’s test 2223[3444] (we’ve MENTALLY removed the other part) — it’s indeed even, but is it valid? Let’s check: 0 < 4 — 3 < K(2) — well, so it’s valid, so here E can totally win.

Do you see the power of parity, fellow coders?

THE CODE IN PYTHON : ~~~~~ import sys

def calcul(): n,k=list(map(int,input().split())) arr=list(map(int,input().split())) arr.sort() quantity=1 value=arr[n-1] for i in range(n-2,-1,-1): if arr[i]==value: quantity+=1 else: if not quantity%2 or value-arr[i]<=k: return "YES"

else:
            value=arr[i]
            quantity=1
if quantity%2:
    return "NO"
else:
    return "YES"

input=sys.stdin.readline

t=int(input()) for _ in range(t): print(calcul()) ~~~~~

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

    Here is the code in a better format : ~~~~~

    import sys

    def calcul(): 

    n,k=list(map(int,input().split())) 

arr=list(map(int,input().split())) 

arr.sort() 

quantity=1 

value=arr[n-1] 

for i in range(n-2,-1,-1): 

    if arr[i]==value: 

        quantity+=1 

    else: 

        if not quantity%2 or value-arr[i]<=k: 

            return "YES" 



        else: 

            value=arr[i] 

            quantity=1 

if quantity%2: 

    return "NO" 

else: 

    return "YES"

    input=sys.stdin.readline

    t=int(input())

    for _ in range(t): 

    print(calcul())

    ~~~~~

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

I think D is interesting because it is like DP on DAG. This is a good contest!

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

I implemented G just using lca not like all weak grandmasters who just implemented it using HLD

"Aura Farming!!!!"

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

For problem D, why does my submission TLE on test 12? This test came from a successful hack and I even tried running the test case on vscode and my code passed it nearly instantly.

Here is my submission 378441055

Here is the submission where the hack came from 378425504

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

solution for f2 using Polynomial Generating Function. TC= O (36^2 log N)
Link =(https://codeforces.me/contest/2236/submission/379129951)

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

can someone please share some problems based on invariance — like problem B.

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

I tried a lot to find bug in the code but, could not find any. However just declaring vis1 outside the loops gives the correct answer. Could you please review it once.

Correct Code
Code with Bug
→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Got TlE on D first but solved it afterwards

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

problem D can be solved for O(n)

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

D is a wonderful problem i think, possibly because i am a newbie

→ Reply