AndreyPavlov's blog

By AndreyPavlov, history, 11 days ago, translation, In English

1780A - Hayato and School

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: AndreyPavlov

Tutorial
Implementation (Python)
Implementation (C++)

1780B - GCD Partition

Idea: 74TrAkToR
Preparation: qualdoom
Editorialist: qualdoom

Tutorial
Implementation (Python)
Implementation (С++)

1780D - Bit Guessing Game

Idea: AndreyPavlov
Preparation: qualdoom, AndreyPavlov
Editorialist: qualdoom, AndreyPavlov

Tutorial
Implementation (Python)
Implementation (С++)

1780E - Josuke and Complete Graph

Idea: T4M0FEY
Preparation: T4M0FEY
Editorialist: T4M0FEY

Tutorial
Implementation (Python)
Implementation (С++)

1780F - Three Chairs

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: qualdoom

Tutorial
Implementation (С++)

1780G - Delicious Dessert

Idea: T4M0FEY
Preparation: T4M0FEY, AndreyPavlov
Editorialist: T4M0FEY, AndreyPavlov

Tutorial
Implementation (t4m0fey)
Implementation (AndreyPavlov)
 
 
 
 
  • Vote: I like it
  • +348
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +46 Vote: I do not like it

Can't wait for the solution of C. Show us guys, how to solve NP-hard problems!

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Has no one made a hack for C yet?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    The tester code probably uses the same faulty algorithm so it would be to no avail.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    The author's solution is wrong. Therefore, any hack would still get AC, even if the output is incorrect.

»
11 days ago, # |
  Vote: I like it +80 Vote: I do not like it

Problem D was very interesting :) ,one mistake and whole efforts of problemsetters and testers got ruined.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it -14 Vote: I do not like it

    I thought D was easier than B. Although I kinda over complicated B for no reason.

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

Weren't the incorrect greedy solutions for C O(n)? Why was the constraint on the problem O(n^2) then?

»
11 days ago, # |
  Vote: I like it +19 Vote: I do not like it

On the last row of Tutorial of B:

"Let $$$s$$$ be the array $$$a$$$"

should probably be

"Let $$$s$$$ be the sum of the array $$$a$$$"

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    They probably used machine translation. The solution to E is impenetrable.

»
11 days ago, # |
  Vote: I like it -21 Vote: I do not like it

Is it not possible to remove problem C for everyone?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    It's a bad idea because some poor people like me spent ~30min trying to solve it and ~20min trying to understand why so many people solved such a hard problem xd

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -60 Vote: I do not like it

      The conditions were all the same and a good time was also announced. so in my opinion, it is fair to remove it

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        No

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        LOL. Some people solved C with incorrect solutions that they figured out within minutes and moved on. And those who realized that solution is incorrect will be punished. What kind of fairness is that?

»
11 days ago, # |
  Vote: I like it +95 Vote: I do not like it

