m3tr0's blog

By m3tr0, 4 weeks ago, translation, In English

2036A - Quintomania

Idea: m3tr0

Tutorial
Solution (myav)

2036B - Startup

Idea: Seny

Tutorial
Solution (Seny)

2036C - Anya and 1100

Idea: m3tr0

Hint
Tutorial
Solution (m3tr0)

2036D - I Love 1543

Idea: eugenechka.boyko.2_0-0

Tutorial
Solution (m3tr0)

2036E - Reverse the Rivers

Idea: m3tr0

Hint
Tutorial
Solution (m3tr0)

2036F - XORificator 3000

Idea: eugenechka.boyko.2_0-0

Hint 1
Hint 2
Tutorial
Solution (eugenechka.boyko.2_0-0)

2036G - Library of Magic

Idea: m3tr0

Hint 1
Hint 2
Tutorial
Solution (m3tr0)
  • Vote: I like it
  • +60
  • Vote: I do not like it

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

make better pretests next time.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone please explain what is logically wrong in this code: https://mirror.codeforces.com/contest/2036/submission/289551678 (it is failing on test case 35). thanks in advance!

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem F can also be solved using digit dp.

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

    i just read your lines that was really nice in the ending

    Mar Gaye Ehsaas Meray, Chubay Wo Ilfaaz Teray, Tumne Dekha Tak Na Jaty Way,

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

    I read a little bit of that code and it seems the code cant really solve for a number NOT a power of 2 (the constant time solution doesnt either). If I understand correctly you are checking if the first i bits of the number are different or not and xorring the remaining numbers. Can you extend your solution to range xor with a similar constraint but % x where x can be anything?

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

      Yes You are exactly correct, this code only handles when x is a power of 2. I had thought about the case when x is not a power of 2 and I could solve it for small values of x only($$$<=1000$$$) by having an additional state for the current remainder of the prefix.

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

        I couldn't find a better solution either, the best I could do was the same as you, I guess I should attach my code in case anyone in the future wants to know.

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

    can you explain your solution, especially how you are ensuring that the remainder is not k ?

    Thanks in Advance!

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

      A number mod power of two, $$$2^i$$$ is just the last $$$i$$$ bits in it's binary representation.

      We can use digit dp in the following way: Suppose you want to build an n digit binary number. Pick a digit (0/1 in this case) and place it at the leftmost space, you are left with n — 1 digits, now you need to count how many numbers are possible to be built in total after placing those n — 1 digits. To do this simply recursively start to add digits and keep track of whether the number you have built so far is a valid number or not. When you reach the end of the number, if the build is valid you return 1, otherwise 0. You can very efficiently count the possible valid numbers you can place in those n — 1 spots.

      Now if the count is odd then you know that your current digit (which you picked first) will appear in the net xor sum (If the picked digit was 1 of course, if it was 0 then it won't appear anyway), hence you can store this net xor sum by the following line:

      $$$xsum_i$$$ ^= (1 << (n — i — 1)) ^ $$$xsum_{i + 1}$$$ for both the digits 0/1 which you put in ith spot. This represents the transition.

      To store both the count of how many times the build starting from ith place to the end appears and xor of all such numbers can be stored separately in two different arrays or you can just use a pair or array<int, 2> like I did here: 290112812

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

        Hi man can you please explain how does this line actually works xsumi ^= (1 << (n — i — 1)) ^ xsumi+1

        the 1<<(n-i-1) is understood because it's just whether this current digit should be on or off based on the number we will get from the subsequent digits(dp(i+1)) but how are we effectively considering the previous digits ?

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

          I am certain this question arised because I didnt explain the dp state properly. xsum_i is the xor of all numbers which can be placed from position i to the end, with the limit of what digits i can place as o and u (read code). As you can see my function in fact returns xsum_0 at the end. The algorithm is simple once the dp state is clear. Focus the number built from index i to the end. You place a digit, and you find the new digit bounds, and then you use the calculations for the rest of the bits. Now the digit you placed, whether it will contribute to the final xor will depend on how many times numbers with this bit on, appears. Again, focus on the number built from i to the end. Amongst all possible numbers, the numbers with the bit on (at i) will be equal to the count of the possible ways in which i can place bits from i+1 to end with the digit bounds induced by placing the digit at position i onto the subsequent bits. This count, we are also storing in our dp states. We do not care about the previous digits for this particular dp state.

          To think of it iteratively, we start from the last bit, calculate all the dp states from that bit with all possible different digit bounds, then move to the bit before it, do the same and use the calculations already done for the bit just in right of it.

          If anything is unclear text me again.

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

    Hi can you please explain how does your cache table works?

    I have this simple code here https://ideone.com/YYmSO6 but currently it only can count the number of numbers that has curent_index==1 starting from current_index till 0th index

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

can anyone please tell me whats wrong with this solution 289604455

»
4 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

BitForces

»
4 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

If you don't know how to make testcases, don't make contests only for fun . L contest

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

289481978 why is this wrong , this is O(klogk)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but why did it give tle

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        In short, carefully constructed inputs will lead to hash collisions when inserting into/updating a dictionary in Python, and that results in a significantly worse time complexity and thus TLE (each individual insert/update can be O(n)). The link outlines how to avoid this issue. For this problem, you can also use a list/array.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

289592707 why is this wrong , can someone tell ?

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

    because you break the loop while reading, it will cause your next query reading the wrong input.

    Instead of if l>=r then break, use if l<r then solve()

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Alternate Solution for Problem G

Let $$$\text{XOR}(1, n)$$$ denote the XOR of all elements from the first to the $$$n$$$-th element in the array.

Case 1: If $$$\text{XOR}(1, n) = 0$$$, the numbers are structured to cancel out in pairs, leaving us with three values: $$$x$$$, $$$y$$$, and $$$x \oplus y$$$. We then query $$$\text{XOR}(1, h)$$$ for each $$$h$$$ starting from $$$h = 1$$$ until we find the smallest $$$h$$$ such that $$$\text{XOR}(1, h) \neq 0$$$. At this point, $$$\text{XOR}(1, h)$$$ isolates the first missing element $$$x$$$ because all other numbers in this subrange occur in pairs and cancel out.

Case 2: If $$$\text{XOR}(1, n) \neq 0$$$, we aim to locate the smallest subarray where $$$\text{XOR}(1, \text{mid}) = 0$$$. We perform a binary search to identify this position, isolating the unpaired number in that range. This number, $$$x$$$, is then equal to $$$\text{XOR}(1, \text{low})$$$ where low marks the boundary.

After identifying $$$x$$$, we search for $$$y$$$, the second unpaired element, starting in the range $$$[x+1, n]$$$:

We perform XOR queries from $$$a + 1$$$ to $$$\text{mid}$$$ until encountering a position where $$$\text{XOR}(x + 1, \text{mid}) \neq 0$$$. This value $$$y$$$ is isolated by $$$y = \text{XOR}(a+1, \text{low})$$$.

Finally, the third number $$$z$$$ can be computed as: $$$z = \text{total_xor} \oplus x \oplus y$$$

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

    Nice idea ! can u tell me why u used

    (in case where xor of 1 to n is 0 , I had same idea for everything else but couldnt figure out how to find first XD)

    while (query(1, temp) == 0)
            {
                temp = 2 * temp + 1;
            }
    

    instead of

    while (query(1, temp) == 0)
            {
                temp = 2 * temp;
            }
    

    The 2nd one is giving TLE , why it is guaranteed that one of them has 1st bit set ?

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

      when you are using former, it's guaranteed that the range has odd number of elements meaning (the pairs+the alone element), but if it has even number of elements in range the it would have (even number of pairs + 2 elements once, and would be the starting of another pair/the other removed element), so we won't really be able to find the solution via 2nd approach.

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

please try to improve your pretests next time

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

Could someone explain what went wrong for me in this submission for D?: https://mirror.codeforces.com/contest/2036/submission/289572926

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

    The loop for going over all spirals should be till min(m, n)/2 not n/2. I changed this part of your code and submitted it. Got AC.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think F can be solved in O(1) time instead of O(log r) since bitwise XOR runs in constant time.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

F is very nice, solved it using some bit tricks, but was thinking about some digit dp solution does it exits ? like dp(n, tight, flag) building n digit number with tight telling us that it is smaller than (say r) and flag telling us about if to take the new string number formed?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Code something like this
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So my code gets accepted when I use a 2D char array but not when I use vector<string>

(Fails on testcase 2)

Any idea what might be causing this?

Thanks!

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

UPD: Figured. I was breaking out of the loop at the end, which was skipping inputs.

For Problem E, the code works fine for test 9 (and gives correct output) on my PC as well as custom invocation (attached) but it gives RTE (on test 9) when I submit it. I am not able to find any undefined behaviour in my code. Can someone help me where the potential RTE could be in my code?

Submission

image

image

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

Can someone point out the logical errors in my code? Thanks. It's wrong on test 4, case 51.

void solve(){
    long long n; cin >> n;
    auto query = [&](long long l, long long r){
        cout << "xor " <<  l << ' ' << r << endl;
        long long res; cin >> res;
        return res;
    };
    auto solve = [&](long long lo, long long hi){
        if(lo > hi) return -1LL;
        while(lo < hi){
            auto m = lo + hi >> 1;
            if(query(lo, m)){
                hi = m;
            }
            else{
                lo = m + 1;
            }
        }
        return lo;
    };
    long long tot = query(1, n);
    long long A = -1, B = -1, C = -1;
    // find 2 ranges of A and B 
    long long p = 1;
    for(long long (*x) : {&A, &B}){
        long long next_p, l, r, res;
        while(p <= n){
            next_p = p * 2;
            l = p;
            r = min(next_p - 1, n);
            res = query(l, r);
            p = next_p;
            if(res) break;
        }
        long long y = solve(l, r);
        *x = y;
        if(y != res){
            if(B == -1){
                B = solve(y + 1, r);
                if(B == -1){
                    solve(l, y - 1);
                }
                if((B ^ A) != res){
                    C = res ^ A ^ B;
                    
                }
                break;
            }
            C = res ^ y;
            break;
        }
    }
    if(C == -1){
        C = tot ^ A ^ B;
    }
    // if((A ^ B ^ C) != tot){
    //     cout << "WR " debug(A) debug(B) debug(C) debug(tot) << endl;
    // }
    cout << "ans " << A << ' ' << B << ' ' << C << endl;
}

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

Seeing that many hacks in div3, especially in ABCDE problems is hilarious. I hope next time pretests will be much better. Great contest anyway.

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

can anyone help me... i really dont understand why should this be giving a wrong answer https://mirror.codeforces.com/contest/2036/submission/290070503

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

A simpler solution to the problem D. Hope this helps!!!

---CODE---


[problem:2036D]#include <bits/stdc++.h> #include<cmath> using namespace std; string s[1000]; string curr; void fun(){ int n,m; cin>>n>>m; for(int i = 0 ; i<n ;i++){ cin>>s[i]; } int top = 0; int bottom = n-1; int left = 0; int right = m-1; int count = 0; while(top<=bottom && left<=right){ curr.clear(); for(int i = left ; i<=right ; i++){ curr.push_back(s[top][i]); } top++; for(int i = top ; i<=bottom ; i++){ curr.push_back(s[i][right]); } right--; for(int j = right ; j>=left ; j--){ curr.push_back(s[bottom][j]); } bottom--; for(int j = bottom ; j>=top ; j--){ curr.push_back(s[j][left]); } left++; curr += curr.substr(0,3); for(int i = 0 ; i<=curr.size()-4 ; i++){ if(curr[i] == '1' && curr[i+1] == '5' && curr[i+2] == '4' && curr[i+3] == '3'){ count++; i = i+3; } } } cout<<count<<endl; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int t; cin>>t; while(t--){ fun(); } }
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Сan someone explain why this formula for calculating XOR(0;x) works? Why are we looking on x (mod 4)???

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

For problem C, I'm getting AC on the one given in the tutorial, and TLE in the code, which I've written. Thing is, both codes are exactly the same except for the format for input taking. Someone see to it. AC — https://mirror.codeforces.com/contest/2036/submission/291926108 TLE — https://mirror.codeforces.com/contest/2036/submission/291925987 infact, this one too gives TLE — https://mirror.codeforces.com/contest/2036/submission/291924193

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    In the check function, you are directly passing string s which results in a new copy everytime the function is called. Use pass by reference instead. Your Submission. The other one uses a global buffer.

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

For problem E, why Complexity:O(n⋅k+q⋅m⋅logn) won't TLE, (q is 1e5 and m is 1e5)

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

I have found a concept for 2036E - Reverse the Rivers in O(n*k+q(m+n)). Example here: 293121249. Interestingly it is not passing through test 6. Can anyone confirm it is asymptotically faster than the example Solution? And if that is the case, why is it not fast enough?

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

Can some one tell me why my solution to E is WA on test2? Thank you!

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

https://mirror.codeforces.com/contest/2036/submission/293980077 Can any one help me ? why I WA on test 2 ?