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

Автор Stefan2417, история, 6 месяцев назад, По-русски

Мы надеемся вам понравились задачи.

Задача 1977A - Маленький Никита была придумана Stefan2417 и подготовлена alexchist

Задача 1977B - Бинарная покраска была придумана alexchist и подготовлена Stefan2417.

Задача 1977C - Никита и ТЧ была придумана и подготовлена Stefan2417.

Задача 1977D - XORофикатор была придумана и подготовлена alexchist

Задача 1977E - Тензор была придумана и подготовлена Stefan2417

1977A - Маленький Никита

Tutorial
Author's code
Feedback

1977B - Бинарная покраска

Tutorial
Author's code
Feedback

1977C - Никита и ТЧ

Hint
Tutorial
Author's code
Feedback

1977D - XORофикатор

Hint
Tutorial
Author's code
Feedback

1977E - Тензор

Tutorial
Author's code
Feedback
Разбор задач Codeforces Round 948 (Div. 2)
  • Проголосовать: нравится
  • +109
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится

better late than never. thank you for the editorial

»
6 месяцев назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Ooooh so you have a temporary third chain in E. I love it, it's close to what I was trying and makes it so elegant. Also thank you for the proof of existence using Dilworth.

The contest was of huge quality, one of my favorite codeforces. Thank you setters. orz

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

for the 2nd question; can anyone help me debug why/where is my logic wrong? its different than author's. https://codeforces.me/contest/1977/submission/262928317

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

Thanks for the editorial!

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

Does anyone know any similar problems to C, Want to improve on the concept of LCM, GCD and divisors.

»
6 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Does anyone know any similar problems to C,

Want to improve on concepts of LCM, GCD and divisors.

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

Yo for C can someone explain me this part?

"Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM."

It's not immediately clear why this will yield the max sequence bro

Edit: nvm I acc get it now it's clear from the tutorial, I'm so stupid bro

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

Thank you so much Stefan! I quite enjoyed figuring out the solve to question C, even if I only figured it out after the contest... Question B was satisfying as well.

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

what does this mean in C problem tutorial?? "Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM."

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Basically since all elements in a divide max(a), then any combination of elements in a will have an LCM that divides max(a) too. And for an LCM to belong to a sequence, it must be

    • divisible by all elements in that sequence
    • must match the actual LCM of that sequence

    Using those facts our search space is now the divisors of max(a) where we just need to check for those two facts and greedily get the maximum subsequence.

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

      crazzy bro,, great explaination. just one thing why this check is necessary in calc func? if (LCM != d) cnt = 0; as it will always be equal, right?

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        not always, take this for example:

        3 2 10 20 60 1

        here the overall LCM is 60 so we search over its divisors. If we choose 4, then only 1 and 2 divide it, but their LCM is 2 (which is acc in a), not 4. We're searching for a subsequence that has exactly that divisor as its LCM for this iteration so 4 is not even valid to consider.

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

      Very well explained. This should be a part of the editorial! Thanks bruh

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

Can someone explain the solution of Problem D. Only thing I am seeing is Xor and Random numbers. Totally Confused right now!!

