MikeMirzayanov's blog

By MikeMirzayanov, 4 days ago, In English

Hello, Codeforces!

Thank you all for participating in Codeforces Round 1134 (Div. 4)! I hope you enjoyed the problems and had a good time. Special thanks to everyone who helped prepare and test the round!

Below you will find tutorials for all the problems. If anything is unclear, feel free to ask questions in the comments. I would love to read about your solutions too!

2290A - Three Piles

Tutorial

2290B - Stubborn Pen

Tutorial

2290C - Books on a Shelf

Tutorial

2290D - Letters Down

Tutorial

2290E - Avalanche

Tutorial

2290F - Value Counters

Tutorial

2290G1 - Lakeside Trail (Easy Version)

Tutorial

2290G2 - Lakeside Trail (Hard Version)

Tutorial

2290H - Extra Road

Tutorial
  • Vote: I like it
  • +102
  • Vote: I do not like it

»
4 days ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Peak contest! Thank you

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

    why ? any reason ?

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Geniuenly amazing round! F was hard imo

»
4 days ago, hide # |
← Rev. 2  
Vote: I like it -32 Vote: I do not like it

Hi guys, sorry for posting this again, but I'm not sure about the proper process to appeal a ban.

I am writing from a new account so I'm unable to create a blog or dm directly.

My old handle is some_random_person, and I got banned in the contest also after I solved Problem A,B,C,D,E. I did a good amount of competitive Mathematics before entering competitive programming, which can help explain why I solved these problems pretty quickly.

I am willing to show proof that I wrote the code on myself (or my code, if allowed), but I'm not sure whether the content of the code would be enough; I'm willing to show my solutions for Educational Codeforces Round 196 (Rated for Div. 2), where I solved A,B,C,E during the contest, but I'm not sure whether the evidence is enough likewise.

I have previously commented in https://codeforces.me/blog/entry/158740, but I'm not sure whether my comment would be seen, I apologize if I am not supposed to post the same content again, and I can delete this post if the rules this is not the right place to post.

Edit: Fine I'll give up, I'm not even sure how I could prove myself now, sorry for messing up the mood by posting here, have a nice day to everyone reading this!

  • »
    »
    4 days ago, hide # ^ |
     
    Vote: I like it +2 Vote: I do not like it

    ruined the mood

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

    heh i am unable to solve the questions of div4 and it is known for the beginner and as per done dsa and solved more questions on leetcode and other platform but got stucked in the simple problem and it is very demotivating for me how to improve the coding part specially maths one in the cp .please guide me it would help me a lot and i would be thankful to you guide in a way that i start enjoying cp sometime it seems like watering the dry plant efforts are going in vane

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

      Hi, I suppose I am not the correct person to ask. But here's my thought in case anyone is interested, and I also hope it could offer some insights into how I approached the problem (instead of using AI or something): First of all I think it depends on what you specifically mean by math, I mean literally most of the questions usually involve some math knowledge. I don't want to spoil any of the solution to any of the questions, but if you're talking about things closer to just math like combinatorics I would recommend doing some competitive math (they were pretty good background knowledge at least for me), I could talk about a specific problem if necessary, but I'm just not sure whether it would count as spoiling if I talk about one of the problems in this contest right now

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

      i think most of the easy problems are not really math at all, but rather simple and clever observations, and maybe a bit of dsa.

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest! Some really interesting problems. Thanks for organizing!

»
4 days ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

For G2, during the contest I found $$$O(n \log^2 n)$$$ at first, and then I tried to optimize it. I don't know why this code is working in nearly $$$O(n \log n)$$$, but if you can find a countercase, I will be happy. 398292581

Fun fact: three minutes after my solution, I found the intended lol.

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

    I think it can be proven that A[i] can only change like 2 times. This holds by the order of your update (the 'work' function).

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

