shishin's blog

By shishin, history, 5 weeks ago, In English

All problems were prepared on Polygon by me, so if you faced any problems (we know about A) I am really sorry about it.

Tutorial is loading...

Idea: shishin

Jury solution: pastebin

Tutorial is loading...

Idea: Artyom123

Jury solution: pastebin

Tutorial is loading...

Idea: shishin

Jury solution: pastebin

Tutorial is loading...

Idea: Artyom123

Jury solution: pastebin

Tutorial is loading...

Idea: shishin

Jury solution: pastebin

Tutorial is loading...

Idea: isaf27 + Kotehok3

Jury solution: pastebin

 
 
 
 
  • Vote: I like it
  • +223
  • Vote: I do not like it

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

Good job!

»
5 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

Fast blazingly fast

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

Thanks for quick editorial.

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

    I see people down-voting, I just liked the editorial and i was thankful for the contest and the quick editorial, now ,whom did I hurt or what was wrong in this comment for these downvotes?

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Thanks for the speedy Tutorial man!

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

Thanks!

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

For D2 My solution got hacked for testcase 67 Can anybody help me? This is my submission link: https://codeforces.com/contest/1419/submission/93235884

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

    That was a system test, not a hack test

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

    Um, for your information, there is a button called "Click here for more information" at the bottom of the page of every submission. Click on it and you can see all tests and know what kind of test data you fail on.

    BTW it's really important to make good index calculation :) And not don't blame hacks, though this solution is hackable.

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

I'm still struggling with B...

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

    try making out patterns on paper and see how the pattern goes, they gave un hint in sample that answer was going to be in 1 to 30 only. so you could simply precompute these 30 values.

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

    You can solve it through recurrence. The first stair case (a single green square in the picture in the problem statement) with will have $$$1$$$ cell. Lets denote the number of cells in the first stair case with $$$a_1$$$ so $$$a_1 = 1$$$ cell. The next possible stair case (the second possible stair case) will have $$$a_2=6$$$ cells. It's made out of two green cells (two $$$a_1$$$s) and one yellow square which has $$$2^2$$$ cells (as in the picture in the problem statement) so $$$a_2=2*a_1+2^2$$$. The third possible stair case will have $$$a_3 = 2 * a_2 + 2^4$$$ cells. I hope that by this point you can see that $$$2^4$$$ corresponds to the red square from the picture in the problem statement? So now the general formula for the number of cells in a nice stair case is $$$a_i = 2 * a_{i-1} + 2^{2*(i-1)}$$$. Now all you need to do is count $$$a_i$$$ up to some value so that you will meet the problem constraints. Then count a prefix sum array of the $$$a_i$$$s and then you can greedily iterate over it up to a given $$$x$$$. Here's my code 93245756.

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

      Thanks, I get your explanation, not sure if its really a proof but close enough. I wasnt confident enough in the contest to procede with this idea

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

        Don't forget to use 1ll if you want to make some power of two ( use 1ll<<x instead of 1<<x), that cost me about 40 min to debug during the contest...

        GL

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

          Bro what does this 1LL does and what do you mean by 1ll<<x and 1<<x

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

            1LL means 1 but in type long long. Just the same as (long long)1

            1ll<<x means shift the bits right x times in binary. This is how I do for getting powers of two in C++. Bit operations are useful to me :v

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

              Author's solution is confusing me can you help me bro

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

              hi pls can you tell me why do we need to use 1LL and not just 1?

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

                So that there is no overflow of number in int

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

                  just out of curiosity i have written the code without using 1LL but it still giving the desired outputsolution without using 1LL pls can you tell why this is showing accepted then

                  thanks

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

                  Because you have i already ll long long int type One side of expression is long long int type it is enough

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

                  thank you for the help i got it

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

                  You are welcome

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

      Why are we doing prefix sums?

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

        Actually, I only used prefix sums since I implemented my solution in Python and I was not sure if it will meet the time limit if I calculate the sum of $$$a_i$$$ on the fly (Python is slow you know).

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

        You don't necessarily need it. We are searching for the smallest n such that a1 + a2 + ... + an < x(the input val), so if you do prefix sum, you can search more conveniently. Again, this is not necessary.

        Pls upvote if this helps :)

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

      Very Very nice explanation

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

      Nice explanation!

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

    Refer to my solution. I think this is the simplest one to understand and apply. I tried to create all possible stairs from staircase with stair 1 then increasing. Subtracting all created stairs from n until its -ve. Hope is helps

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

    Refer to my solution. I think this is the simplest one to understand and apply. I tried to create all possible stairs from staircase with stair 1 then increasing. Subtracting all created stairs from n until its -ve. Hope it helps........

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

Jury's solution for D2 can't opened..

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

