### dbsic211's blog

By dbsic211, 14 months ago,

Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.

UPD: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.

UPD2: Rejudge done, the round remains rated.

Statistics

1617A - Forbidden Subsequence

Hint
Solution
Implementation (C++, I_Love_YrNameCouldBeHere)
Fun fact

1617B - GCD Problem

Hint
Solution
Implementation (Solution 2, C++, dbsic211)
Implementation (Solution 3, C++, anthony123)

1617C - Paprika and Permutation

Hint 1
Hint 2
Solution
Implementation (C++, physics0523)

1617D1 - Too Many Impostors (easy version)

Hint 1
Hint 2
Hint 3
Solution
Implementation (C++, dbsic211)

1617D2 - Too Many Impostors (hard version)

Thanks must be given to arvindf232 and generic_placeholder_name for the solution.

Hint 1
Hint 2
Solution (Step 1)
Hint 3
Hint 4
Solution (Step 2)
Implementation (C++, dbsic211)

1617E - Christmas Chocolates

Hint 1
Hint 2
Hint 3
Solution (Step 1)
Hint 4
Solution (Step 2)
Implementation (C++, physics0523)

• +425

| Write comment?
 » 14 months ago, # |   +27 ooh fast editorial :)
•  » » 14 months ago, # ^ |   0 dbsic211 orz
•  » » » 14 months ago, # ^ |   0 Wow it's amazingly fast editorial :D.
•  » » 14 months ago, # ^ |   -21 anthony123 orz
 » 14 months ago, # |   +22 omg fast editorial
•  » » 14 months ago, # ^ | ← Rev. 2 →   +26 As lck, I am offended by your template :(Bad Kevin, I will throw you into River Cam when u arrive at Cambridge
 » 14 months ago, # |   +9 Today B screwed me.
•  » » 14 months ago, # ^ |   +7 It was easy but very observational, if you can observe quick it's pretty easy otherwise it screws.
•  » » 14 months ago, # ^ |   0 There must exist a solution for c=1 under the given constraints.I still don't exactly see why that is the case....
•  » » » 14 months ago, # ^ |   +14 Assume $c = 1$, you are left with $n - 1$ which must be divided in two groups, $a$ and $b$.Dividing by $2$ will either equally distribute the amount or it won't. In the second case, one value will always be $+1$ than the other and $gcd$ of two consecutive numbers is $1$. In the first case, both numbers will either be odd or even. If both numbers are even then simply subtract $1$ from one value and add it to the second value, by doing this both numbers will be odd now with a difference of $2$, hence $gcd = 1$. If both numbers are odd, subtract $2$ from one value and add it to the other value. By doing this you will have two odd numbers with a difference of $4$, hence $gcd = 1$Maybe this is a complicated way to think about it but that's how I did it
•  » » » » 14 months ago, # ^ |   0 How to prove two odd numbers are mutually prime with a difference of 4 between them ?
•  » » » » » 14 months ago, # ^ |   +3 if the difference between the two numbers is 4,their gcd cannot be greater than 4.now since the numbers are odd 2 and 4 won't divide them.so now we are left with 1 and 3.let's say the gcd is 3 so it divides the smaller number x the next numbers it will divide will be x+3,x+6 but our second number is x+4. so 1 is their gcd.
•  » » » » » 14 months ago, # ^ |   +9 gcd(x+4, x) = gcd(x+4-x, x) = gcd(4, x) but x is odd => gcd(4, x) = 1
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 thanks!
•  » » » » 14 months ago, # ^ |   0 Nice, thanks for the explanation!
•  » » » » 14 months ago, # ^ |   0 When it comes to proving that there exists a pair $(a, b)$ for $c=1$ which solves the problem one can use Goldbach's conjecture (which was shown to work for numbers $\leq 10^{18}$). If $n-1$ is odd then it's easy to see that we can choose $a=x$ and $b=x+1$ where $x=\frac{n}{2}-1$, but when $n-1$ is even GC gives us that there exist 2 primes $p, q$ such that $p+q=n-1$.
•  » » » » 12 months ago, # ^ |   +1 Thanks your explanation was lucid and simple .I was able to frame the solution and am sure it will be helpful in upcoming problems. May God bless you with more ratings
 » 14 months ago, # |   +5 Great contest! I especially enjoyed solving problem D, thanks :)