My solution failed system tests on C because it got a better result than the author's one, lol

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

    Did you found any counter-test for your solution?

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

      Yeah

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

    They should have asked for the exact assignment instead of just the maximum value, so that they can check for a FAIL verdict correctly. (FYI, FAIL is the verdict when the submission found a better solution than the jury's) They might have found the issue before the contest if this was the case.

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

    lol

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

    how it should be 11 can u explain it bit more clearer...

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

      There are 6 guests who likes the dish #1, and the remaining 5 likes the #2. So if we split the 6 guests in table #1 and #2, and the 5 who like #2 at table #3, all 11 guests will be happy.

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

    my code gives output 11 and it was accepted which was incorrect. can you please explain your logic or provide your code.

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

Problem G is quite similar to this problem. I had to modify my solution for the Educational round problem a bit to get AC on this round's G.

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

Problem B Video Editorial Link : https://youtu.be/EmMdN5P0BhI

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

Guys for E, will finding distinct gcd's for pairs of numbers in the range l,r work? If yes what's the optimal way to do it?

»
11 days ago, # |
Rev. 10   Vote: I like it +22 Vote: I do not like it

A brief tutorial to problem E, for people like me who cannot follow the official one:

Value $$$x$$$ will appear in one of the edges iff: $$$L \leq px < (p+1)x \leq R$$$, where $$$p=ceil(\frac{L}{x})$$$.

Now we enumerate every value of $$$p$$$ and count the number of possible $$$x$$$ for each $$$p$$$.

For $$$p=p_0$$$, the above inequality gives range of x: $$$\frac{L}{p_0} \leq x \leq \frac{R}{p_0+1}$$$.

Note that there is a hidden constraint of $$$ceil(\frac{L}{x}) = p_0$$$. This translates to $$$\frac{L}{p_0} \leq x < \frac{L}{p_0-1}$$$.

Combine the two ranges above, we get, for $$$p=p_0$$$, possible values of $$$x$$$ satisfies: $$$\frac{L}{p_0} \leq x \leq min(\frac{R}{p_0+1}, floor(\frac{L-1}{p_0-1}))$$$.

And we use sqrt decomposition to solve this counting problem: For $$$p\leq sqrt(L)+1$$$, we compute the range of $$$x$$$. For $$$p > sqrt(L)+1$$$, we have $$$x \leq sqrt(L)$$$, so we can just iterate through all $$$x$$$ values.

Complexity is $$$O(sqrt(L))$$$.

»
11 days ago, # |
Rev. 7   Vote: I like it +3 Vote: I do not like it

In C question greedy solution fail on test case-

1

11 3

1 1 1 1 1 1 2 2 2 2 2

5 4 2

correct answer for above testcase = 11, but greedy solution gives answer = 10

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

Can anyone explain what was the intended solution for C, which turned out to be incorrect.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Group people by what they like, and while there are groups of people and tables left, try to put the largest group on the largest table. If they don't fit, just use as many as you can and subtract that amount before deleting the table. If they do fit, delete the group of people and the table. "Answer" is however many people this process gives a table. The original might've been slightly different, but this is the silly wrong solution I got AC with.

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

In Problem D, in 2nd Tutorial (by qualdoom), for the condition (pt.2) where "$$$cnt-cnt_{new}\not=1$$$", can someone kindly explain the part, how this below equation is formed?

$$$m - k - 1 = cnt_{new} - cnt$$$

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

    Consider the real number is 24 its binary representation is 11000, and you need to guess this number. also, you can't subtract a number greater than the real number so if we subtracted 1 from real number which was 24, we will have 23 which its binary representation is 10111 so the number of unit bits has been changed and become 4-unit bits instead of 2 how this happened? hence, we now have 23 which has 4-unit bits and previous has 2 so the LSB at index (4-2+1) 0-based we add 1<<lsbIndex to obtain the real number. I hope that helped you.

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

Who can explain me, how to use mobius function in problem F?

  • »
    »
    11 days ago, # ^ |
    Rev. 27   Vote: I like it +9 Vote: I do not like it

    When you want to get $$$f(d) = \#func(a, b)$$$ where $$$gcd(a, b) = d$$$. You can count $$$g(d) = \#func(a, b)$$$ where $$$d | a$$$ and $$$d | b$$$.

    Then $$$f(d) = \sum_{i=1}^n g(i * d) * \mu(i)$$$

    Where $$$\mu(x)$$$ is the mobius function.

    Then you need to count for each number $$$k$$$ from 1 to max $$$a_i$$$, the number of triplets $$$(a_i, a_j, a_k)$$$ with $$$k | min(a_i, a_j, a_k)$$$ and $$$k | max(a_i, a_j, a_k)$$$.

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

took nearly an hour for B because I thought you had to split it into k equal parts lol

»
11 days ago, # |
  Vote: I like it +12 Vote: I do not like it

I don't know why. I want to comfort the author. qnq

»
11 days ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Can someone give a test case where this approach gives a wrong answer to C?

  1. Calculate how many meals of each type and how many tables of each size there are.

  2. Go through the meals, if there is a table with the same size as the count of that meal, then put those people to that table.

  3. Put remaining meal and table counts to two priority queues. While there are still some empty tables or not all people has a spot: take the top of meals and put them at the biggest empty table, if some people who like that meal are still left, check if there is empty table with that amount of spots, if there is put them there, otherwise put that number back to priority queue.

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

    Ok, here's a counterexample: tables are 2 2 3 and people are 1 1 1 1 2 2 2. The second step goes as no-op, so you will take ones into the third table (which has 3 seats) and then twos are placed in the remaining first/second table, which is not a correct strategy since you could have placed ones into first and second table and then remaining twos into the third table.

»
11 days ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

My approach for D (similar to the second tutorial solution, it seems, but it doesn't explicitly need flags and might be easier to understand for some):

To determine whether the last bit is 0 or 1, we can simply subtract 1. If the last bit was a 1, then it becomes 0 and the $$$cnt$$$ decreases by exactly 1. Now that the last bit is already 0, we can check the second-to-last bit by subtracting 2. In general, if the last $$$k$$$ bits are set to 0 while the rest of the bits are unchanged from the original, we can test bit position $$$k$$$ (from the right) by subtracting $$$2^k$$$ and seeing if $$$cnt$$$ decreases by exactly 1.

But what happens when the bit at the position we're testing (let's say position $$$k$$$) is actually a 0? In that case, $$$cnt$$$ either stays the same or increases, so we know that this position originally has a 0. However, this attempted subtraction of $$$2^k$$$ ruins our desired pattern, because the bit at position $$$k$$$ changed from 0 to 1 and at least one bit on its left has changed. We would have wanted the bits from up to position $$$k$$$ to all be 0 and everything else unchanged in order to test the next bit, at position $$$k + 1$$$...

We can deal with this by "undoing" the latest undesirable subtraction by instead treating it as part of the next subtraction. Normally, the next subtraction is supposed to be $$$2^{k + 1}$$$, but since we already performed an undesirable subtraction of $$$2^k$$$, we simply subtract another $$$2^k$$$ to result in a overall subtraction of $$$2^{k + 1}$$$ as if the undesired subtraction never happened.

Note that there could be a sequence of undesirable subtractions, in which case, we just keep track of the total of the undesirable subtractions and treat them all as part of the next subtraction. Eventually, we would have to find a 1, which resolves all these undesirable subtractions. Once we find the MSB, the $$$cnt$$$ should become 0, at which point, we are done.

My submission: 190561881 ($$$acc$$$ is the accumulation of undesired subtractions that we are trying to undo)

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

Simple implementation for F 190544353

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

    Can you explain your solution if it's different from the editorial?

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

      I have similar solution. Mine is: calculate $$$dp[x]$$$ -- number of ways to choose a triple which value of gcd is $$$x$$$. To calculate amount of such triples for every $$$x$$$ sort an array then for every $$$x$$$ consider only numbers which are divisible by $$$x$$$, let their indices be $$$ind$$$, we should calculate sum over all $$$i < j$$$ of $$$ind_j - ind_i - 1$$$, we can calculate it by iterating over these indices storing sum of considered indices and their cnt. Then you have a $$$dp$$$ where you should substract from $$$dp[x]$$$ $$$dp[2 * x], dp[3 * x], ...$$$ to obtain correct answer.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. What is the correct solution for problem C then, if it exists?
  2. In the editorial for problem E, it is mentioned that for g<L, ceil(L/g) will have O(sqrt(L)) values, how?
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Consider for g<sqrt(L) and g>sqrt(L) respectively, for the first situation there's at most sqrt(L) values of g, so ceil(L/g) will have at most sqrt(L) values. For the second situation, we have 1<=ceil(L/g)<L/g+1<L/sqrt(L)+1=sqrt(L)+1, so there's at most ceil(sqrt(L)) different values.

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

      How to generate all values of ceil(L / i) where i belongs to [1, L] in O(sqrt(L))?

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

        First let i = 1 to ceil(sqrt(L))-1. For the remaining values, for m = L/ceil(sqrt(L)) to 1, calculate the range where ceil(L/i)=m.

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

Can anyone explain in first tutorial of problem D, how does the initial algorithm makes 60 requests at worst?

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

I did the same thing in problem B yet kept getting TLE. Can someone point out my mistake. Thankyou!

while(test--)
    {
        int n;
        cin >> n;
        int * arr = new int[n];
        int * cuml = new int[n]; //Cuml is for cumalative sum
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
            if(i==0)
            {
                cuml[i] = arr[i];
            }
            else
            {
                cuml[i] = arr[i] + cuml[i-1];
            }
        }
        int ans = 0;
        for(int i = 0; i < n-1; i++)
        {
            if(cuml[n-1]%cuml[i]==0)
            {
                ans = max(cuml[i],ans);
            }
            else
            {
                int temp = gcd(cuml[i],cuml[n-1]);
                ans = max(temp,ans);
                cerr << temp << '\n';
            }
            
        }        
        cout << ans << '\n';
    }