E just clicked for me, that it doesn't depend on the order of the moves but rather on the number of total moves and after that, it was just a matter of calculating total number of moves and see whether it is odd or even and that is it..

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

    can you explain how did you calculate the total number the only way I can think of is using segment tree, I'm a noob the proof in the editorial doesn't make sense to me

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

      #include <bits/stdc++.h> using namespace std; void solve() { int n, k; cin >> n >> k; vector<long long> v(n + 1, 0); long long moves = 0; for (int i = 1; i <= n; i++) { cin >> v[i]; moves += v[i]; } vector<long long> points(n + 1, 0); for (int i = n; i >= 1; i--) { if (i + 1 <= n) points[i] += points[i + 1]; long long cur = v[i] + points[i]; int cnt = i - max(1, i - k); moves += cur * cnt; points[i - 1] += cur; points[max(1, i - k) - 1] -= cur; } if (moves % 2 != 0) cout << "Alice\n"; else cout << "Bob\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) solve(); return 0; }
      • »
        »
        »
        »
        4 days ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        This can help.

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

          this should be the intended solution not that i%(k+1) biz, just need to optimize it for storing just the parity not whole values

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

            that's the smart part ig. int/long long in C++ gcc by default does a 2^31/2^63 modulo and also since we are taking a modulo wrt even number. the parity is preserved. It is a malicious but fine usage of UB in C++

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

            No, the intended solution should be the editorial. This is only the alternative solution.

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

              well the editorial is somewhat of an optimized version of this solution, but that could be difficult to understand for some people who have just started coding and don't have a very solid in it.

      • »
        »
        »
        »
        41 hour(s) ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        wait so your alg is about maximizing the number of moves made and then checking parity for bob and alice? does any order of moves maximize the number of moves or does that not matter for the problem?

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

          Well the order in which alice and bob pick the number doesn't matter, the number of moves regardless of that will remain same,as to why, that is pretty simple, it follows as

          intial config : a_1 , a_2 , a_3,.... a_i ,, a_j ,, a_n

          we let two index say i and j, i am trying to show that it doesn't matter on which index the operation is applied first, the resulting array remains same.

          i first then j

          a_1 + 1, a_2 + 1, a_3 + 1, .... a_i — 1,....., a_j,.....,a_n

          a_1 +2 , a_2 + 2, a_3 + 2, ... a_i — 1 + 1,...., a_j — 1,....., a_n

          j first then i

          a_1 + 1, a_2 + 1, a_3 + 1,....., a_i + 1,....., a_j — 1 ,....., a_n

          a_1 + 2 , a_2 + 2 , a_3 + 2, ,, .. a_i + 1 — 1 ,....., a_j -1 ,....., a_n

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

      A better way to understand these problems is through Grundy numbers and the Sprague–Grundy theorem, which are fundamental concepts in combinatorial game theory.

      They are particularly useful for solving impartial games.Games in which both players have exactly the same legal moves from any given position.

      The main idea is that instead of analysing the entire game state and all possible sequences of moves, we can assign a number (called a Grundy number) to each independent component of the game.

      We can then combine these numbers using XOR to determine whether the current position is winning or losing.

      After reading about this the solution given in tutorial definitely make sense to you.

      But yes it's somewhat advanced concept but it's always better to have more knowledge.

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest. Especially problem C

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

    Ohhh yess. I've really enjoyed 'C' too! Although I solved it with deque, it'd probably be easier to solve with some vectors and calculations :|

»
4 days ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Here is my idea for problem F today. (I used AI to help with my English grammar, because English is not my first language.)

We look at two values i and i + 1 to find their positions.

When I say "between i and i + 1", I mean the elements of the array p that are located strictly between the position of i and the position of i + 1 (in either order). Formally, if pos[i] is the position of value i in p, these are the elements p[k] such that k is strictly between pos[i] and pos[i + 1]. Let k be the number of these elements.

Also note that there is no integer strictly between i and i + 1, so every other value x satisfies either x < i or x > i + 1.