•  » » 14 months ago, # ^ |   +11 In D1, the difference between "<=,>=" and "<,>" changes everything...
 » 14 months ago, # |   +23 Great contest! Great problems! Great editorial! Sad orange can’t play._.
 » 14 months ago, # |   +6 Lightening fast editorial :)
 » 14 months ago, # |   +53 Time complexity of editorial: O(1)
 » 14 months ago, # | ← Rev. 2 →   0 In the solution of problem C, the observation will be $x$ $mod$ $y$ $< \lceil \frac{x}{2} \rceil$ if $x$ $>=$ $y$
 » 14 months ago, # |   +12 Problems were good and so the quality of the editorial. All editorials should have hint spoilers.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 I like how the author split the editorial into hints, solutions, and code snippets, and had them spoilered separately, which would be helpful for beginners who are learning cp;) (But it’s also extra effort, so I wouldn’t go as far as to ask for having this in particular, rather, I’ll just treat it as a bonus)
 » 14 months ago, # |   +111 As a tester, I have some fun facts about problem D:Originally, D had only one version, which is the current D1. Then I tested D and came up with a $\frac{4n}{3} + O(1)$ query solution. (Actually, originally, $n \bmod 3 = 0$ wasn't a thing, and the lower bound was $4$, so getting that to AC was a lot of pain :v) That solution became D2 — except that later, arvindf232 came up with the $n + 2$ query solution. Then we had a problem, which was that we couldn't decide which of $2n$, $\frac{4n}{3}$, or $n$ should be the official D1/D2. In the end we decided that $2n$ for D1 and $n + O(1)$ for D2 would be best for balance.We (or at least I) thought that D2 was more difficult than it ended up being. We had the idea of changing the distribution to 1750-1250-2500, but it never came to pass. In my opinion, the original distribution turned out to be better. :v
 » 14 months ago, # | ← Rev. 3 →   +59 I'm curious, how many participants actually proved their solution of B?EDIT: I'm not looking for proofs of this solution or that solution. I'm more interested in the ratio of "guessed/hoped" vs "solved". Actually in some sense it's more interesting to hear from people who didn't prove their solution.
•  » » 14 months ago, # ^ |   0 Ya, i have prrof for my solution. By choosing c = 1, the problem can be proved by checking even or odd of number and its half. submission: https://codeforces.com/contest/1617/submission/139495888
•  » » 14 months ago, # ^ |   +49 The 3-case people probably proved their solution, but probably most other solutions didn't :v My "proof" was a vague understanding of probability and a heavy dose of inshallah :)
•  » » 14 months ago, # ^ |   +3 Me. I used the approach of finding the first prime that does not divide n — 1, which must exist within the first 10 primes since n is at most 1e9.
•  » » 14 months ago, # ^ |   +3 if n-1 is odd then answer is some consecutive number but if it is even, by goldbach's conjecture it follows that it can be written as a sum of two primes.
•  » » 14 months ago, # ^ |   0 I proved it but I think it's hackable. Solution Link
•  » » 14 months ago, # ^ |   +11 You can check it here
•  » » 14 months ago, # ^ |   +3 Ummm Yes, I can prove my solution
•  » » 14 months ago, # ^ |   0 It took me 44 mins on B just to prove that a brute force soln works and in the end i coded the entire proof lol .When i was a newbie i used to solve these type of questions pretty fast but as my experience increased i started proving things haha.Anyways i liked the contest very much
•  » » 14 months ago, # ^ |   0 i assumed the gcd is 1 because otherwise the complexity would be exponential then i made a program that told me how many numbers can be obtained from x%y with 1<=y
 » 14 months ago, # | ← Rev. 2 →   0 139546379 I don't know why I get TLE on D2, I think my time complexity is $O(n)$.Edit: I know where was wrong. I didn't handle the case when query return -1
 » 14 months ago, # |   +8 Thank you so much!!!
 » 14 months ago, # |   +19 Can we do D2 in $\leq n$ queries?It can be done is $n + 1$ by reducing $1$ query from the editorial's solution using the fact that the two people between the impostor and crewmate we detected, are of opposite type, so we can just ask for one of them.
