dbsic211's blog

By dbsic211, 5 months 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

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

ooh fast editorial :)

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

wow so superfast editorial!

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

thanks

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

omg fast editorial

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

Problems were really good.

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

Today B screwed me.

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

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

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

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

        god

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

        I thought this exactly same as well, so not a strange way i suppose

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

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

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

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

        Nice, thanks for the explanation!

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

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

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

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

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

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

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

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

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

Lightening fast editorial :)

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

Time complexity of editorial: O(1)

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

These editorials are faster than chinese's problem-solving.

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

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

  • »
    »
    5 months 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)

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

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

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

  • »
    »
    5 months 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 :)

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

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

      I did the same, although I think you meant (n — 1 — prime) mod prime != 0 instead of (n — 1) mod prime != 0

      So the solution would be:

      • a = p
      • b = n — 1 — p
      • c = 1

      where p is the first prime such that (n — 1 — p) mod p != 0

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

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

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

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

    You can check it here

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

    Ummm Yes, I can prove my solution

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

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

    Isn't this called Goldbach's conjecture that you can represent any number as sum of 2 primes so you can make n-1 with sum of 2 primes. As far as i know no one proved it until now

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

    This is how I did (proof):

    I always use a number line for such problems and this is my go-to. In this problem, I always considered c to be 1, and the rest of my solution went up from there.

    If we give a look at the number line, then the gcd of any two numbers will never exceed their difference.

    Case 1: n is even and say n=82; --> Taking c=1 leaves us with 81 --> 40.5 is what we get if we divide it by 2 (You know why we divide) --> Distribute the 0.5 (40.5+0.5 + 40.5-0.5 gives us 41 + 40) --> In the number line adjacent numbers will always have a gcd of 1. So gcd is 1.

    Case 2a: n is odd and say n=81; --> Taking c=1 leaves us with 80 --> 40 is what we get if we divide it by 2 (You know why we divide) --> Move the two numbers to the nearest odd numbers (40-1 + 40+1 gives us 39 and 41) --> In the number line their difference is 2 and no way you can divide those numbers with an odd number which is greater than 1. So gcd is 1. (max diff is 2)

    Case 2b: n is odd and say n=83; --> Taking c=1 leaves us with 82 --> 41 is what we get if we divide it by 2 (You know why we divide) --> Move the two numbers to the nearest odd numbers (41-2 + 41+2 gives us 39 + 43) --> In the number line their difference is 4 and no way you can divide those numbers together with an odd number other than 1. So gcd is 1(max diff is 4 and you can't jump from 39 to 43 using 3 steps)

    So, it's proved that in all the 3 the cases their gcd will always be 1 for the given constraint while maintaining their summation.

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

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

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

Thank you so much!!!

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

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

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

    (nevermind, I was wrong here.)

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

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

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

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

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

Thank you for the fast editorial :)

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

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

Please explain me solution of problem C in easy language !

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

    First see how many numbers from 1-n are not visited and how many numbers from array are left(numbers which are >n or are more than required for eg 3 2's so 2 are left unused).1st observation if a number is odd it can be change from 1 to number/2.Eg 7 --> 1 to 3,and if it is odd than it can be changed to number/2 — 1.Eg 10 --> 1 — 4.So now just iterate over the numbers left and the numbers not visited and if a left number can't be changed ans is false. You can refer to my solution

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

Problem D in n+1 queries: 139550123

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

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

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

    While, There are no generalized ways to think about any problem.

    How i though of problems like this contest's B is by observing the pattern by first writing a brute force solution (which in this case is 3 nested loop for a, b, and c), and then run it for small cases like n <= 50, and made the formula out of the observation. which turned out to be the 3rd solution of editorial.

    Hope this helps :)

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

»
5 months 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 dbsic211

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

Great Questions! The contest was not good for me , wasn't able to solve any of them! Just another bad day.

Well done dbsic211 !

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

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

orz

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

»
5 months 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 :)

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

borked checker rejudge time

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

In B if the number is odd then there exists a solution for c = 1 by Goldbach's conjecture!(A famous conjecture). Although it isn't proven yet however has been verified for very large numbers well outside given limit. A nice trivia :)