Please make strong pretests from next time. Nothing is more painful than getting your problem A wrong after the system testing :/

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

    First time creating a contest is hard, some mistakes may be made.... We will be even more careful next time.

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

      nah, pretests are good but problem B was hard to interpret.

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

      how u come up to 2^k-1 diectly..in div2b can u explain a bit. Thnx

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

        There's a really useful tool called messing around with the numbers

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

        First, one can easily see the basic solution is one stair (after understanding the problem, which took me something like 10 min).

        Then, the sample input explanation tells you that another nice stair is which have 3 stairs.

        Lastly, (maybe) you would notice that the image in the description has 7 stairs, and there are only squares with a side length of powers of two.

        So I assumed that nice stairs must consist only squares that have side length of powers of 2.

        Next is to prove it (you can choose to prove it by AC, but that's not what I'm gonna do here) using mathematical induction (or something similar): 1. assume that a solution with n stairs ( a_n ) exists. then you can see that by duplicating this solution and attach them to a bigger square in the middle (like the yellow square in the description), you can make solution ( a_{n+1} ), as you just created a new nice stair contains (2n+1) squares and (2n+1) stairs.

        Since the base case is 1 stair with 1 cell, the only solutions must be something in this series.

        I'm lazy so I'm not gonna write down the formulas. Hope this make you understand better.

        And, make sure to use 1ll instead of 1 when using 1ll<<x for powers of two. This cost me 40 min approximately during contest, which results in not having enough time for implementing pE and broke my dream to 1900+.

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

          This proof is not satisfactory enough. At best, it says that it works for 2*a_i +1 if it works for a_i. How do you still know there aren't any other numbers in the middle for which it works?

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

            Oops my bad. I forgot to mention that this is what i went through during the contest. As you say, this do not prove that there is no other solution, but I thought this was correct and gave it a try. If anyone knows the full proof pls let me know ><

            Thanks for pointing that out :)

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

      Problem B was not clear, ot really needs more explanation.

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

Please make tight pretests I realized my mistake after the contest in Problem A. Please try to set some pretests because passing two pretests I can then console the answer as well

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

My contest was ruined because of B. I will look for pattern and think less next time .

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

    I found the pattern in the "sum of first n numbers formula" during the contest. I just figured that we have to increase n by a power of 2 in this formula (n*(n+1))/2 and subtract it from x until you run out of cells. I just made this conclusion from the first two good staircases and tried my luck. here's my submission: https://codeforces.com/contest/1419/submission/93215283

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

      The only part I not understood is why "n" should increase by multiple of 2. Can you explain?

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

        Every staircase was just one greater than the previous one and it seemed like the sum of first n natural numbers. So the only thing that remained was which of these sums i had to choose. Look, the first good stair is formed with only one square where n = 1, the next one is when n = 3 that is total number of cells are equal to 6 and then the example in the problem statement had n = 7 and hence x = 28. Notice that 3-1 = 2 and 7-3 = 4 hence n is increasing as a power of 2. I tried all cases from n = 1 to n = 7 and only these 3 worked out which gave me more confidence on my intuition.

»
5 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

"If the single last digit is odd, then Raze wins, else Breach wins." It is not mentioned that If the single last digit is even then Breach wins. How can you assume that ?

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

    If the single last digit is odd, then Raze wins, else Breach wins

    If the last remaining digit is not odd, it is even. That should be obvious.

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

    I didn't understand your question. Any digit is either odd or even. Hence, if the single last digit is not odd, than it is even.

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

    My bad, I misinterpreted it -_-.

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

Great Contest !! Good work Guys

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

Great Contest, good editorial, nice question. Loved it :)

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

long statements were obvious and low pretests are obvious too because of this much of WAs after the contest

but out of those, problems were good

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

On question e: So, I don't know why, but I misunderstood the meaning of coprime (yeah I know) to be divisible, so two numbers that are coprime means (what I thought) a number is divisible by the other.

So I was solving a more restrictive case of the question. Well, not that it matters. I wasn't able to get it in time anyway.

Thanks for the fast tutorial!

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

I am unable to get the explanation for B. I know the pattern , but can someone prove it please ?

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

    I can't understand it either

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

    See, if you just try it out by yourself, you'll notice that stairs are only possible for n values: 1,3,7,15, 31....., i.e 2i+1. And also the cells needed for a particular value of n, is actually n(n+1)/2 . So one could just loop while sum is less than x and updating n with 2n+1.

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

Problem A got unexpectedly wrong for many!!

»
5 weeks ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it
»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the implementation idea for E? Even with the editorial, I still don't see how to efficiently sort all divisors into these "buckets" based on what prime divisor they have. Or is O(number of divisors * number of prime divisors) good enough?