•  » » 14 months ago, # ^ |   +33 I don’t think $< n$ is possible, but exactly $n$ queries is possible (tho idk how)There are around $2^n$ possible answers, and each queries gives a binary answer. So the theoretical lower bound is $\log_2(2^n)=n$ queries.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 (nevermind, I was wrong here.)
•  » » » 14 months ago, # ^ |   0 I don't think this works in all cases. If the different 3-tuples occur somewhere in between, we will need $n+1$ queries still.
•  » » » » 14 months ago, # ^ |   0 Yes, with this way it is mathematically impossible to get exactly $n$ queries. If there is a $n$ query solution it won't be this one.
 » 14 months ago, # |   +3 Nice problems great editorial with hints. overall great contest!!! Well done dbsic211.
 » 14 months ago, # |   0 Was totally confused at C. Luckily understood the meaning of k range to solve D1 and that saved my rating for this contest or else whoooooosh it would have gone
 » 14 months ago, # |   +21 Problem D in n+1 queries: 139550123
•  » » 14 months ago, # ^ |   0 Can you explain your solution :)
 » 14 months ago, # |   0 How to think the solution of problem B during the contest....
•  » » 14 months ago, # ^ |   +3 Actually, first observation is gcd(a,b)=c so a=cx and b=cy where x and y are mutually prime. So the given equation becomes c*(x+y+1)=n . so c is a factor of n. Now you think that if n is a prime number, then it's only factors are 1 and the number itself. if c=the prime number itself, then x+y+1=1 ===> x+y=0 which is not possible according to the given problem. So c=1 for prime numbers. On the other hand the equation will be holding for composite numbers as well so, you can proceed with c=1. therefore the equation becomes x+y+1=n or x+y=n-1. Now, we have already said that x and y are mutually prime. So the immediate thing that should come to mind is that two consecutive numbers are equal . if n-1 is odd, then you should know that an odd number can be written always as a sum of two consecutive numbers (if x is odd, then x=x/2+x/2+1 ...x unrelated to the explanation above) . otherwise,n-1 is even, so a possibility is x=(n-1)/2 and y=(n-1)/2 . But x and y are coprime, so probably, we can go one step forward for y and one step backward for x .Then x=(n-1)/2 -1 and y=(n-1)/2+1 .Now if originally x and y were even numbers, then the new x and y must be odd numbers. These two odd numbers with a difference of one will always be coprime. Otherwise,if both new x and y are even, then decrease x one more time and increase y one more time .Again we end up with two odd numbers and these two with a difference of 4 will always be mutually prime .
 » 14 months ago, # |   +1 Great problems, fast editorial with hints, I hope more of these contests will be held :)Thanks dbsic211
 » 14 months ago, # |   +9 Superfast editorial! What's more, with hints!I enjoy the contest very much, the problems are fabulous, thank you!
 » 14 months ago, # |   -9 For anyone looking for video editorial you can check mine outIt's only up to D1 tho
 » 14 months ago, # |   +3 Problems were nice, although I could try only up to D1.Hoping to see you in another round :)
 » 14 months ago, # |   +8 borked checker rejudge time
 » 14 months ago, # |   -8 Can anyone tell me, for problem D1 why I am getting the wrong answer verdict on Test Case 1? Any help would be appreciable. Thank you :)Submission
•  » » 14 months ago, # ^ |   0 You are only printing the elements of ans. You also need to print the size of ans before you print it's elements.
•  » » » 14 months ago, # ^ |   0 Thanks, buddy! Now my code is asking too many queries so can you or anyone tell me any optimal way to solve this question.I spent too many queries just to find one crewmate and one imposter to get the answer so is there is any optimal way to find them?
•  » » » » 14 months ago, # ^ |   0 You can read the editorial. It tells you how to find one crewmate and one imposter in exactly n queries.
 » 14 months ago, # |   +1 SIUUU!
 » 14 months ago, # |   0 In problem B , why Brute force solution is working
