Блог пользователя m3tr0

Автор m3tr0, 46 часов назад, По-русски

2036A - Квинтомания

Идея: m3tr0

Разбор
Решение (myav)

2036B - Стартап

Идея: Seny

Разбор
Решение (Seny)

2036C - Аня и 1100

Идея: m3tr0

Подсказка
Разбор
Решение (m3tr0)

2036D - Я люблю 1543

Идея: eugenechka.boyko.2_0-0

Разбор
Решение (m3tr0)

2036E - Пустить реки вспять

Идея: m3tr0

Подсказка
Разбор
Решение (m3tr0)

2036F - XORофикатор 3000

Идея: eugenechka.boyko.2_0-0

Подсказка 1
Подсказка 2
Разбор
Решение (eugenechka.boyko.2_0-0)

2036G - Библиотека Магии

Идея: m3tr0

Подсказка 1
Подсказка 2
Разбор
Решение (m3tr0)
Разбор задач Codeforces Round 984 (Div. 3)
  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
40 часов назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

make better pretests next time.

  • »
    »
    37 часов назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится

    true

  • »
    »
    33 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    true

»
40 часов назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 часов назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

спасибо за местечко в разборе! задача F мне очень зашла еще при тестинге, особенно, когда я решал ее вместо географии :)

алсо: чтобы название функции в $$$\LaTeX$$$ отображалось без наклона и при этом не надо было писать \text, то можно написать \DeclareMathOperator{\shortname}{displayname}

»
39 часов назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Problem F can also be solved using digit dp.

  • »
    »
    37 часов назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Thanks in Advance!

»
38 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone please tell me whats wrong with this solution 289604455

»
38 часов назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

BitForces

»
37 часов назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

L contest , if you don't know how to make test cases don't make contests

»
37 часов назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

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

»
37 часов назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

»
36 часов назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

289592707 why is this wrong , can someone tell ?

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 часов назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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$$$

»
36 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please try to improve your pretests next time

»
35 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    20 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 часов назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
34 часа назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 часа назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Code something like this
»
27 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
24 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A chad for doing it in C

»
17 часов назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
}

»
13 часов назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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