Edit: thanks to everyone who responded. I forgot just how sparse primes are. Turns out, you don't even need to precompute primes, just checking for primality with a simple $$$O(\sqrt{n})$$$ function is enough: 93278287

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

    The maximum "number of divisors" for $$$n \leq 10^9$$$ should be around 1000 so it is enough to pass

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

    Before solving any queries, precompute all "small" primes up to $$$\sqrt{10^9}$$$. Then any number up to $$$10^9$$$ can have at most one "large" prime factor.

    Now to solve each query:

    For each $$$n$$$, iterate through the "small" primes to find out which "small" primes are prime factors of $$$n$$$. You will not TLE because there are only a few thousand "small" primes.

    Using this you can find the "large" prime factor if it has one. There will be at most $$$9$$$ prime factors in total because the product of the first $$$10$$$ primes is more than $$$10^9$$$.

    Then, iterate up to $$$\sqrt{n}$$$ to find all factors of $$$n$$$. For each factor, you can check all the prime factors. Again, you will not TLE because of the limit on the total number of factors.

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

    The problem guarantees that

    the total number of divisors of n for all test cases does not exceed $$$2⋅10^5$$$.

    And number of prime divisors is a small number, as it is at most 10 (2*3*5*7*11*13*17*19*23*29 = 6e9)

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

    Number of prime divisors is less than 10. And number of divisors is bound roughly by square root of n (it is only a loose bound, but already enough).

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

    More Simple (Easy to Understand) Solution for E:

    Insert all the factors of n in a set.

    Set the first value as s.begin()

    After that for each index i, find the first number from current set (using just simple iteration) whose gcd with ans[i-1] is not 1. And put that particular value at the ith position.

    That's it. You will be able to fill the whole array this way. No matter what is the value of n.

    It can be proved intuitively, mathematically, and with examples too. (Left to readers)

    For the number of insertions,

    The whole array won't need any insertions. Because we filled it in a way, that needs 0 insertions, for such arrangement.

    So, just check gcd(ans[0],ans[no. of factors-1])

    If it's 1, then insertions req = 1

    Else, insertions req = 0

    I solved it, this way.

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

      It can be proved intuitively, mathematically, and with examples too. (Left to readers)

      I'm really curios about this, can you at least provide some intuition?

      This is definitely much easier to implement, but I don't see why this process will never get itself in a corner. You essentially have a greedy algorithm, and it's a bit surprising to me that it works.

      I think there are two big questions: (1) why is there always a non relatively prime number available, and (2) why will the last one never be relatively prime with the first number (the first one must be prime, so basically why is the last number a multiple of the first one?)

      Edit: Ok, I see why (2) is correct: the last number you pick will always be n, so it's of course a multiple of the first divisor.

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

        Because n always come at the last position as you said and it is not coprime to any of the earlier numbers.

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

        I got a simple intuition while solving,

        It was like:

        If I take 1st element as smallest number (It will always be prime), and 2nd element as the smallest available non co-prime number with the 1st element, then, there will be a number in the factor list which will be non-prime with the 2nd element, always.

        Let's take an example:

        n = 6 Factors = 2,3,6

        ans[0] = 2 (We will set this)

        ans[1] = 6 (gcd(2,6) != 1)

        Now, if we have 2 & 6 in the factor list, one can easily say that 3 and maybe some other multiples of 3 too, will be there in the factor list, which will be non co-prime with 6.

        So, this will be valid for filling out the whole list.

        This was my intuition and an informal proof, for this solution.

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

          can you please explain, how will there always be a non co-prime number in the divisor set available? can this be proved? because this method is really great!Thanks!

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

    I don't know why this simple solution works 93280623. Is test cases are Weak?

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

I have used the same approach as mentioned in the editorial for Problem A & C but I am getting wrong answer.
Can anyone please help me out?
Problem A my submission.
Problem C my submission

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

    Problem A: "num" can be many digits long so it cannot fit in the int data type. You should store "num" as a string instead.

    Problem C: You missed out one case. From the editorial: "If at least one account is already infected we can infect all other accounts in a single contest."

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

      Oh shit!!
      Problem A: Got it.
      Problem C: I thought if the rating changes the account is no longer infected.
      Thank you.
      I don't know when will I get a positive rating...

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

      Is it given in the Question, if atleast one account is infected we can infect all other accounts.

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

    For problem A size of number is not given so you cannot store it in int try using string to input number, A

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

My approach for A was same as editorial then also got WA. Please help identifying the error

https://codeforces.com/contest/1419/submission/93215050

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

    It's not sure that $$$1$$$ would not win if $$$oddodd$$$ is lesser than $$$oddeven$$$. The case you're failing where $$$oddodd$$$ is lesser than $$$oddeven$$$ but $$$1$$$ could mark all the $$$oddeven's$$$ and win since he has $$$\lfloor{\frac{n}{2}\rfloor}$$$ moves which is greater than the count of $$$oddeven$$$.

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

