When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

sevlll777's blog

By sevlll777, history, 12 months ago, translation, In English

Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers.

1798A - Showstopper

Hint 1
Hint 2
Tutorial
Solution
Rate the problem

1798B - Three Sevens

Hint 1
Hint 2
Tutorial
Solution
Rate the problem

1798C - Candy Store

Hint 1
Hint 1.1
Hint 1.2
Hint 2
Tutorial
Solution
Rate the problem

1798D - Shocking Arrangement

Hint 1
Hint 1.1
Hint 2
Tutorial
Solution
Rate the problem

1798E - Multitest Generator

Hint 1
Hint 2
Hint 2.1
Hint 3
Tutorial
Solution
Rate the problem

1798F - Gifts from Grandfather Ahmed

Hint 1
Hint 2
Hint 3
Hint 3.1
Hint 4
Tutorial
Solution
Rate the problem
  • Vote: I like it
  • +262
  • Vote: I do not like it

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

Shows me , posted 5 days ago, fastest editorial ??

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

Oh, a tutorial with Python code, how avant garde

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

E can be passed by brute forcing all possible positions to change. Not sure if its provable but I couldn't think of any hack cases when coding it. https://codeforces.com/contest/1798/submission/199283535

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    This case can hack it.

    1

    100000

    1 49999 1 1 1 1 ...... 49999 1

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

Really great round, problems till D felt pretty solvable. Although managed to solve only 2 but had fun.

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

Fastest Editorial but I wanna unsolve first...

»
12 months ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

In Problem D:

Can anyone tell me the ans of test case:

1

5

1 2 3 -30 -20

According to my understanding, the ans should be No, as sum of abs(-30 + -20) > max(3) — min(-30), but many of the passed solutions are outputing Yes

Edit: Got it, forgot to read the very first line of question

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

    The sum of the array needs to be 0

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

    a1 + a2 + a3 + ... + an = 0 this does not hold in your case.

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

WoW! The editorial dropped faster than my rating :)

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

WOW! Lightning fast editorial

»
12 months ago, # |
Rev. 6   Vote: I like it +12 Vote: I do not like it

Problem B is very similar to Kahn's algorithm.

code
»
12 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

You can solve C by abusing the fact that LCM grows fast too.

Greedily try to make segments of the same cost. Naive $$$O(n^2)$$$ is to check if you can make the cost for the current range equal to $$$lcm(a[rstart, i])$$$ for every $$$i$$$, but you only need to do the $$$O(n)$$$ check if the value of LCM changes between $$$i-1$$$ to $$$i$$$. If it doesn't change you already know it's possible for the range $$$[rstart, i-1]$$$. So you just need to check if you can include $$$i$$$ in the range. 199293298

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

Did you not include a pretest with n=3e5 in D on purpose?

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

    Also he did not include a pretest with n=2e5 in C on purpose.So my C and D are all hacked haha.

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

      Also no pretest with 50000 on B, causing my rank to drop from 2700 to 7000.

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

    Can you tell me what I'm doing wrong submission? It failed in test case 10 of problem D.

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

The system test of problem E is too weak. My brute force solution passed it, and it can be hacked by a very simple testcase. Please be more careful for preparing testcases.

Link:199296293

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

This was kind of a hope greedy works contest imo.

In both c and d i was like "i hope this covers all cases, let's submit". I don't really like this kind of problems

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

    That's so true man I did the same with C then I could not think about the solution of D so with 5 minutes remaining just coded up whatever came to mind and it got accepted with 15 seconds remaining hehe.

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

      True, turns out that in d you can just assign any valid value and repeat for each element of the array and it's guaranteed to find the solution

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

      niceee, good to know people with 1600 rating are also HOPING for solutions to cover all cases , not just me

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

Please explain C someone ???

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

In C, according to tutorial if we solve for prefixes like:

{[a1, a2, a3] [a4, a5, a6] [a7, a8, a9, a10]} have price tags {c1, c2, c3} and c1 becomes equal to c3. the solution should fail, correct me where I'm wrong.