Key observation. The difference between b[i] and b[i + 1] depends only on the elements between i and i + 1 (including i and i + 1 themselves). Any other element x is on the same side of both i and i + 1, so it changes b[i] and b[i + 1] by the same amount, and it cancels out in b[i + 1] - b[i].

Case 1: i is before i + 1 in p
Case 2: i is after i + 1 in p

Both cases give the same formula, pos[i + 1] = pos[i] + b[i + 1] - b[i] - 1. We write them as two cases only because the direction of the movement is different.

How to build the array p
Cases where the answer is -1

Time complexity: O(n)

Memory complexity: O(2n), which is O(n)

Code: 398317784

Note
»
4 days ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Hi Mike , Thank you for the contest.

It's more of a technical point , the summations can be made cleaner by adding \limits right before mentioning the lower and upper bounds of the summation (or generally any structure product,cap,cup,etc..) , which sound more natural than floating boundaries , so instead of $$$\sum_{i=1}^n(g_i-h_i)\le k$$$ , $$$\sum\limits_{i=1}^n(g_i-h_i)\le k$$$ sounds better.

About the code , maybe having the implementation in a separate spoiler would be better ? , I mean some people prefer to implement the task even after spoiling the idea from the editorial.

Even though I couldn't attend in time , but I feel like C is harder than D , It feels like C needs more thinking than D , probably even with the knowledge requirement.

These are just few minor things I can note , but overall great contest , I'll upsolve later problems too,

»
4 days ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I solved D using a Sweep Line Algorithm 398294439

And solved E using Fenwick Tree with Range Update Point Query 398327494

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

Perfect contest!I enjoy it,thank you

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

Is it only me or did anyone else code lazy segment tree for F.

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

H can be solved by binary search and then checking if you can make all edges with value > mid,s nodes on a simple path

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