In question A it is not given that positive integer is string(it could be taken as int type too).

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

    Which type you use is your personal affair However, it is given that it has up to a thousand digits, which does not leave much choice

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

    It's just stdin. You can read it as int or string but since n <=10^6, that integer value as a whole will be huge!

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

In the D1 problem, what to print if there are only 2 or 1 value as input? Do i just print 0 or do I also print out the order of similar to the input?

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

nice div2E

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

I think you overcomplicated D2... It's literally D1, just a tiny bit different in calculating the number of cheap ones.

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

why i can't see jury solution..?

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

    Yeah, it's a real problem. Fix jury's solutions, please!

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

In Problem C, I thought rating can't go beyond [-4000,4000] so messed up :(

I am curious though, how would we solve this problem if rating can't go beyond this range.

Any ideas?

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

After seeing the number of successful submissions in D2 and E, I really wish I hadn't tested this round and would've given it live. Would've been a really great opportunity to go back to purple. ;__;

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

https://codeforces.com/contest/1419/submission/93253990 Can someone please tell why this code is failing at test case 2. It is giving the right answer when i put in those individual test cases, but for some reason when i am putting them collectively, its failing to give the right ans.

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

    The input number is very large you cannot store it in int or long , use string to store the number, A

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

one of the best codeforces round i have taken part in .. great problems, enjoyed a lot :) :)

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

There was not a necessity of including the problem D1 in this contest.

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

Problem D is solved more than Problem A.. weird..

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

    It's not weird XD this problem indeed has the same difficulty as A.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

D2 can be solved in a very simple greedy fashion. I simply sorted a[] and first filled all even positions for the final order and then filled all odd positions in the increasing order of a[i]. See my submission for better understanding — https://codeforces.com/contest/1419/submission/93275649

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

    I think sorting takes O(nlogn). So solution can also be O(nlogn). Right?

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

      Yup, but i found this to be very straightforward and elegent.

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

    I am practicing after contest and I also came up with this solution intuitively but I wonder how to prove it, do you also have a proof?

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

    Yes, seeing many of submissions use greedy. Why this greedy approach can work? Any proof or idea can help me better understanding on this? Thanks!

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

    https://medium.com/@harryjobz/sages-birthday-1c68ffc70987 Simply pick all the even positions first in the sorted array like you said. I have explained how here. It does not matter actually how you pick the odd positions after you are done picking the even

»
5 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

On clicking the link for jury solution of E, it shows "You are not allowed to view the requested page." P.S. It is fixed now.

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

