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

snowysecret's blog

By snowysecret, 2 years ago, In English

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 1, Java, SecondThread)
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)
  • Vote: I like it
  • +425
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

ooh fast editorial :)

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

omg fast editorial

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    As lck, I am offended by your template :(

    Bad Kevin, I will throw you into River Cam when u arrive at Cambridge

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Today B screwed me.

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

    It was easy but very observational, if you can observe quick it's pretty easy otherwise it screws.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There must exist a solution for c=1 under the given constraints.

    I still don't exactly see why that is the case....

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

      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

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How to prove two odd numbers are mutually prime with a difference of 4 between them ?

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

          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.

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

          gcd(x+4, x) = gcd(x+4-x, x) = gcd(4, x) but x is odd => gcd(4, x) = 1

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice, thanks for the explanation!

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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$$$.

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

        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

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Great contest! I especially enjoyed solving problem D, thanks :)

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

    In D1, the difference between "<=,>=" and "<,>" changes everything...

»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Great contest! Great problems! Great editorial! Sad orange can’t play._.

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Lightening fast editorial :)

»
2 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Time complexity of editorial: O(1)

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

In the solution of problem C, the observation will be $$$x$$$ $$$mod$$$ $$$y$$$ $$$< \lceil \frac{x}{2} \rceil$$$ if $$$x$$$ $$$>=$$$ $$$y$$$

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Problems were good and so the quality of the editorial. All editorials should have hint spoilers.

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

    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)

»
2 years ago, # |
  Vote: I like it +111 Vote: I do not like it

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

»
2 years ago, # |
Rev. 3   Vote: I like it +59 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

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

    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 :)

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

    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.

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

    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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I proved it but I think it's hackable. Solution Link

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

    You can check it here

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

    Ummm Yes, I can prove my solution

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<x and those were all from 1 to (x-1)/2 so i kind of proved it

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

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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you so much!!!

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

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

    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.

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

    (nevermind, I was wrong here.)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problems great editorial with hints. overall great contest!!! Well done snowysecret.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem D in n+1 queries: 139550123

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to think the solution of problem B during the contest....

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

    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 .

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great problems, fast editorial with hints, I hope more of these contests will be held :)

Thanks snowysecret

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Superfast editorial!

What's more, with hints!

I enjoy the contest very much, the problems are fabulous, thank you!

»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

For anyone looking for video editorial you can check mine out

It's only up to D1 tho

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problems were nice, although I could try only up to D1.

Hoping to see you in another round :)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

borked checker rejudge time

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are only printing the elements of ans. You also need to print the size of ans before you print it's elements.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can read the editorial. It tells you how to find one crewmate and one imposter in exactly n queries.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

SIUUU!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B , why Brute force solution is working

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

    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.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice trick to solve D2

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

can anyone help me with this code :

139558441

a lot of thanks to anyone who can help me

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this test case:

    1
    2
    8 4 
    

    Expected output is 2, while your code produces -1.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      my code produces 2 not -1

      pic
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

          I understand now what's wrong with my code

          Spoiler

          Thanks a lot for the help

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I like the A question which made me an orgasm

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain this? in problem B solution 3 if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's just $$$a = 2, b = n-3, c = 1$$$. $$$n$$$ is even, so $$$n-3$$$ is odd, so it's coprime with $$$2$$$.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If you are interested in video solutions, here are the solutions for the first 4 problems.

»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Whyyyyy.... your mistake on E checker cost me 140 rating :(

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

    -1000 social rating bad very bad :((((

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

.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 years ago, # |
Rev. 6   Vote: I like it +14 Vote: I do not like it

I tried to hack my solution but I got "Unexpected verdict". Is there a problem with the solution to that problem?

Screen-Shot-2021-12-16-at-14-38-46

The test is

2

7 9

The 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice Contest snowysecret

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast editorial! Thanks!

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem E is really nice, good job!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anyone can solve D2 in n queries? I can just solve it in (n+1) queries!

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

I used Trie to solve E. Submission link

(I know it's overkill but the logic is somewhat different from the one in editorial)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey! Can you please explain what is the idea behind your solution?

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

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?= ^ =

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not needed, I coded without that query.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you help me see why my code got WA?139605367

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

        Your code seems to count imposters twice.

        Like this

        15

        0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

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

          I understand now what's wrong with my code

          Thanks a lot for the help!

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

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

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

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?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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. ~~~~~

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

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I wonder what "The jury is adaptive" means. Why there are still feedbacks of "wrong set of impostors"?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is pretty amazing. Loved to upsolve it.

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone explain me the meaning of "FST","AK"?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • failed on system test

    • solve all the problems in a contest

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

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

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

[My Submission](https://codeforces.com/contest/1617/submission/139840155

Can someone tell me why my code to Problem D1 is getting Idleness limit exceeded even though I flushed wherever required. Thanks in advance.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are flushing after cin , flush after cout. Tip : Use endl.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any number can reach 0, and 0 can reach any number.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is not the intended solution for 1617B - GCD Problem...

Link : 141021665

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

can someone tell me why i am getting WA on testcase 2 in this solution : https://codeforces.com/contest/1617/submission/141883310

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    $$$7 \% 3$$$ is $$$1$$$ not $$$4$$$, since the remainder when $$$7$$$ is divided by $$$3$$$ is $$$1$$$.

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

Really, Great Editorial :)

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

There exists a completely different and overcomplicated reasoning for the solution of problem E:

Notations:

  • $$$lsb(x)$$$: least significant set bit in binary representation of $$$x$$$.
  • $$$msb(x)$$$: most significant set bit in binary representation of $$$x$$$.

Firstly, let's visualize the effects of an operation $$$x = 2^k - x$$$ on the binary representation of integer $$$x$$$.

  • In the trivial case, if we choose $$$k$$$ such that $$$2^k = x$$$ then $$$x$$$ just turns $$$0$$$.
  • When we choose some $$$k$$$ such that $$$2^k > x$$$, observe that the operation is essentially equivalent to flipping the bits in the range $$$[k + 1, lsb(x))$$$ of the binary representation of $$$x$$$.

Observations
Optimal strategy for making two arbitrary integers equal
Finding the two integers which require the maximum number of moves to equalize

Implementation: link

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

Problem C can also be solved in O(n) approach which is bit easier to understand than one provided in the editorial.What we need to do is maintain a cnt array.We will traverse the array and for each element we will find the maximum remainder that number can leave this is O(1) operation.The maximum remainder will either obtained on v[i]/2 or v[i]/2 +1.If the remainder is greater than n do cnt[n]++ else do cnt[rem]++.If a number is already within the range 1 to n then we will skip its first occurence and for the remaining occurences we will proceed as stated above.Now we will traverse the cnt array from n to 1 and we will initialize a var curr_cnt=0 and we will add cnt[i] value to curr_cnt and if curr_cnt <=0 at any instant we will return -1 else we will decrease curr_cnt by 1 for that index.To output the min number of operations required we will just count the numbers greater than n or the number which are between 1 to n and have multiple occurences so we wont count its first occurence and will add other occurences.This approach works in O(n)

Solution Link : https://codeforces.com/contest/1617/submission/244048117