However as Goldbach's conjecture is about primes, I wasn't able to construct solution where a and b are prime, within given time limits. So had to settle for them just being coprime.

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

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

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

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

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

SIUUU!

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

In problem B , why Brute force solution is working

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

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

      But that would be true if we were iterating "a" and checking gcd(a,n-1) but we are checking gcd(a ,n-1-a), here both the numbers are changing how can we comment if the gcd would be 1.

      Edit

      Sorry for my mistake. gcd(a,n-1-a) is equal as gcd(a,n-1)

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

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

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

Very nice trick to solve D2

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

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

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

      my code produces 2 not -1

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

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

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

      Thank you very much, I realized I just needed to change if(x>n ||(x == n && a[n] == true) ) to if(x>n ||(a[x] == true) ).

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

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

I like the A question which made me an orgasm

»
5 months 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";

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

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

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

my code for problem C is giving right output in vs code but it is giving wrong output in codeforces for test 2 .Can someone say why it is happening so and how can be it corrected ? My submission link : https://codeforces.com/contest/1617/submission/139565621

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

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

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

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

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

.

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

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

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

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

Nice Contest dbsic211

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

Fast editorial! Thanks!

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

Can someone please tell the prerequisites of problem E? I am in a dilemma whether to upsolve it or not. Also I think editorial should contain prerequisite section as we see in codechef :)

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

Problem E is really nice, good job!

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

dbsic211 , I think the condition in key observation in Problem C holds if y > (x/2) along with (x >= y) i.e. x mod y < x/2 if (x >= y) and (y > x/2)

I think you have just missed (y > x/2) in writing in the key observation. Please review and update if necessary.

Given: x >= y > (x/2)

Claim: x mod y < x/2

Proof:

since x is greater than y, => WLOG, x = my + n, where 0 <= n < y. We have to prove that n < x/2.
Assume the contradiction to be true. 
i.e. n >= x/2.  
=> x = my + n >= my + x/2. 
=> x - x/2 >= my + x/2 - x/2. 
=> x/2 >= my. 
But given is y > x/2. 
=> x/2 > mx/2. 
=> m < 1. 
=> m = 0. 
so x = my + n becomes x = n. 
But we know x mod y < y => n < y => x < y which contradicts the given statement. 
»
5 months 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!

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

I think c was a lot easier than b maybe I am weak in number theory

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

Couldn't solve even A, and submitted B with TLE, lol I'm too noob

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

So like the adaptive stuff about jury is just bs? that was a very weird addition for me but then the solution was kinda straight forward for D1 so Im thinking thats why they added it.

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

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

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

»
5 months 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?= ^ =

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

    Not needed, I coded without that query.

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

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

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

        • »
          »
          »
          »
          »
          5 months 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!

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

I don't really know how my n^3 solution for Problem A didn't get FST. https://codeforces.com/contest/1617/submission/139485745

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

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

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

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

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

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.

»
5 months 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"?

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

Problem D is pretty amazing. Loved to upsolve it.

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

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

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

    • solve all the problems in a contest

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

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

Can someone find what's wrong? I am getting wrong number of impostors verdict in Test 1 itself in D2 while upsolving. I think it maybe something related to interactive problems. Link to submission

»
5 months 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 please provide a proof of this line from the editorial of problem D1?

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

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

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

»
5 months 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$$$?

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

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

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

Can someone help me with this submission of problem D2? On my system it is working fine for test 1, but it is failing here.. Maybe some thing related to interative problems... Thanks in advance!

https://codeforces.com/contest/1617/submission/140571766

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

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

In problem 1617B :GCD problem

a/c to question we have to find a , b ,c such that a + b + c=n and gcd(a ,b)=c. so for example: n=18 a=1,b=16,c=1 since gcd(1 ,16)=1 and 1+16+1=18. Is it considered as a correct soln??? if yes then can we apply this for all value of n.

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

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

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

Can anyone tell me why my solution is not working for Problem C

https://codeforces.com/contest/1617/submission/146021818

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

  • »
    »
    4 weeks 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$$$.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Really, Great Editorial :)