Edit: I read the question wrong

»
12 months ago, # |
Rev. 4   Vote: I like it +33 Vote: I do not like it

Problem D was easier than Problem C... Is it?

»
12 months ago, # |
Rev. 2   Vote: I like it +55 Vote: I do not like it

(For problem F) I had never heard of the Erdős--Ginzburg--Ziv theorem but I guessed that it had to be true by the fact that none of the samples had "-1" as an answer.

For those curious, an elementary proof is in the second response here.

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

    Why that proof need to reduce the original problem to the case when n = prime?

    Does any step using the property that $$$p$$$ is a prime?

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

      Yes, because it assumes a-b is relatively prime with p when a != b

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

In C, I really thought as long as the biggest bi (i.e max(b1,b2...bn) could divide the GCD, it should be fine. It took me like an hour after the contest ended to figure out why this wouldn't work.

Love it when my brain turns off when I need it.

»
12 months ago, # |
  Vote: I like it -42 Vote: I do not like it

Did not participate in this round but surely not a well set round. You expect Div2C and Div2D to have a certain difference in difficulty. The D problem surely didn't deserve to be a Div2D.

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

My Solution for problem C

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

Like these hints.Thanks.

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

easy and cool up to problem D. However, can't solve problem E. I hope I will see a color change.

»
12 months ago, # |
  Vote: I like it -13 Vote: I do not like it

anyone provide me problem B c++ code

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

another opportunity to feel ashamed....!!![ ]

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

In C problem , wrote the code of LCM wrong. Didnt check as i was taking GCD and LCM for granted. Can't handle more negative. Wanna die :(

Negative delta loading ...

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

Thanks for the problems! Pretty interesting and balanced set.

By the way, it seems we can't view the reference solutions.

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    lol, indeed, thanks for pointing it out. fun fact is that I copied template from editorial of previous round, and it is impossible to see reference solution in that editorial too, and nobody said that before. that is pretty much proves, that this references are useless, but I'll update them soon.

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

How would you do D, if the sum wasn't 0?

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

    Basically the same idea of considering prefix sums works except you have to be a bit more careful. If all the numbers are nonnegative or nonpositive it's clearly impossible. Now, without loss of generality assume the total sum is nonnegative. Let mx be the max element and mn be the minimum element. If the total sum is >= mx — mn, then of course the task is impossible no matter how you reorder the array, otherwise it's possible.

    First, place all the 0s in the array at the front. Then, it is possible to add elements so that the prefix sums are always in [0, mx — mn). Specifically, if the current sum is in [0, -mn), you add a positive element, otherwise if it is in [-mn, mx — mn), you add a negative element.

    This strategy ensure the prefix sum will always be in [0, mx — mn) until we run out of positive elements or negative elements. Then, since the total sum is in [0, mx — mn), adding the remaining positive or negative elements will still keep the prefix sum within [0, mx — mn).

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

<0000000000000000000>

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

how to solve the problem C if the types can be shuffled?

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

Appreciate that the solution has hints. Helps with upsolving problems beyond our range!

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

About the D Problem.

max1≤l≤r≤n|al+al+1+…+ar|

Is there a way to minimize this formula?

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

Would there be any efficient algorithm for Problem C when also allow reordering of the packs? Like for 20 3 6 2 14 5 20 7 21 2 we would still need 2 tags but we cannot use the prefix argument.

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

For B, you can choose the elements that appear the least later on in the future and it also works.

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

The solution link in the problem F is not working. Hope it will be fixed soon.

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

I think the testcases of problem B is weak ? My nearly brute force solution 199278375 passed (1387ms) ,and you can easily find a testcase to hack my code.

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

    Which part is brute force? Learn meaning of it first xD. It is greedy and since everyone can take at most one place, your solution is correct. Getting 1387 ms. because for every test case (5e4), you're clearing your arrays with size 5e5.

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

      Thanks. I should learn more.

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

gcd(a1⋅b1,…,an⋅bn) is divided by lcm(b1,…,bn) can someone prove this?

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

    Let $$$x$$$ be $$$lcm(b1,…,bn)$$$. Now let's try to price each type of candy with $$$x$$$. For each $$$i$$$, if cost of one pack is $$$x$$$ and one candy costs $$$b_i$$$, one pack will contain $$$x/b_i$$$ candies. So $$$a_i$$$ must be divisible by $$$x/b_i$$$. If we reorder that, $$$a_i⋅b_i$$$ must be divisible by $$$x$$$. Since $$$gcd(a1⋅b1,…,an⋅bn)$$$ is divisible by $$$x$$$, Each $$$a_i⋅b_i$$$ contains $$$x$$$ as a divisor.

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

why is my submission on problem c showing tle in test case 4. its a O(n) solution https://codeforces.com/contest/1798/submission/199363574

edit: i found my mistake in worst case it was going upto n^2 . thank you

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

Really great round

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

Great round and a great editorial indeed. If anyone wants a video editorial for these problems (for Problem A, Problem B, Problem C, Problem D). You can watch this here — video editorial

»
12 months ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#include <cmath>
#include<algorithm>
#include <stdint.h>


int arr[1010][1010];
int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    long long int a[n+1],b[n+1];
	    for(int i=1;i<=n;i++){
	        cin>>a[i]>>b[i];
	    }
	    int count=1;long long int prev=a[1]*b[1]; long long int prev_fac=a[1];
	    for(int i=2;i<=n;i++){
	        long long int p1=(a[i]*b[i])/(__gcd(a[i]*b[i],prev));
	        long long int p2=(prev)/(__gcd(a[i]*b[i],prev));
	        if(a[i]%p1==0 && prev_fac%p2==0 ){
	            prev=__gcd(prev,a[i]*b[i]);
	            prev_fac=__gcd(prev_fac,a[i]);
	        }
	       else{
	           count+=1;
	           prev=a[i]*b[i];
	           prev_fac=a[i];
	       }
	        
	        
	    }
	    cout<<count<<endl;
}
}

