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

Автор m3tr0, 3 недели назад, По-русски

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)
  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

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

make better pretests next time.

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

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

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

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

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

алсо 2: в русском едиториале очепятка. "Количество чисел равных $$$k$$$ ОП модулю $$$m$$$ равно ...", предлагается исправить

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

Problem F can also be solved using digit dp.

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

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

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

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

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

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

    Thanks in Advance!

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

      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

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

can anyone please tell me whats wrong with this solution 289604455

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

BitForces

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

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

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

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

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

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

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

289592707 why is this wrong , can someone tell ?

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

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

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

    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 ?

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

      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.

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

please try to improve your pretests next time

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

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

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

»
3 недели назад, # |
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.

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

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

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

A chad for doing it in C

»
3 недели назад, # |
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

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

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

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

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

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

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(); } }
»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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://codeforces.me/contest/2036/submission/291926108 TLE — https://codeforces.me/contest/2036/submission/291925987 infact, this one too gives TLE — https://codeforces.me/contest/2036/submission/291924193

  • »
    »
    5 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

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

      Thanks a lot man, it really made me learn something new

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

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