Please help !

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

What is the time complexity in F and why is it quick? IMHO we have O(N * 2^(an average number of prime divisors)) so it doesn't seem like a quick solution.

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

    lets think like this. you know the number of divisors of a number n is O(log(n)). now you are only iterating on SOME of these divisors.

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

    Let $$$preres_x$$$ be the number of ways of choosing the triplets where the $$$gcd(a_i,b_j)$$$ is a multiple of $$$x$$$ and $$$res_x$$$ be the number of ways of choosing the triplets where $$$gcd(a_i,b_i)$$$ is exactly $$$x$$$. You can calculate array $$$res$$$ from $$$preres$$$. If you know the values of $$$res_y$$$ for all $$$y$$$ (where $$$y$$$ is a multiple of $$$x$$$) and $$$preres_x$$$, then you can calculate the value of $$$res_x$$$ and finally, $$$res_1$$$ will be the answer. You can do this by iterating from $$$3*10^5$$$ to $$$1$$$.

    The time complexity is sum of harmonic sequence $$$\sum_{x = 1}^{N} \left \lfloor \frac{N}{x} \right \rfloor$$$ which is equal to $$$O(nlogn)$$$.

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

Of all the rounds this had to happen in a round full of Jojo's references

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

Can someone please tell me what was wrong with C? My approach to solving C was: Group all the guests having the same liking. Now assign the biggest group to the largest table. If some guests are still left, insert them in the priority queue and continue this way.