Could you please explain D. I didn’t quite understand the editorial.

  • »
    »
    3 days ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it 0 Vote: I do not like it

    In D, We need to find the number of letter which we applying operation on it.

    for this case abdc , first we apply operation in 'c' to 'a' as c -> b ->a ,in next operation we apply in 'd' to 'b' as d->c->b ,we can observe that here c -> b is common so our operation will be like this first d to c gives abcc , then c to b gives abbb and final aaaa ,so letter b , c, d is used in operation ,thus ans is 3

    so make an array for a to z with initial zero vectord(27, 0); ~~~~~

    vector<int>d(27, 0);
        for(int i = 0; i < n/2; i++){
            int up = s[i] &mdash; 'a';
            int down = s[n-1-i] &mdash; 'a';
            if(up > down) 
            swap(up, down);
    
            if(up < down){
                d[up]++;      
                d[down]--;      
            }
        }~~~~~
    

    decrease the value of char(end path) in array,and increase the value of char (start path), and compute the prefix sum of result array ,and count how many >0 are there.

        int cnt = 0, ans = 0;
        for(int i = 0; i < 26; i++){
            ans += d[i];
            if(ans > 0) cnt++; 
    
    }
  • »
    »
    3 days ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    I did it like the merge intervals problem.

    let "abcd" be the string I'll check all the pallindrome matching pairs

    a-d b-c

    then draw intervals first one from a to d and second from b to c because the interval a to d overlap b to c they become one i.e. a to d

    it means that when we will be converting all ds to as(to match the pallindrome pair) we will also be converting everything between a and d also to a

    so we need not bother about the second interval "b to c"

    so answer is the one interval "a to d" => 'd' — 'a' = 3;

    void solve()
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
     
        vector<vector<int>> v;
        for (int i = 0; i < n / 2; i++)
        {
            vector<int> vec = {s[i] - 'a', s[n - i - 1] - 'a'};
            sort(vec.begin(), vec.end());
     
            v.push_back(vec);
        }
     
        sort(v.begin(), v.end());
     
        vector<vector<int>> ans;
     
        for (int i = 0; i < v.size(); i++)
        {
            if (ans.size() == 0)
                ans.push_back(v[i]);
     
            if (ans.back()[1] < v[i][0])
                ans.push_back(v[i]);
            else
            {
                ans.back()[1] = max(ans.back()[1], v[i][1]);
            }
        }
        int count = 0;
        for (auto i : ans)
            count += i[1] - i[0];
     
        cout<<count<<endl;
    }
    
  • »
    »
    41 hour(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    i did something different. i took the min and max char for each i. then i sorted, then reverse. Then i set max and min for the first element. when ever the next elements coincides with the first, they get together. whenever it doesnt happen. i add that current range then start at the next.

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

but my code is so hard?

Снимок

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

D was such an interesting problem! I implemented it by brutly calculating if there is way to make the string a palindrome without making it a complete string of a's. If that took more than 25 moves, it would obviously be the wrong choice.

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

D was soooo good. Loved the contest

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

The solution to problem G2, which uses a Segment Tree for verification, and the structure is written “bottom‑up,” does not pass. Its asymptotic complexity is O(30nlogn), and the time limit is 4 seconds, but the solution gets a TL on test 3; given the speed of C++, this is very strange. (Решение задачи G2 использующие Дерево отрезков для проверки, причем структура написана "снизу-вверх", не проходит. Его асимптотика O(30nlogn), а ограничение по времени 4 секунды, но решение ловит TL на 3 тесте, учитывая скорость c++, это очень странно)

#pragma GCC optimize("O3,unroll-loops")
#define LOCAL
#include <bits/stdc++.h>
//#define int long long
using namespace std;
#ifdef LOCAL
    //constexpr int N = 1 << 5;
#else
    //constexpr int N = 1 << 18;
#endif
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct ST {
    int N;
    vector<pair<int, int>> tree;
    ST(int n = 0) {
        int k = 0;
        while((1 << k) < n) k++;
        N = (1 << k);
        tree.resize(N << 1);
    }
    void upd(int i, int x) {
        i += N;
        tree[i] = {x, i - N};
        while(i >>= 1) tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
    }
};
signed main() {
    #ifdef LOCAL
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        long long n, k; cin >> n >> k;
        vector<int> h(n), hh(n);
        for(int i = 0; i < n; ++i) {
            cin >> h[i];
            hh[i] = h[i];
        }
        ST tree(n);
        auto check = [&](const int &x) -> bool {
            long long sum = 0;
            h = hh;
            for(int i = 0; i < n; ++i) tree.upd(i, h[i]);
            for(int i = 0; i < n; ++i) {
                auto [mx, idx] = tree.tree[1];
                if(!mx) break;
                int idx1 = (idx + 1) % n, idx2 = (idx + n - 1) % n;
                if(h[idx1] + x < mx) {
                    sum += mx - x - h[idx1];
                    tree.upd(idx1, mx - x);
                    h[idx1] = mx - x;
                }
                if(h[idx2] + x < mx) {
                    sum += mx - x - h[idx2];
                    tree.upd(idx2, mx - x);
                    h[idx2] = mx - x;
                }
                tree.upd(idx, 0);
                if(sum > k) return false;
            }
            return true;
        };
        int l = 0, r = 1e9;
        for(int it = 0; it < 30; ++it) {
            int m = l + (r - l) / 2;
            if(check(m)) r = m;
            else l = m;
        }
        cout << r << '\n';
    }
    return 0;
}
  • »
    »
    3 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The expected complexity of G2 is $$$O(n \log h_{\text{max}})$$$, not $$$O(n \log n \log h_{\text{max}})$$$. The latter is expected to fail (if you try hard, you may have such solution to pass, though).

    You can locally measure the running time if you make a largest random input.

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

problem E can solve by using segtree:

Code
  • »
    »
    2 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    the tutorial E is very simple. I can't believe that there was hidden such a clever property within this problem.

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

any one can tell h

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why they put H on last , it was so easy

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Here is an alternative $$$O(n \log n)$$$ solution for problem H using binary search:

Solution
Code
»
30 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

W contest!