Can anyone point out the mistake in logic for C?

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

the solution for F can't be viewed.
Also if the complexity for single si is n^3(8000000) and the restriction is 1s, how can this avoid getting TLE?

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    I pasted my code in editorial. For a more understandable and better written code, I recommend to look into jiangly's submissions (Top1 of this round).

    On practise, this is very very fast $$$O(n^3)$$$ (it can be even improved to $$$O(n^3/w)$$$, where $$$w = 64$$$, with bitset), a lot of solutions fits into 50ms, and also there is Python solution that fits under 200ms.

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

    $$$200^3$$$ is just $$$8*10^6$$$ which is super fast for 1 second on Codeforces' servers.

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

      I didn't notice that the sum of $$$s_i$$$ is no greater than 200. I thought for each $$$s_i$$$ there is a O($$$n^3$$$) dp and the total complexity will reach O($$$n^4$$$)...
      $$$8*10^6$$$ can be done in 1s is pretty fast though

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

E is a beautiful problem

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

In Problem C I don't understand why using GCD and LCM. can anyone explain it in detail? I really appreciate any help you can provide.

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    let the cost of each pack of candies be $$$C$$$. So, it must satisfy that $$$C = B_i \times D_i$$$ for each $$$ 1 \leq i \leq n$$$.

    Thus, All $$$B_i$$$ must divide $$$C$$$ which means $$$lcm(B_1, B_2,..., B_n)$$$ must divide $$$C$$$.

    Now, $$$D_i$$$ is a divisor of $$$A_i$$$. let, $$$K_i = \frac{A_i}{D_i}$$$.

    $$$C = B_i \times \frac{A_i}{K_i}$$$ for each $$$ 1 \leq i \leq n$$$.

    $$$K_i = \frac{B_i \times A_i}{C}$$$ for each $$$ 1 \leq i \leq n$$$.

    $$$K_i$$$ must be an integer which means $$$C$$$ must divide $$$B_i \times A_i$$$.

    Thus, $$$C$$$ must divide $$$gcd(B_1 \times A_1, B_2 \times A_2,..., B_n \times A_n)$$$.

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