PS: Understood the solution. But why are we keeping 2 random numbers of each index?

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

    To reduce the probability of collision. It's for the same reason that you use two modulos in hashing sometimes.

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

    Will you please explain it for us?

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

      Suppose we want the 1st column to contain exactly one 1. Then there are n options in which we can have that 1. Let's say we make the only one 1 at the first row itself. Then the set (of each row) of XORificator used will be unique. Similarly, it will be unique for each of the (i, j) if we decide that in the jth column the only 1 will be at ith row.

      So, now we will calculate all the unique set of XORificator, for which we have used hashing. Now, if the cnt[hash] is x that means x columns will contain only one 1 with the following set of XORificator. So, you can just choose the one with the most cnt and that will be your answer.

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

        Yep! Got the feel. Thanks.

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

        But we still have a non-zero probability of getting a wrong answer , right?

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

          No, it's actually 0, the only reason it might cause a wrong answer is when the hash values collide, where as seen in the editorial you can just store 2 values for the hashes, making the hash collision probability wayyy less(around 0 for the problem constraints), but a single hash suffices

          Why is the probability zero: Well, the lower bound of the answer is 1, cause you can just select a single column and invert every 1 except one. Now imagine You selected the column $$$i$$$ as the column with the single inverted 1, and the row $$$j$$$ as the 1 bit, since there is only a single way to make that cell $$$(i, j)$$$ to be one and none other $$$(i, k)$$$, the operations you chose are unique, so just save the resulting table best answer, and since there is no other way to fix $$$(i, j)$$$, if it was to fix $$$(i, j)$$$ this would be the best result, just take the maximum for every $$$(i, j)$$$

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

            Short answer: the only reason the probability for WA is 0 is just that for a fixed (i, j) there is only a single way to do it

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

            It is not zero, but a very small probability (negligible for the purposes of passing tests).

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

              which probability isn't zero? hash collision or the idea itself? (regarding of the hash function)

              Like there is a chance that not fixing anything will be the best answer? in that case there is at least 1 column is special(since we know that the answer >= 1), where its answer is calculated during the selection of that column and row

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

                You can't say that the probability is exactly zero unless you can make sure that there is absolutely not a single case where a hash collision that leads to wrong answer occurs, which is why we say it's a 'non-zero probability' because it is indeed not exactly zero, but negligible.

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

                  By zero I meant the prob of wrong answer not considering hash collisions, but yes, taking that into part even if u have 10000 different hash values for a single element there is always a way for the to collide even when n = 2, (and in my original comment I said unless hashes collide)

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

                  It seemed quite obvious to me that the original question was asking about whether hash collision can occur or not (because otherwise they wouldn't say terms like non-zero probability), so starting with saying directly "no, it's actually 0" to that question looked like you had some clear evidence that it can always avoid hash collision (or even if that occurs you still won't get wrong answer) somehow.

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

                  Ohh, I thought the question was asking if there is a chance the idea itself not being correct and giving wrong answer

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

                  yes , i was referring to the hash collisions. Can't we generate test cases for which there is high chances of collisions(considering the hash functions used)? Thanks

»
6 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

For B I did some uninteresting wack shit. Someone explain Jiangly or Tourist's solution for B please? They did something like % 4 = 1 then 1, % 4 = 3 then -1 and % 2 = 0 means 0.

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

In problem B, why is [-1 0 -1 -1 0 1] not a valid answer for x = 19? -1 + 0 + -4 + -8 + 0 + 32 = 19, so why am I getting wrong answer? Judge says "wrong answer. wrong coefficient format.", what am I doing wrong?

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

    Atleast 1 number for every pair of adjacent elements should be 0

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

      @SriRam523 How did you understand this point from the problem?

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

        In the constraints of the problem (at the top), it reads, "There does not exist an index $$$0≤i≤n−2$$$ such that both $$$a_i≠0$$$ and $$$a_i+1≠0$$$."

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

Could someone explain the hashing in D. I could come up with the idea of trying to fix a $$$i, j$$$ cell to be 1, but couldn't deal with the efficient XOR operations. What will we actually hash right here?

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    You want to count which configuration on the rows appearead most often : if a given configuration appeared n times, it means that there will be n special columns if you use it.

    So if you name a configuration "000110" for example (meaning flip rows 4 and 5 only), you want to hash this string to keep track of how many times it appeared. The issue is that you want this hash in O(1) time. Luckily, if, for each column, you try to make bit 1 special, then bit 2 special, etc... you will notice that the string representation of your configurations does not move much (only 1 or 2 characters change each time). So you want a hash that you can easily change in O(1) using this property instead of re-hashing in O(n).

    For this, you can use author's trick to prevent collision, or use a more classic technique of "rolling hash" which worked for me for example.

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

I believe there is a typo in C's tutorial, it should be LCM > max

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

I am unable to understand why I am getting WA in problem C.

submission

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

I am unable to understand why I am getting WA in problem C.

submission

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

    A possible reason:when you calculate the LCM of all elements, it will go beyond i64. So try to stop getting LCM as it becomes larger than the max element. (Cool painting btw)

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

For D I got the idea, but why if I use an unordered_map to keep track of how many time had a configuration appeared I will get a ME

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

    (At first, I wanted to use 01trie to maintain the times a configuration appeared but I think it would get a ME too.

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

Problem D can have also have deterministic solution rather than probabilistic one. we can write the solution for two different cases (m > n and m <= n). for m > n number of rows are less than 550, for a cell in the grid to be 1 the set of rows to be flipped can be encoded into a string (len < 550), complexity: n * n * m (n < 550). these strings can be stored in a map with their count and max count string is answer. unordered map can be used for speed up. for m <= n we can solve this using dp, where two columns differing at two or zero places are used for transitions, we check every pair of columns for transitions, answer can easily be constructed for a cell having max dp value, complexity: n * m * m (m < 550), max iterations ~ 1.65 * 10 ^ 8, safely under the time limit:

262840232

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

    hey i was also using the same approach but didnt separate the case of m>n and my sol tled.Nice to see i was half right for the dp.Thanks

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

Can someone please explain the time complexity of Question C?

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

Has anyone tried solving problem C with the Hasse graph (an edge $$$u \rightarrow v$$$ means $$$v | u$$$ )? It's easy to construct it in $$$O(n^2)$$$ but I can't find a way to maximize the set (I tried DP on graph). Eventually I did to the Brute force solution.

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

i'm struggling with problem C.

here is my approach.

[solve for N]

if N <= 1: return 0

if LCM(A[1] ~ A[N]) overflow A[N]: return N

if LCM(A[1] ~ A[N — 1]) == A[N]: find maximum length subsequence its LCM is not A[N] <- brute force

if LCM(A[1] ~ A[N — 1]) < A[N]: [solve for N — 1]

https://codeforces.me/contest/1977/submission/263102096

what is wrong with my code

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

In the authors code for D did he just ignore the possibility of collisions? If yes then is this normal in competitive programming to ignore collisions if chances are too low?

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

    Yep, if there's not a huge chance of collision then you can mostly ignore it

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

Honestly, don't know how I didn't realize that the LCM on C could be bounded that easily, I guess we have good and bad days

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

[RU] Здравствуйте! Не могу понять, почему мой код для задачи B проходит тесты на c++, но не проходит на c. Когда я выбираю компилятор c, то моя программа почему-то не проходит ограничение по времени на втором-третьем тесте. Объясните мне, новичку в c, где я ошибся.

[EN] Hello! I can't understand why my code for task B passes tests in c++, but does not pass in c. When I choose the c compiler, for some reason my program does not pass the time limit on the second or third test. Explain to me, a beginner in c, where I made a mistake.

#ifdef __cplusplus
  #include <cstdio>
  #include <cinttypes>
#else
  #include <stdio.h>
  #include <inttypes.h>
#endif

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define MAX_N 32

int main()
{
    uint32_t t;
    int n;
    short a[MAX_N + 1];
    
    scanf("%" SCNu32, &t);
    while (t--)
    {
        uint32_t x; scanf("%" SCNu32, &x);
        for (n = 0; x; ++n)
            a[n] = x & 1, x >>= 1;
        a[n] = 0;
        for (int i = 0; i < n; ++i)
        {
            if (a[i] == 2)
            {
                a[i] = 0;
                a[i + 1]++;
                continue;
            }
            if (a[i] == 1 && a[i + 1] == 1)
            {
                a[i] = -1;
                a[i + 1] = 0;
                a[i + 2]++;
                continue;
            }
        }
        if (a[n]) ++n;
        printf("%d\n%hd", n, a[0]);
        for (int i = 1; i < n; ++i)
            printf(" %hd", a[i]);
        puts("");
    }
}
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can the problem C be solved by Dynamic Programming ?

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

    you can solve it with recursive and memoization but you need to use unordered map

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

    262785009

    Check out this soln

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

      Thanks !!!

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

      Can you please explain the logic behind this part of your solution:- I am not able to understand it.

      if (mp[LCM])
          {
              // It is a factor
              ans = max(ans, 1 + func(p, LCM, a, n));
              ans = max(ans, func(p, val, a, n));
          }
          else
          {
              ans = max(ans, max(mp[a[p]] * 1ll, mp[a[p]] * 1ll + func(p + (mp[a[p]] - 1), LCM, a, n)));
              ans = max(ans, func(p, val, a, n));
          }
      
      
      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        if part

        if our current lcm which is val,if we take lcm(val,a[p]) ll LCM = lcm(val, a[p]); if after taking lcm our result LCM comes an element which is already present int mp[] that means it's the factor in that case we hope that in future we can form a sequence that doens't exit in mp other wise base condition return a large negative value =-1e17

        else part

        now we get out LCM which isn't present in mp[] that means we can form sequnce till that and also we can also increase our sequnce further

        but we have to store temporary ans that's why this max(mp[a[p]] * 1ll, mp[a[p]] * 1ll + func(p + (mp[a[p]] — 1), LCM, a, n))) first part in max return ans till that if we don't able to increase our length and 2nd part return the max if we can increase our length

        now why i use m[p] instead of 1 bc

        if we have element like 5 7 7 7 7

        we can just take 5 7 7 7 as whole rather than

        5 7

        5 7 7

        5 7 7 7

        hope u understand

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

Has anyone tried divide and conquer in B? There are 5726623061 sequences of {-1, 0, 1} lenght 32 with at least one zero among every 2 adjacent elements. We can bruteforce first 16 elements of the sequence, and use precalced values for other half.

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

I have another approach for C :

sort the array and check for the longest prefix such that lcm of that prefix is not the last element of the corresponding prefix.

is this wrong?

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

Stefan2417, problem E editorial is incorrect.

Let $$$n = 3$$$ and only one edge $$$1 \leftarrow 2$$$. According to the text solution $$$1$$$ will be white and $$$2$$$ will be black (or vice versa). Then the red stack is empty, but no vertexes are reachable from the 3rd. You said such a situation is impossible, but here it is.

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

    The editorial is incorrect, but the code handles this case correctly. In particular, the part

    if (ask(i, st.back())) {
      st.push_back(i);
    } else {
      st2.push_back(i);
    }
    

    does not match with the editorial; the editorial says that the vertex should be put into the empty stack by default, but the code puts it into the first stack, if the last vertex in the first stack is reachable from the current vertex, and into the second stack only if the aforementioned condition is not true.

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

In editorial C, What d(C) means?

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

In editorial C, why is O(N * d(C)) sufficient? Is'nt N <= 10**3 and C <= 10**9, thus O(d(C)) <= square root of C which is 10**4?

Would'nt O(N * d(C)) be 10**7 than?

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

[user:Stefan2417]Stefan2417

In Problem C this solution should not pass but it passes.

Please anyone try to hack it. https://codeforces.me/contest/1977/submission/263672671

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

I don't get C — Nikita and LCM. I understand that if the lcm of the whole array is equal to the max element in the array, then all elements divide the max. What I take from this is that the max element should not be in our solution subsequence.

What does "iterate over the divisors of the maximum" mean?

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

    It means that If all the elements in array A are divisible by max(A), LCM of any subset of A will be divisor of max(A).

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

For problem "B" how can it be a WRONG_ANSWER.Can anyone help? https://codeforces.me/contest/1977/submission/264399208

Input 7 1 14 24 15 27 11 19 Participant's output 1 1 5 0 -1 0 0 1 6 0 0 0 -1 0 1 5 -1 0 0 0 1 6 -1 0 -1 0 0 1 5 -1 0 -1 0 1 6 -1 0 -1 -1 0 1

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

282198440 Can anyone please tell me what's wrong in this ?

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

lastonemaman