•  » » 14 months ago, # ^ |   0 Because there are only limited divisors of $n - 1$, which means that eventually there are going to be two coprime numbers. There's some math that proves this, but ehh, nobody cares enough to prove it.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 because the gap of two prime number at most 300 in the range 10^12. so,when you picked up a big prime ,the other side is lower than prime.so there gcd is 1. for example, n=34,if we pick a prime 29,then the other side is (34-29)-1=4 so a=29,b=4 and gcd(29,4)=1.
 » 14 months ago, # |   +9 My more complicated, less elegant solution to D1: Make queries of the form (1, 2, i) for i in [3, 2n/3 + 1] If the results are not all the same, we immediately know 1 and 2 are different, and we easily have the answer ans[i] = query(1, 2, i). Otherwise, if all of the results are the same, then we know 1 and 2 are whatever the result is. Proof: assume that 1 and 2 are different but all the queries [3, 2n/3 + 1] returned the same result. Then there are a total of (2n/3+1 — 3 + 1) same results, plus 1 for either 1 or 2 matching, for a total of 2n/3 of the same, contradicting the constraint. WLOG, say 1 and 2 are imposters. Now, query all the disjoint triplets that haven't already been queried (i.e. all but (1, 2, 3)). We know one of the triplets must return 1 (same reasoning as in editorial solution), having >= 2 crewmates. Let the triplet be (a, b, c). Of the queries (1, a, b), (1, a, c), and (1, b, c), at least one of them will return majority crewmate, and the two people that aren't 1 are crewmates. This step takes at most 2 queries (since after 2 failures, there is only one option left). By now, we've identified 1 crewmate and 1 imposter, and can determine the remaining (n-4) people with the simple queries. So in the worse path, we use (2n/3-1) + (n/3-1) + 2 + (n-4) = 2n queries.
 » 14 months ago, # |   0 Very nice trick to solve D2
 » 14 months ago, # | ← Rev. 2 →   0 can anyone help me with this code : 139558441a lot of thanks to anyone who can help me
•  » » 14 months ago, # ^ |   0 Try this test case: 1 2 8 4 Expected output is 2, while your code produces -1.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +1 my code produces 2 not -1 pic ...
•  » » » » 14 months ago, # ^ |   0 It's because you're not handling multiple test cases correctly. Just wrap this testcase with another one, and you can spot the error.For example, on the input 2 6 4 1 7 8 8 3 2 8 4 your code produces -1 -1 while the intended output is -1 2.
•  » » » » » 14 months ago, # ^ |   +1 I understand now what's wrong with my code SpoilerThanks a lot for the help
 » 14 months ago, # |   0 can someone please tell why this is giving me RTE on the first test case? it is working fine on my compiler https://codeforces.com/contest/1617/submission/139558421
 » 14 months ago, # |   +3 I like the A question which made me an orgasm
 » 14 months ago, # |   0 can anyone please explain this? in problem B solution 3 if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";
•  » » 14 months ago, # ^ |   0 It's just $a = 2, b = n-3, c = 1$. $n$ is even, so $n-3$ is odd, so it's coprime with $2$.
 » 14 months ago, # |   +1 If you are interested in video solutions, here are the solutions for the first 4 problems.
 » 14 months ago, # |   +33 Whyyyyy.... your mistake on E checker cost me 140 rating :(
•  » » 14 months ago, # ^ |   +35 -1000 social rating bad very bad :((((
 » 14 months ago, # | ← Rev. 2 →   0 .
