AndreyPavlov's blog

By AndreyPavlov, history, 22 months 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: IzhtskiyTimofey
Preparation: IzhtskiyTimofey
Editorialist: IzhtskiyTimofey

Tutorial
Implementation (Python)
Implementation (С++)

1780F - Three Chairs

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: qualdoom

Tutorial
Implementation (С++)

1780G - Delicious Dessert

Idea: IzhtskiyTimofey
Preparation: IzhtskiyTimofey, AndreyPavlov
Editorialist: IzhtskiyTimofey, AndreyPavlov

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

| Write comment?
»
22 months 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!

»
22 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Has no one made a hack for C yet?

  • »
    »
    22 months 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.

  • »
    »
    22 months 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.

»
22 months 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.

  • »
    »
    22 months 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.

»
22 months 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?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I think it was to allow solutions that did not use priority_queue or something similar

»
22 months 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$$$"

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

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

»
22 months ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

delete

  • »
    »
    22 months 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

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it -60 Vote: I do not like it

      delete

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

        No

      • »
        »
        »
        »
        22 months 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?

»
22 months 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
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you found any counter-test for your solution?

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

      Yeah

      Spoiler
  • »
    »
    22 months 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.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lol

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      22 months 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.

»
22 months 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.

»
22 months 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))$$$.

»
22 months 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

»
22 months 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.

  • »
    »
    22 months 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.

»
22 months 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$$$

  • »
    »
    21 month(s) 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.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    22 months 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)$$$.

»
22 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
22 months 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.

  • »
    »
    22 months 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.

»
22 months 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)

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

Simple implementation for F 190544353

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      22 months 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.

»
22 months 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?
  • »
    »
    22 months 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.

    • »
      »
      »
      21 month(s) 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))?

      • »
        »
        »
        »
        21 month(s) 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.

»
22 months 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 !

»
22 months 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.

  • »
    »
    22 months 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.

  • »
    »
    22 months 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)$$$.

»
22 months 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

»
22 months 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?

  • »
    »
    21 month(s) 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.

»
22 months 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.

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

»
22 months 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

»
22 months 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!

»
22 months 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

  • »
    »
    22 months 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

»
22 months 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.

»
21 month(s) 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?

»
21 month(s) 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.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how do we get the root L bound in problem E. Can someone prove