Though this is not gaming community, I thought there will still be lots of comments regarding valorant. But I am alone :(

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

When I click on Jury Solution I get an error "You are not allowed to view the requested page".

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

I have a question about D2.

My solution is to just order n/2 biggest elements at odd position in increasing order, and n/2 smallest elements at even position in increasing order.

After I solved E, just about 10 minutes were left so I submitted this solution without any hope. But it passed system test .. Can someone prove my solution?

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

    Let's call a number "big" if it's bigger than the median, "medium" if it's equal to the median, and "small" if it's smaller.

    You can easily see that an optimal solution can be constructed that consists only of small and medium numbers. In your solution, all the small numbers are automatically cheap. And the number of cheap medium numbers is bounded by the number of large numbers (minus 1), which your solution also gets.

    So it's impossible to do better.

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

    Assuming that your proposed solution is 1-indexed, consider the following. On placing the smallest (n / 2) elements in ascending order in the array at even positions, it's ensured that the two smallest elements in the larger (n / 2) elements will be matched against the smallest element in the entire array, In case of any other ordering of the two smaller elements in the array, against which an element from the smaller n / 2 elements may be compared, there is always an alternate ordering where the comparison is never worse.

    For instance, if the two smallest elements in the larger (n / 2) array are x and x + y, and they are currently compared with some s, where s is not the minimum of the array, replacing s with s — t (t > 0) never yields a worse comparison result.

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

    I also solved this way

    My thoughts

    The array will look like this

    \/\/\/\/\/\/

    So obviously we will not get more than n // 2 items and we should consider n // 2 smallest

    Also, for n < 3 the answer is 0

    Now, let's look at elements [n // 2], [n — 1] and [n]

    If [n - 1] > [n // 2],

    then everything is fine, we captured the most expensive item we could hope for, there is no better use for [n — 1] and [n]. We can add one to the answer and forget [n] and [n // 2], effectively reducing the problem to size (n — 2). We don't forget about [n — 1], but on the next step we will have to place it at exactly the place where it already is.

    If [n - 1] == [n // 2]

    Let's consider [k] such that [k] is the rightmost element less than [n // 2]. Then all elements in range k + 1... n // 2 are absolutely unreachable no matter what we do as they're equal to [n — 1]. And all elements in range 0... k are reachable by elements n // 2... n because these elements are certainly bigger

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

Though I liked the questions , and also the editorials were fast , I would like to request you to make better pretests , as it hurts man when one of your solution which you assume has been passed gets failed, it really hurts man. Today I have seen many of them for question 1st and 5th , hope this doesn't happen again , as it really really hurts

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

There is no access to jury's solutions

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

Can someone help me with the search for errors in my solution of E? I can't understand tester's comment on WA2.

wrong answer Integer parameter [name=divisors[1252]] equals to 0, violates the range [2, 735134400] (test case 1)

Where is the problem in my answer for this test? I can't see full correct answer, I can't see jury solution right now, I don't know where is error in my program :(

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

    It means you have not output all divisors of 735134400. There are 1344 in total. The judge has read the zero in the second line as a divisor not as the number of moves. That is why you get this error message.

    Edit: Since 1 is coprime to all numbers, you only have to print 1343 divisors.

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

Its nice to have these kind of "adhoc only" round sometimes. Even the idea for F problem is very easy to come up with (implementation is definitely tedious). Nice round!

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

Thanks for soooooo fast tutorial! And also thanks for the great contest, it improved my coding skills greatly lol.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

The author's solution E is not correct, in particular, for example 12. It will make 2, 12, 6, 3. And the answer will be 1, although it is clear that it is 0 (that is, for 2 prime and at least 4 divisors)

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

    They haven't explained how the following case will be handled exactly:

    $$$ {p_1}^{q1}.{p_2}^{q2} $$$ where ($$$ q1 > 1 $$$ or $$$ q2 > 1 $$$). 12 falls in this category, although they have handled this case in their jury solution.

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

    This can be easily handled if after making the structure mentioned in the editorial, one starts filling up divisors from the last prime $$$ (p_{n}) $$$, this way we can ensure that there will be always something in between $$$ p_{n} $$$ and $$$ p_{1} $$$.

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

I fst *2...

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

what does these lines mean? If n is even the remaining digit will be red. If n is odd the remaining digit will be blue

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

Already ELO in Valorant and now happening here also.

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

not a good contest

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

It's also possible to solve problem F with the observation that, given any minimum spanning tree of a graph, that graph is connected by edges of length at most $$$t$$$ if and only if that minimum spanning tree has no edges longer than $$$t$$$. (This is equivalent to saying that Kruskal's algorithm works.) Adding one vertex and at most four edges to a graph doesn't change its minimum spanning tree very much, only removing at most three of the edges in the original minimum spanning tree, so it's possible to calculate the minimum value of $$$t$$$ for any plausible relevant detachment location in $$$O(5^2)$$$ with a modified Prim's algorithm on an 5-vertex graph associated with that location. (See 93293641.)

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

Framing of B question was very confusing. It took me more than 1 hr to just know what the question is saying.

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

Can anyone explain problem A solution?

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

D2 was an Easter egg.

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

My solution can pls anyone tell where i am making the mistake in digit game

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

    Value of num is very large it can't fit in int or long long , use string for num , A

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

In B, the problem is basically choose the maximum count of numbers from (1, 3, 7, 15 ....) and form any number less than equal to x. Why can we solve it greedily? Shouldn't we be applying dp?

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

    Because we need to find the maximum different nice staircases using 'at most' n cells, and if we use from small nice staircases to big nice staircases It always have the correct answer. Using dp, if he ask 'how many ways' using exaclty n cells.

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

      I still don't understand. Isn't the concept similar to coin change dp problem?

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

        In this specific problem, you need dp if you have to use exactly $$$n$$$ cells.

        Greedy is enough if you have to use at most $$$n$$$ cells.

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

Am I the only one who thinks that C could have been phrased a little better ?

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

Loved the contest! I think D questions were a bit too easy, but hey I'm a newbie so I shouldn't complain!Also a quesion on Omen could've been more interesting ;)

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

In problem stairs:

If we take staircase of height 6, then it can be an answer, with 1 square of size 3, 2 squares of size 2 , and rest will be squares of size 1, they will be disjoint , only corners of same size square will touch.....check if this case is right or wrong.

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

who can tell me the train of thought ( is it right? ) of F? ( or tell me where it is thanks )

i can't understand the solution

thank you so much

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

The Dashboard was quite interesting!!!

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

To speak the very truth,I couldn't understand the statement of problem "B" properly.Solution is so far!Could some of you help me,please.

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

shishin: Although the contest was good, the problem statement of C was not really clear. After reading the tutorial only, I figured out that if I have one infected account, I can infect all others by making all others equal to infected one, then change the infected one. Reading the problem statement, I didn't find any clue of that, what I interpreted while reading was, that newly infected accounts and the previously infected account (from which new infection occurs) should have same ratings even after the contest. I think mentioned word "instantly" didn't really justified the phenomenon you were trying to convey. It may be possible that only I found this thing to be difficult to understand. I hope you take this as a constructive criticism.

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

Ok but E was just USAMO 2005 right?

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

    Why are you not getting Segmentation fault in these lines?

    for (ll i=0;i<n;++i){
              if(a1[i]>a1[i-1]&&a1[i]>a1[i+1]){
                  ++cnt;
                 
              }
          }
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain further

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
         for (ll i=0;i<n;++i){
                  if(a1[i]>a1[i-1]&&a1[i]>a1[i+1]){
        
        1. Your if condition is wrong. Count will increase if a1[i] is smaller than a1[i-1] && a1[i+1].

        2. for i = 0, a1[i-1] is not defined, and for i = n-1 , a1[i+1] is not defined.

        Correction :

        for (ll i=1;i<n-1;++i){
                  if(a1[i]<a1[i-1]&&a1[i]<a1[i+1]){
                      ++cnt;
        
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i did as you said but now it is failing at the very first test.

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

            because above loops are failing on boundary conditions. dry run of your program. You'll understand.

            Below is solution, which is exactly the same idea.

            93306091

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

    It's very surprising how you passed test case 1 as a1[-1] is not possible.It's array out of bound.

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

shishin Thanks for fast editorial. Questions were nice. I have a feedback for editorial.

Please explain things in more details. Just like problem D, it was hard for me to understand how binary search actually fits here. I understand, for you it may be very obvious but for new bies, sometimes it is difficult :).

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

I have an alternate solution for D2. Sort the array, place the first half on odd indices and second half on even indices. For example if the sorted array is 2,4,6,8,10; then make the array as 6,2,8,4,10. After this, count the number of elements which are less than their neighbours. If there are repeated elements, it would still be a valid arrangement to find maximal no. of cheap spheres.

This is in a way similar to your solution, where I am using the same concept that if we can find x cheap, we can definitely find x-1 cheap spheres too. By this method, you can directly get the maximum amount of cheap spheres possible.

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

    Yes, most people who did greedy used this. It's easier to see.

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

    thanks santosh. Later I submitted with above solution. But I am not able to develop sense of applying binary search. After getting solution, I realise binary search can be applied, but lacking intuition of knowing at first place "Yes binary search will help here".

    Tried to understand D2's juries solution, but It seems to be long. and flag like "f" makes it hard to understand.

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

Still can't understand problem B. Can anyone help me?

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

    square.png

    Nice stair case : If all squares are contributing in stair step So you can see, all squares present in this image are contributing in one step of stairs.

    So for making stair case with n stairs, you must have exactly n squares.

    This can be true only if n is "powerOf2-1"

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

    If you managed to find the pattern, then the problem becomes pretty easy. Here's my submission- 93223145

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

what does this line mean ? A staircase with n stairs is called nice, if it may be covered by n disjoint squares made of cells.

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

    It means if a staircase can be completely covered with n non-overlapping squares that don't go out of the staircase, it's called nice. (look at example)

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

    So for making stair case with n stairs, you must have exactly n squares.

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

Can anybody please explain me the first problem.. I am struggling with what has been explained. Thanks in advance.

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

    Raze can delete only elements from odd places, while breach can delete only from even places.

    if(totalNumOfDigits is even){ 
    //last element will be removed by breach. So if at even places, if there is a single even number, Breach can keep it till last, and it wins. other wise last element left will be odd and raze wins.
    }
    else { //totalNumOfDigits is odd
    //last element will be removed by Raze. so if there is a single odd number at odd places, raze will keep it till last to wins. If all numbers on odd places are even, breach wins.
    }
    
»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

In E, what if k=2 and q1+q2>2, n=p1^q1+p2^q2. Then p1*p2=pk*p1, so it doesn't work. For example: n=24, 2 4 8 24 6 3 6

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

Why simple sorting and greedy placing did worked for me in problem D2 submission

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

Could someone please provide a formal proof of why the greedy solution in D2 works. I understand till the idea that picking the smallest (n-1)/2 elements is the most beneficial way as it's always better to keep the possible candidates for the center as low as possible. But I'm not able to proceed beyond that in the proof. Thanks in advance.

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

https://codeforces.com/contest/1419/submission/93311817 can anyone please tell me why I am getting wrong Answer

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

Can someone tell me what is the complexity of this solution for problem E? 93314845

During the contest I was sure this would TLE, but voila!!!

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

I think the statement of the ahead two problems is a little bit long.....

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

Why to make D2 complicated (by using binary search) if this simple approach is enough.
Solution

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Please somebody tell me what am I missing in C
https://codeforces.com/contest/1419/submission/93322918
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the case in which all the elements are equal in your code you have 2 options, if they are equal to x the answer is 0 but in the opposite case the answer must be 2 because there is no way that the sum of the differences is 0, so you have to infect n-1 and leave one uninfected to make up the sum for what you need 2

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

      Got It! Thank you for explanation brother!

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

Thanks for nice problem set and quick editorial.

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

https://codeforces.com/contest/1419/submission/93326069

I am failing test set 10 on problem E because of incorrect number of transformations on case 25, yet when I compare it with correct solutions, it gives the same number of transformations. Is there a bug? Or am I missing something?

Thanks in advance

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

https://youtu.be/fHyJObr8EdI My solutions ( A-D )

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

I solve problem D by putting the smaller numbers in even position and bigger numbers in odd position.... Here's my code: 93251846

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

Hi everyone! I am not able to understand the logic of the part ~~~~~ else if (cnt > 0) { cout << 1 << '\n'; } ~~~~~ in the jury solution of the problem Killjoy at line number 21. If cnt represents the number of ratings equal to x initially, how does it being greater than 0 helps in determining the contests to be 1?

E.g. If we have x = 70 and the ratings as [70,72,74], the answer should be 2 contests but the solution should show it as 1.

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

    The answer is 1. Imagine we sum the difference to 70 for all numbers, we call this number k. k = (70 — 70) + (72 — 70) + (74 — 70) so k = 6. It may seem that you need another contest but because 70 = 70 we can infect this account before the contest start. And now we can sum or substract to this k. The process will be: 1.Infect account with rating 70. 2.After the first contest accounts will be [76, 70, 70].

    If (cnt > 0) it means that we can inffect one account before the contest. So we will need just one contest to infect the rest.

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

      Hi, thanks for the explanation. Also did you mean that in step 2 of the process, after the first contest, the ratings will be [76,70,70] i.e. we will compensate k=6 by adding the already affected account by 6 and subtracting it from the disinfected accounts?

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

Hi, Why solutions with 10^5 sqrt(10^7) gets TLE? This number is less than 10^9. It is a doubt related with another problem involving number theory. https://codeforces.com/contest/1366/problem/D. Thank you.

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

CAN ANY BODY TELL THAT IN PROB C OUR NEW RATINGS CAN GO BEYOND -4000 OR +4000 ???

PLEASE tell

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

in the b problem the tags say two pointer . Is there a two pointer method ?

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

My code for problem D accepted D2(93375350) but failed in D1(93375360)

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

D is quite simple if Binary Seach didn't click to someone

MY SUBMISSION

The idea is quite simple

Sort the input array and design the output array in the following fashion

a(n/2) a(0) a(n/2+1) a(1) a(n/2+2) a(2) ...alternating

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

I used the same logic as above to solve the Problem A, It showed wrong answer for pretest 2. Can anybody help me debugging my code? Link to my solution:- 93208219

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

Nice Problems!

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

great job!

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

Can anybody explain Killijoy properly?

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

Not able to understand B

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

I'm afraid the problem E is a bit easier than common...

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

    And many of my friends said that they have difficulty understanding the problems...

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

I think problem B was good, but language is not clear...

ll int t=1;
cin>>t;
while(t--)
{
        ll n;
        cin>>n;
        ll c=1;
        ll int ans=0;
        while(1)
        {
            ll x = (1ll<<c)-1;
            n=n-(x*(x+1))/2;
            if(n<0)
            break;
            else
            ans++;
            c++;


        }
        cout<<ans<<endl;
            }
return 0;
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

neal actually make D2 a greedy problem, how to prove it, can someone help me ?

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

    Sort the array and partition the array into halves, name them $$$A$$$ and $$$B$$$. Where elements in $$$A$$$ are lesser or equal to the elements in $$$B$$$. If length $$$n$$$ is odd $$$|B|$$$ = $$$\lceil \frac{n}{2}\rceil$$$ and $$$|A| = \frac{n}{2}$$$, else $$$|B|$$$ = $$$\frac{n}{2}$$$ and $$$|A| = \frac{n}{2} - 1$$$. Clearly, in both cases, The Cardinality of $$$A$$$ is the $$$answer$$$(Upper Bound) if all the elements of $$$A$$$ and $$$B$$$ are different.

    Say, $$$x$$$ the last element of $$$A$$$ and try to place it between any two adjacent elements in $$$B$$$ that are greater than $$$x$$$ and obviously that may be the last two elements of $$$B$$$ or if there's any other two adjacent elements in $$$B$$$ are also greater than $$$x$$$, then you can still swap places(i.e still place $$$x$$$ between the last two numbers).

    If there's no such two adjacent elements, you can still place $$$x$$$ between the last two numbers(since, placing $$$x$$$ between those two last numbers doesn't affect placing other element in $$$A$$$ which is less than $$$x$$$ between those two last numbers because, there should be at least $$$2$$$ spots) and take the second last number from $$$A$$$ as $$$x$$$ and do the same for rest of the elements of $$$A$$$ and it's not necessary that the elements around the elements in $$$A$$$ after merging should be greater than them. So, find the number of elements which are smaller than its neighboring elements.

    May not be good as you'd expect but this was my intuition.

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

Why are the limits in F so tight? Even after 4 TLEs and a bunch of constant optimisation, my $$$O(n^2 \log 10^9)$$$ (93436282) barely passed in 1996ms.

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

    Jury's solution passed in 46ms, so we think the limits are ok.

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

How do you prove that a nice staircase has height $$$2^k - 1$$$ for some $$$k \geq 1$$$ for problem B? I got the recurrence $$$s_i = 2s_{\left\lfloor{\frac{i}{2}}\right\rfloor} + 1$$$ where $$$s_i$$$ is the minimum number of squares used to cover the staircase with height $$$i$$$. I used this to find all nice staircases, but I don't see how it relates to $$$2^k - 1$$$.

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

Thx

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

pls someone can help me in the 1419d2 here is my solution i have used this idea sort the array print the last element then first element and then 2nd last element then keep on printing the element from the front which is yet to be printed and the last element which is yet to be printed for ex tc: 1 3 2 2 4 5 4

first sort 1 2 2 3 4 4 5

5 1 4

5 1 4 2

5 1 4 2 4

5 1 4 2 4 2

5 1 4 2 4 2 3(final ans)

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

In problem-C: Where it was told that I can also change the rating from already infected contestant?

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

    In each contest, any of these n accounts (including infected ones) can participate. Killjoy can't participate — 3rd para, 2nd sentence.

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

I feel like the solutions given in Editorial for problem D and E, are the way too complex than it should be...

My solutions for both these problems are: 93217720 and 93561739

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

There exist a solution of F with time complexity of $$$O(2^m n\log^2 n\log T)$$$ where $$$m$$$ is the number of components that is $$$\leqslant 4$$$ .

It uses scanline and Segment_tree Divide (sorry for cannot explain it in English excatly) to count if there is a point coverd by all the components.

Upd : I've improved my algorithm to $$$O(2^m n\log n\log T)$$$ which allows n up to $$$10^5$$$. We can just turn range modify to range query so that we don't need segment_tree Divide.

code

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

Hello!

I have solved F in the following way and am getting WA6.

Algorithm: The difference with the solution in the editorial lies in checking whether certain value is valid. The way I check it is that after performing a DFS on the graph with a limit $$$T$$$ on the distance, we get a list of components. I leverage the fact that the point to be added must share either $$$X$$$ or $$$Y$$$ coordinate with each of the components. So I pick the smallest (in number of vertices) component and iterate through the $$$X$$$ and $$$Y$$$ coordinates of its points. For each, x0, I compute the possible intervals for $$$Y$$$ coordinates. To do that I compute such intervals for each component one by one and intersect these sets of intervals. Before computing the intervals, I've first sorted the points in the components based on its $$$X$$$ or $$$Y$$$ coordinate depending on for which coordinate I'm computing the feasible intervals. This results in the intervals being sorted in ascending order. In turn, this makes it easier to intersect the intervals in linear time. In the end if the intersection of these intervals is non-empty, then we can find such point, otherwise we can't.

Can anyone see any flaws in the approach or is it rather implementation error?

Any feedback highly appreciated!

Thank you!

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

    YLWang does this sound similar to your approach?

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

    shishin Have you considered or come across a solution similar to the above? Thanks

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

    Found my mistake, it was extremely subtle typo, copy-paste error. In one place, instance of somePoint.x, I had somePoint.y. Took me hours of debugging...

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

    I think the main idea of your approach is right. Maybe details got wrong.

    You can use generator and brute-force to check your solution.

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

      Thanks!

      I sorted it out as mentioned in my last comment. The bug was that when sorting points based on $$$Y$$$ coordinates, when y's are equal, I should compare x coordinates, but I was comparing x coordinate with the other point's y coordinate. Silly typo. Once that's fixed, passed all tests in 249ms in Java 11. Here's the accepted submission

      In terms of finding the error, I was expecting it to be a genuine error so was reading through more complex parts of the solution :) The way I found it was to take fully visible tests from CF tests. I had to run on 30 tests before finding a failing example. For this problem, to generate valid test cases where the answer isn't -1 requires a bit more careful impl than just generating random points. I was reluctant to do that.

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

for problem D1 and D2, you could have just sorted the array, and placed the first half of the numbers (lowest numbers) in increasing order starting from index 1, placing them every other index, and place the other half of the numbers (highest numbers) in decreasing order in an opposite fashion, then using basic implementation to get the answer afterwards

for ex: 1 3 2 2 4 5 4 -> 3 1 4 2 4 2 5

in the end its just a constructive problem running in O(n log n)

code: here