•  » » 14 months ago, # ^ |   0 5%4==1 5%3==2 9%6==3 14%10==4 5 is already left thus we can make a permutation in 4 moves. Hope this helps
 » 14 months ago, # | ← Rev. 6 →   +14 I tried to hack my solution but I got "Unexpected verdict". Is there a problem with the solution to that problem?The test is27 9The particular thing about that test is that the diameter of the tree shouldn’t consider the node 0, (just nodes 7 and 9 in this case) my solution didn’t consider that and that is the reason of the wrong answer. This happens when all the nodes in the input lie in the same path from the root to the farthest node. Please consider adding a similar test.
 » 14 months ago, # |   0 I've implemented the idea of D2 on D1(6 queries), but wasn't aware that same way I can solve D2. And i also missed the simple idea of D1!!
 » 14 months ago, # |   +3 Nice Contest dbsic211
 » 14 months ago, # |   0 Fast editorial! Thanks!
 » 14 months ago, # |   +6 Problem E is really nice, good job!
 » 14 months ago, # |   0 Is there anyone can solve D2 in n queries? I can just solve it in (n+1) queries!
 » 14 months ago, # | ← Rev. 2 →   +6 I used Trie to solve E. Submission link(I know it's overkill but the logic is somewhat different from the one in editorial)
•  » » 13 months ago, # ^ |   0 Hey! Can you please explain what is the idea behind your solution?
 » 14 months ago, # | ← Rev. 2 →   0 for Problem D1,why we need query $(n-1,n,1)$ and $(n,1,2)$ ?It seems that query $(1,2,3)$ to $(n-2,n-1,n)$ can find one pair of crewmate and impostor.can give me a counter-example？= ^ =
•  » » 14 months ago, # ^ |   0 Not needed, I coded without that query.
•  » » » 13 months ago, # ^ |   0 Can you help me see why my code got WA?139605367
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +3 Your code seems to count imposters twice.Like this150 1 0 1 0 1 0 1 0 1 0 1 0 1 0
•  » » » » » 13 months ago, # ^ |   +5 I understand now what's wrong with my codeThanks a lot for the help！
 » 14 months ago, # | ← Rev. 2 →   0 Could someone please tell me whats wrong with my d2 solution? I am getting the same output as testcase 1, but its showing "Incorrect set of impostors"?Here's my code
 » 14 months ago, # | ← Rev. 2 →   0 Since the number of impostors k and crewmates n-k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different.Can someone explain why?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 You know that n is divisible by 3. So you can split it into x intervals of 3 each, such that x*3=n. So assume x=n/3.Now, k>n/3 =>k>x and k<2*x. so k belongs to [x+1,2*x).Applying pigeon hole principle, you have x intervals and a minimum of x+1 impostors to fill, so at least one interval will have 2(or more) impostors.With this, it wont be difficult to see that ~~~~~ for any n and k, that satisfy the constraints, the number of impostors k and crewmates n-k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different. ~~~~~
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 According to the pigeon hole principle, As long as one adjacent 0-majority tuple and 1-majority tuple exists, there is exactly 4 cases of one kind of tuple.0-major -> {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0}; 1-major -> {1, 1, 1}, {1, 1, 0}, {1, 0, 1}, {0, 1, 1}.for the {0-major} + {1-major} and {1-major} + {0-major} cases, brutally select each tuple, pair them up, try all 2 * (4 * 4) = 32 cases, we can see there will always be at least one 4-consecutive indices {id, id + 1, id + 2, id + 3} from all 6 places for each case, for which query {id, id + 1, id + 2} and query{id + 1, id + 2, id + 3} differs.For example check 2 tuples {0 1 1} + {0 0 0}, start with the second index, {1 1 0 0} meets our need.The method may be kind of tedious, I wonder if other elegant proofs exist.
 » 14 months ago, # |   0 Need help in understanding WA for C. https://codeforces.com/contest/1617/submission/139618376 My submission, I have implemented a code similar to the one described in the editorial (I think). I get WA on a 2000 elements array so I'm not able to identify the test case which defeats my solution. Any help will be appreciated.