How was C an NP hard problem?

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

    I did exactly the same, and I'm quite curious about the issue with it too. (Hope that the editorial will come out soon).

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

    Your approach is incorrect. Consider the following scenario:

    • 6 people like dish 1, and 4 people like dish 2.
    • Three tables, with capacities 3, 3, and 4 respectively.

    If you assign the biggest group to the largest table, then the 4-table serves dish 1 (all four like it), one of the 3-tables serves dish 2 (all three like it), and the other 3-table serves dish 1 (two out of three like it), with one unsatisfied guest. But if you instead had both 3-tables serve dish 1 while the 4-table serves dish 2, then everyone would be satisfied.

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

Why did you delete issue C?

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

Even though C couldn't be solved with given constraints during the contest I think it's better to lower constraints to make it solvable, write a proper solution and post the updated solution in the editorial, instead of completely removing it from the contest and archive. The problem is not bad at all, tbh.

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

    It's NP-hard, which means it almost certainly cannot be solved in polynomial time. Constraints would require $$$n$$$ to be about $$$20$$$, or maybe even less! The brute-force solution would be incredibly dull. There may be heuristics to speed it up and allow a little higher constraints, but this is not suitable for CP.

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

      Doesn't mean it can't be solved at all. Better to keep a modified version with extremely low constraints than to remove it completely.

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

Can anybody tell me "correct" solution of C? or at least some ideas

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

    Normal greedy method would fail the pretest (before it was deleted of course). My idea was to apply the data structure priority_queue, and for each current type of dish with the maximum number of people, compare it with the current largest table. If there are people left, insert this into the queue and repeat the process until there are no more people or no more tables. The main part of my code was:

    priority_queue<int, vector<int>, less<int> > q;
    sort(alls(c), cmp);
    for (int i = 0; i < maxn; i++) {
        if (cnt[i] != 0) {
            q.push(cnt[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (q.empty()) break;
        int t = q.top(); q.pop();
        int cap = c[i];
        ans += min(t, cap);
        if (t > cap) {
            q.push(t - cap);
        }
    }
    cout << ans << endl;
    

    Where $$$c$$$ denotes the tables and $$$cnt$$$ is used for counting the number of people for each dish.

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I would surely become a specialist after this round (rank 16) but...... It's unrated! And problem G is kind of rigid that almost everyone who has learnt sam before can solve it.

But anyway,the problems are excellent!

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

can someone explain what's wrong with problem C. Instead of posting correct solution why authors completely removed problem C

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

    There is no correct solution to that problem. It is a NP-hard problem which cannot be solved in polynomial time

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

D was quite confusing cuz I have never solve interactive problems lol. F was easier than normal :V.

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

I am getting TLE on test case 3 for problem D. Please help, sumbission:190734004

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

[del]

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

I don't understand the tutorial for problem G. Can anyone explain the idea of it?

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

Does any one know how to calculate the time complexity of G? More detailedly,the time complexity of find the number of x,which is a factor of n, that l<=x<=r? The solution implied that is almost nlog(n) in total , but I can't understand why.