m3tr0's blog

By m3tr0, 46 hours 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
  • +47
  • Vote: I do not like it

»
40 hours ago, # |
  Vote: I like it -8 Vote: I do not like it

make better pretests next time.

  • »
    »
    36 hours ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    true

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

    true

»
39 hours 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://codeforces.net/contest/2036/submission/289551678 (it is failing on test case 35). thanks in advance!

»
39 hours ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem F can also be solved using digit dp.

  • »
    »
    37 hours 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,

  • »
    »
    11 hours 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?

    • »
      »
      »
      3 hours 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 hours 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!

»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please tell me whats wrong with this solution 289604455

»
38 hours ago, # |
  Vote: I like it +27 Vote: I do not like it

BitForces

»
36 hours 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

»
36 hours ago, # |
  Vote: I like it -16 Vote: I do not like it

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

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

      but why did it give tle

      • »
        »
        »
        »
        35 hours 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.

»
36 hours ago, # |
  Vote: I like it -9 Vote: I do not like it

289592707 why is this wrong , can someone tell ?

  • »
    »
    4 hours 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()

»
36 hours 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$$$

»
35 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

please try to improve your pretests next time

»
35 hours 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://codeforces.net/contest/2036/submission/289572926

  • »
    »
    20 hours 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.

»
35 hours 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.

»
33 hours 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?

  • »
    »
    33 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Code something like this
»
27 hours 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!

»
16 hours 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

»
14 hours 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;
}

»
12 hours 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.