•  » » 14 months ago, # ^ |   0 Input1 2 1 1  Expected Output-1 Your Output0
 » 14 months ago, # |   0 In problem D, I wonder what "The jury is adaptive" means. Why there are still feedbacks of "wrong set of impostors"?
 » 14 months ago, # |   0 Problem D is pretty amazing. Loved to upsolve it.
 » 14 months ago, # |   +5 Can anyone explain me the meaning of "FST","AK"?
•  » » 14 months ago, # ^ |   +5 failed on system test solve all the problems in a contest
 » 14 months ago, # | ← Rev. 2 →   +4 I have a solution to problem E which does not involve graphs in any way. At the beginning, our array values fit in range $[0, 2^{30}]$. Let's now divide the array into two parts $L$ and $R$, where $L$ will contain all values $\le 2^{29}$ and $R$ will contain all larger values. Now suppose $(x, y)$ is the optimal pair we are searching for. Here comes a crucial observation. If both $(x, y)$ are in $R$ they are both larger than $2^{29}$ so we cannot use any $k \le 29$ operation on them. The only way to continue is to use $k = 30$ and make them both less than $2^{29}$. Also suppose $x \le 2^{29}$ and $y > 2^{29}$. In this case we have to transfer one value to the other side by using $k = 30$, but transferring $x$ is never optimal. Let's prove it. Case $x = 2^{29}$ is trivial. Otherwise $x < 2^{29}$ so $2^{30} - x > 2^{29}$ and since also $y > 2^{29}$ we arrive at the previous state when we are forced to decrease both of them using $k = 30$. This means that it is always better to do an operation on $y$, again reducing it to some value $< 2^{29}$ and continue from there.All the reasoning above means that all values $R$ have to be reduced in one operation to become less than $2^{29}$ and after that we can merge those values with $L$ and repeat our algorithm again with a threshold $2^{29}$.We can repeat this process until we arrive at a simple case when all values are in range $[0, 1]$. Here we can just consider a transition $0 \rightarrow 1$ and we are done.This solution can be implemented in various ways. One I can think of is to store $L$ and $R$ as sorted vectors and merge them using two pointers. But I personally think that maps are the most simple and elegant way. Maps introduce an additional $\log n$ factor, resulting in a $O(n \log n \log 10^9)$ solution overall which is still fast enough considering a very generous time limit.Here is my submission: https://codeforces.com/contest/1617/submission/139683868
 » 13 months ago, # | ← Rev. 2 →   0 [My Submission](https://codeforces.com/contest/1617/submission/139840155Can someone tell me why my code to Problem D1 is getting Idleness limit exceeded even though I flushed wherever required. Thanks in advance.
•  » » 13 months ago, # ^ |   0 You are flushing after cin , flush after cout. Tip : Use endl.
 » 13 months ago, # |   0 Sorry if it's obvious, but why is the graph formed in E connected? I see that there are no cycles but how do we know that we can get from any $x$ to any $y$?
•  » » 12 months ago, # ^ |   0 Any number can reach 0, and 0 can reach any number.
 » 13 months ago, # |   0 I think this is not the intended solution for 1617B - GCD Problem...Link : 141021665
 » 13 months ago, # |   0 Can anyone tell me what's wrong with my code? I've coded differently, but the approach is same as given for problem C. 142936588
•  » » 13 months ago, # ^ |   0 Solution with TC O(N):142954118
 » 12 months ago, # |   0 Can anyone tell me why my solution is not working for Problem Chttps://codeforces.com/contest/1617/submission/146021818
 » 11 months ago, # |   0 In Problem C, According to Editorial Solution I found -1 as output when I provide array = {1, 2, 7, 8} as Input. But here the output should be 2. Like for array[3] = 7 we can choose x = 3 and 7 % 3 i.e. 4 lies in [1, n], similarly for array[4] = 8 we can choose x = 5 and 8 % 5 i.e. 3 lies in [1, n]. hence we can obtain the permutation as {1, 2, 4, 3} which should be acceptable. May be I am wrong if anyone found the proper solution please reply ASAP.
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 $7 \% 3$ is $1$ not $4$, since the remainder when $7$ is divided by $3$ is $1$.
 » 9 months ago, # |   +3 Really, Great Editorial :)