My contest went bad. But the overall quality of the problems are really good. I really appreciate the tutorial format too :)

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

For Problem F, the $$$n^3$$$ DP can be instead be done in $$$n\log n$$$ after a recent preprint. See submission 199466476 (assuming I implemented it correctly).

Obviously, this is completely unnecessary.

»
12 months ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

Ok, its 2 days after round, I decided to write a little postscriptum, which can answer some questions and show some insights of problemsetting/testing.

Firstly: thanks everyone who wrote comment with positive feedback about the problems, it's a big pleasure to see it, really. Second: apologize to everyone who got FST and negative delta because of it, pretests quality on problems B, C, D was poor, I'll be more careful with this next time.

Why D is easier than C, is it intended?
Story of problem A
Story of problem B
Story of problem C
Story of problem D
Story of problem E
Story of problem F

Forgive my non-prefect English, but I believe text is still understandable despite my mistakes. Thanks everyone who read that!

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

    Is there any basic proof for why greedy works in C? Still can really believe it or prove it myself

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 4   Vote: I like it +3 Vote: I do not like it

      Consider any possible answer and any possible price tag in it. If this price tag can be expanded to the right by 1, lets expand it. Since "If one price tag is enough for a set of candies, then if you remove any type of candy from this set, one price tag will still be enough" this action can not increase number of price tags. So starting from any possible answer we can expand any price tag to the right while we can, and number of price tag will not increase. After we do all possible expands we will achieve greedy construction (in greedy construction no price tag can be expanded to the right. and its unique construction, because there is only way to choose prefix that cannot be expanded to the right, and so on).

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

        Ok, it makes sense, idk why didn't I see it during contest.

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

    Thanks for the editorial, I have a simple doubt, Can you tell me in problem C we are taking lcm(b1,b2...bn) and not lcm(b1*d1,b2*d2...bn*dn). Is that because we are trying to remove di from the picture?

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

Cost of each bag from i to j will be gcd(ai*bi, ai + 1 * bi+ 1,...., aj * bj) (provided the condition stated in tutorial for i to j is satisfied) Or I am thinking wrong? Please someone explain.

Thanks, in advance.

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

    Cost can be any integer $$$x$$$ such that $$$gcd(a_i \cdot b_i, \ldots, a_j \cdot b_j)$$$ divides $$$x$$$, and $$$x$$$ divides $$$lcm(b_i, \ldots, b_j)$$$. So yeah, this gcd is one of the options of cost.

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

      Can you please explain why in your initial question "Is one price tag enough", just checking LCM(b1,b2,b3,...bn) as the cost of each bag was working?

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

For problem E, why is it the case that you only need to check if the dynamics value at i+1 is greater than or equal to a_i? Why don't they need to be exactly equal? In other words, how is it possible to create any number of tests up until the maximum number of tests that can be achieved by changing one element?

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

    Yes, this is fair remark. We can see that if 1 change was made to make $$$x$$$ tests, we can redo it to make exactly $$$x - 1$$$ tests. If first element was changed ($$$i+1$$$) it is pretty clear, we just extend $$$go_{i+1}$$$ to cover one more test. And if not first element was changed, you can change previous element (see picture). So if you can achieve $$$x$$$ tests you can achieve $$$x-1$$$ and so on, recursively, you can achieve any number from $$$1$$$ to $$$x$$$. And since $$$a_i \geq 1$$$ in the problem, its enough.

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

      Oh ok I think I understand now. Thank you for the clarification.

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

I didn't understand that C should be greedy. Anyone to explain?

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

@sevlll777
In C The word 'cost' is the sum of all costs or the cost of an individual packet.

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

thank you for writing the editorial with hints......

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1798/submission/245358316 I mistakenly solved the harder version of $$$D$$$ where sum of the elements of the array is not necessarily 0