yud08's blog

Codeforces Round #982 (Div. 2) Editorial
By yud08, history, 6 hours ago, In English

Thank you so much for participating in our round! We really hope you enjoyed it. For us, it was an amazing and educational experience, and we look forward to the possibility that we could one day help to or hold a round again. Thanks again to abc864197532 and Vladithur for making the process so smooth and enjoyable.

2027A - Rectangle Arrangement

Tutorial
Code

2027B - Stalin Sort

Tutorial
Code

2027C - Add Zeros

Tutorial
Code

2027D1 - The Endspeaker (Easy Version)

Tutorial
Code

2027D2 - The Endspeaker (Hard Version)

Tutorial
Code
Tutorial (Segment Tree)
Code (Segment Tree)

2027E1 - Bit Game (Easy Version)

Tutorial
Code

2027E2 - Bit Game (Hard Version)

Tutorial
Code
  • Vote: I like it
  • +37
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it -86 Vote: I do not like it

D1 is the worst problem i've seen in recent times

→ Reply
»
5 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

Problem B is very tricky.

→ Reply
»
5 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

Good to know my first approach to 2027B was nlog(n). I couldnt think of O(n^2) solution for some reason.

→ Reply
»
5 hours ago, # |
  Vote: I like it +17 Vote: I do not like it

B and C were pretty good problems...D1 felt like a common DP problem

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

Can anyone explain why changing map to unordered_map in 2027C - Add Zeros causes a TL?

I even took the solution from the editorial and ended up with a TL.

Editorial solution with unordered_map 288191624 (TL 16)

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Worst case access for unordered_map is O(n), whereas worst case for ordered_map is O(log n). In unordered map, the values are stored in buckets modulo a big number. If the input is constructed in such a way that all elements get stored in the same bucket, the worst case time complexity to access a single element becomes O(n). Hence, causing the TLE

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    test cases are made in such a way that they cause collisions , as the worst time complexity is O(n) so it can't pass. If you still want to use hashmap you would have to make your own hash function. https://codeforces.net/contest/2027/submission/288190713

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    One way to bypass this issue is to declare a custom_hash. The worst case time complexity for this still remains O(n), but you could atleast pass the current input values since you can use a random number generator to hash the values. Add the following piece of code and let me know if it passes or not.

    struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<int, int, custom_hash>
    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you for your replies!

    I also found this amazing post explaining that.

    Blowing up unordered_map, and how to stop getting hacked on it

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

      Yeah, that's a great post. In the last contest, my submission to D was hacked for the very same reason..so this time, I made a custom hash function to minimize the risk of collisions for my solution to C

      → Reply
  • »
    »
    28 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also had the same thing.

    My guess is that based on this blog, https://codeforces.net/blog/entry/62393 test cases were created with large numbers of hash collisions.

    → Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

problem B

4

1 1 3 2

if we apply stalin then 2 will be automatically deleted and now we just have to remove 3 , then the resultant array will be 1 1 . The answer should be 1 .

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to remove some/none of the elements then apply operations on resulting array.

    → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial

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

B was really difficult to analyze (for me); Only able to solve A ,hoping to perform better in upcoming ones.

→ Reply
  • »
    »
    55 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because N<=2000 then you should think about an n^2 solution now we have no idea what that solution might be but every time we think about an n^2 solution we tend to fix some number in the array and loop. and here comes the idea of fixing the max element in the resulting array or the left most element in the resulting array. this was my thought process

    → Reply
»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

If anyone could explain D2 to me in detailed manner would be really helpful, thanks in advance..

→ Reply
  • »
    »
    18 minutes ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I solved this using segment trees. You need to define each node of the tree to have two parameters, "cost" and "count". When you combine the two nodes, if the costs are identical, you return a new node with the same cost and the sum of the two counts, otherwise, you return a copy of the node with the lower cost.

    Now, the problem is much simpler. Define dp as a list of length m+1 of these trees (each of size n+1), and initially set all nodes to have infinite cost. Then, update it such that dp[i][n] has cost 0 and frequency 1, for all i. Now, if we define dp[j][i] as the minimum cost to remove all elements from a[i] onwards, using all elements from b[j] onwards, it is clear we need to consider two transitions:

    1. Switching from b[j] to b[j+1] with no cost — we do this by filling in the dp with the outer loop going from n-1 to 0, and the inner loop going from m-1 to 0. Then we can just update dp[j][i] to be equal to dp[j+1][i].

    2. Transitioning from a[i] to a[i+k], for all k that it is possible to do in one go (which is solved the same way as D1, I did this using a sliding window approach in O(mn)). This transition is simply equivalent to querying the segment tree dp[j] from i+1 to i+k, because we have made the segment trees such that by combining nodes, you're automatically picking the ones with the lowest cost, and adding up the frequencies. This is all done in O(logn) time, adding up to a O(mnlogn) solution, which passes comfortably.

    I am told there is a much nicer solution but I'm far too daft to figure that out myself, so bashing the problem with a few too many segment trees seems to be the only option.

    → Reply
»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone please outline the two pointer approach for D1?

→ Reply
  • »
    »
    16 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    void solve()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    vector<ll> preSum(n + 1);
    ll maxA = 0;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxA = max(maxA, a[i]);
        preSum[i] = preSum[i - 1] + a[i];
    }

    vector<ll> b(m + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }

    // If the maxA is greater than b[1], it's impossible to perform any operations to empty a
    if (maxA > b[1])
    {
        cout << "-1\n";
        return;
    }

    vector<ll> dp(n + 1, inf);
    //  deleting 0 elements is 0 cost
    dp[0] = 0;

    // Iterate over array b
    for (int j = 1; j <= m; j++)
    {
        int l = 0, r = 1; // l is the left boundary of the prefix sum, r is the right boundary
        while (r <= n)    // While the right boundary does not exceed n
        {
            // Check if the current prefix sum difference exceeds b[j]
            while (l < r && preSum[r] - preSum[l] > b[j])
                l++; // If the prefix sum exceeds b[j], move the left boundary

            // If l is less than r, it means we can delete the prefix
            if (l < r)
                dp[r] = min(dp[r], dp[l] + m - j); // Update dp[r] with the minimum cost

            r++; // Move the right boundary
        }
    }
    cout << dp[n] << "\n";
}
    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve B using Monotoic Stack to find the maximum sub array that have the first element is largest? Time complexity will be reduce to O(n)?

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

Having an answer be 0 mod 1e9+7 for D2 is kind of crazy

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

Why my solution for Question C getting TLE

My solution 288152538

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

Problem c have also another solution

→ Reply
»
77 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

can some one please explain the last part in problem C if one didn't use a map

→ Reply
»
46 minutes ago, # |
  Vote: I like it +2 Vote: I do not like it

problem B "this will always break the non-decreasing property."

this should be "non-increasing property" ?

→ Reply
  • »
    »
    20 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you're right. The blog should update soon. Thanks for pointing it out.

    → Reply
»
28 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Why these indian cheaters do cheating by youtube and telegram groups, this leads to bad rank even on solving 3 problems ;(

→ Reply