Блог пользователя shishyando

Автор shishyando, история, 4 года назад, По-русски

Привет, Codeforces!

Мы с Artyom123 и Kotehok3 рады пригласить вас на Codeforces Round 671 (Div. 2), который пройдёт в 19.09.2020 17:35 (Московское время). Этот раунд будет рейтинговым для всех участников, чей рейтинг ниже 2100 (По крайней мере мы очень на это надеемся).

Мы хотели бы поблагодарить:

У вас будет 2 часа на решение 6 задач, одна из которых разделена на простую и сложную версии (ну или чтобы поиграть в Valorant, которому и посвящён этот раунд по какой-то никому не понятной причине).

Вам придётся разбираться с проблемами агентов из вселенной этой игры, чтобы получить заветный плюс к рейтингу. Помогайте им так, как будто это ваши союзники в рейтинговом матче!

gl hf

Разбалловка задач: 5007501250(750 + 1000)22503000

UPD: Разбор

  • Проголосовать: нравится
  • +367
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I hope that statements are short with strong pretests.

»
4 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

"This round will be rated for all participants, whose rating is lower than 2100 (We really hope so)."

:(

»
4 года назад, # |
Rev. 4   Проголосовать: нравится -42 Проголосовать: не нравится

You must remember — peaker has an advantage!

»
4 года назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

The first 6 problem round in such a long time!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +79 Проголосовать: не нравится

That day will be my birthday, I hope i can do well on that contest and make the day more memorable...

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I hope that Dindic`s algorithm will be in the round

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Храплю как гаст

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Можно раунд по кс?(

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +31 Проголосовать: не нравится

Tired of posts about short statements and strong pretests

So what if statements are long? So what if pretests are weak? Everybody is in equal position and competitive spirit does not waver. For all I care you can remove all pretests and I will gladly participate anyways.

What I really need is short queues and strong/correct checkers. And if I can ask for more, then give me an appropriate editorial

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +40 Проголосовать: не нравится

    Removing pretests will definately make queues shorter! :D (Ofcourse we won't do that)

    As for the tutorial, we will try our best to make it as understandable as possible.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    some old Codeforces problems have weak pretest causing high amount of hack which cause some lucky people can get free 1500 point by spamming "0" zero in his room

    https://codeforces.net/blog/entry/59431#comment-430573

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    So what if pretests are weak? Everybody is in equal position

    I really disagree with this. Yes, everybody gets the same pretests. However, people are hurt differently. Some people (me for example) rely on strong pretests for problems like A and B. These problems usually have multitests and generating strong pretests isn't that hard. Others are careful and don't trust the Pretests Passed verdict. They will still check their code for logical/implementational errors and corner cases. Clearly, strong/weak pretests makes a huge difference for these two types of people.

    Removing pretests will definately make queues shorter! :D (Ofcourse we won't do that)

    shishyando this seems like exactly what you did. 1 pretest for A (not including samples) and around 70 systests for A (causing such a long queue that systests still hasn't finished). I FSTed A, and I didn't want to wait for all the systests to finish so I decided to stress test myself (by copying an AC submission). Turns out that my program messed up the parity of each position when n is even. However, to my disappointment, such a submission (surprisingly) passes all the pretests. I am interested as to why the for pretests for A are so weak. An easy solution would be allowing 1000 tests and have the first 100 be max cases (to check for tle) and the rest be randomly generated binary strings of length from 1 — 10. Another option is to just generate all binary strings of lengths 1 — 9, in addition to max cases. Both seem really easy to implement and I'm curious why you didn't do so.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -17 Проголосовать: не нравится

      I had to make a single pretest in A (except the sample) to avoid long queues. The pretests were made randomly, and I thought that it was strong enough. We didn't find any problems with A's tests during the testing phase.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Even with 1 single pretest in A, you can still easily make strong pretests. Allow there to be 1000 cases, guarantee that the sum of n doesn't exceed 2e5, and make each case small to better account for various corner cases. The issue with problems like A is that special cases only appear when there are no even/odd numbers in all even/odd positions. Thus, randomly generated large tests are very bad at "hacking" solutions. Also, shishyando what is the thinking behind having 70 systests for each problem? This is the slowest systest I've ever seen and it seems that a lot of the tests are unecessary.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I would've argued that I'm don't mind exchanging strong pretests for more algorithmic questions, but it seems there is not much to exchange.

      I understand not wanting to waste time on A&B. I myself managed to pass pretests with an incorrect checker for that very reason ^_^

      Of course it would be a different game without pretests, but I would play it anyway. People would work on their solutions more rigorously and really try to prove it before submitting

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        What I'm trying to say is that weak pretests affects everyone differently, not that

        Everybody is in equal position

        as you've suggested.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did not care about weather the statements were long but the pretests on C should have been stronger. I failed it on test 61. Also from what the test case constraints were clarifying the ratings of an individual could only be in the range [-4000,4000] to which I based my solution on and that is why it did not pass. You would tell me "well why did you not ask for a clarification" well the answer is because my submission passed all the pretests thus I imagined that that was the solution.

    I have no problem with the problem statements being long. 0 problem. But the pretests must be strong.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

VALORANT!!!!!!

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

Clashes with ioi (

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Gamers joining Codeforces because of Valorant .

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Normal Div 2 Rounds: Score distribution will be announced shortly before the round. Div 2 Round 671: Here is the score distribution Meanwhile other testers: Are we joke to you?

»
4 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

As a tester I recommend you to read all the problems.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Thank you problem setters and testers for taking the pain to arrange the contest.

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

I can assure you. ;-)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

One other thing I couldn't care less about is the score distribution. Seriously, why people always talk about it?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    The score distribution tells you roughly how hard the problems are so you can plan your strategy in advance. For example, if you have solved A and B and are stuck at C, you can try working on D1 because it should be easier (at least to the testers) compared to C.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ok, but except for compound problems, there should never be later problems with lower difficulty rating. It contradicts the very idea of sorting problems by difficulty and most rounds don't even involve compound problems

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Conflict in opinion is common to happen. Maybe, according to the problem setters, some problem is harder, but when the testing round occurs, sometimes that problem is found to be easier to the testers.
        That's the significance of the scoring distribution. It maps to approximate difficulties of the problem to help the contestants. :)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          I just don't see how it can help. If you want to know approximate difficulty, you just look at the number of solutions.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    I use it to determine if I'm participating in codeforces or speedforces.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Again, during the contest you have much more reliable source of information about difficulty — number of successful solutions

»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Hoping to become expert in this contest.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

" A problem has an easy version and a hard version. " This hasn't happened in a long time, I'm waiting.

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Oh, score distribution is cool. Hope the problems will also cool and there'll be no issue with the problems like the last round.

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

A very unique and interesting rating graph shishyando xD

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hope Retired_cherry will change some problem in the last few minute, and some guy will solve it in 1 minute.

»
4 года назад, # |
  Проголосовать: нравится +85 Проголосовать: не нравится

As a tester, I can confirm that problem statements contain words.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wasn't scoring distribution supposed to updated only 5 hours or so before the contest?

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

we want a contest that is related to pubg!!!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is the fourth one 750+1000 instead of 1750? Is that intentional?

»
4 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

CS:GO themed contest when? :p

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Subtasks! After a really long time.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Subtasks! After a really long time.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Super excited :D

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When are we planning to have another Codeforces Round 657 (Div. 2) type of round, which was a nightmare more me. Also are we expecting more mathematical problems in this round?

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

bol fy fca.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -62 Проголосовать: не нравится

IPL starts today. Which team are you supporting today? #MIvsCSK

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm looking forward to see "Score distribution is changed to * * * * * *

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Sorry IPL, Not today.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится

(WhatsApp-Image-2020-09-19-at-6.00.00-PM.jpg)

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

    IPL will last for atleast a month so are we expecting these type of memes in every contest? I hope not.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, actually today was the first match amidst this lockdown and that also between two teams who meet in the finals many time. But yeah, this is not the right place for such memes

»
4 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

The round is also clashing with Leetcode biweekly contest 35. Can there be possibly any change in contest time?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Who else is just waiting rn for contest to start?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think Gamers are joining Codeforces because of Valorant :P

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

This will be the first contest I have ever done. I hope all participants have fun and challenging problems to solve and learn.

I thank all of you; authors for your time and energy.

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Когда написал тупой коммент и смотришь на свой вклад: https://www.youtube.com/watch?v=pgRZpbT5w7k

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope will not be like the last contest, because it was disappointment.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

as a tester you will enjoy this round

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm not sure about problem statements, after they say about the "Valorant" part. Hope to have good statements. :3

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Understanding problems is similar to finding Among Us Imposter

»
4 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

god damn it I fu**ed up in A and B it could've been way better

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please tell me how to solve D2 and E? Thank You very much.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      $$$D2$$$

      $$$D2$$$ can be solved in the same way as $$$D1$$$ — just place $$$a_{n/2+1}$$$ ~ $$$a_n$$$ and $$$a_1$$$ ~ $$$a_{n/2}$$$ alternatively.

      $$$E$$$

      $$$E$$$ can be solved like this: If $$$n$$$ has a divisor which is square number $$$k^p (k,p>1)$$$ greater than $$$1$$$, find all divisor of $$$n$$$ (let's define these as $$$a_i$$$.) which is not the multiple of $$$k$$$, and order $$$a_i \times k^p, a_i, a_i \times k, a_i \times k^2 , \ldots a_i \times k^3$$$. Repeat this to get an answer, and the minimum number of moves is $$$0$$$.

      If $$$n$$$ has no such divisor, it means $$$n$$$ is equal to the product of $$$m$$$ ($$$2 \le m \le 9$$$) distinct prime numbers. And there will be $$$2^m-1$$$ divisor (except $$$1$$$), and we can consider those as combination of different prime factors — $$$b_i$$$ is multiple of $$$j_{th}$$$ prime factor of $$$n$$$ if $$$i \And (2^{j-1})$$$ is nonzero. Now we just need to rearrange the numbers from $$$1$$$ to $$$2^m-1$$$ so that the bitwise and values of all two adjacent enlements are nonzero. And for each number $$$i$$$, print $$$b_i$$$. The minimum number of moves is $$$1$$$ if $$$m = 2$$$, $$$0$$$ if $$$m \ge 3$$$. The rearrangement method can be found by considering the following sequence: $$$\left[1,3,2,0,6,4,5,7\right]$$$

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Approach for C??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    First, check if the average distance from x for each element = 0. If it is, then the answer is 0 if all elements already equal x, else 1. Otherwise, if x is in a, then the answer is 1. Otherwise, answer is 2.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    you do it in atmost 2. the case for 0 is easy. 2 can be done by infecting (n — 1) elements while using the last one as offset and then infecting the last one while using any element as offset. The case for 1 was tricky and I did some guess work.

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

This round is too unbalanced. In A — D you just need to figure out the idea, and don't have to know any algorithms, and around 3500 people solved all of them, but E is probably too hard for div2.

  • »
    »
    4 года назад, # ^ |
    Rev. 6   Проголосовать: нравится +33 Проголосовать: не нравится

    For A-D, I agree with you but E is definitely not hard. It's basic number theory and observations(constructive algo).

    Hint for E : Just find prime factors of the number and try to put the product of then any two primes in between those 2 primes. Obviously, you need to handle some corner cases like prime square or number is product of only 2 primes.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, the gap between D and E this time was surely overwhelming...

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        See, it is very difficult to make a balanced contest. Actually in D2, simple greedy algorithm worked(place the smallest (n/2) elements and then remaining in the gaps between them). That's why D2 had so many submissions. I think no one in the testing team thought that such algorithm would worked, else problem D would have been definitely replaced.

»
4 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

This was basically speedforces

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for a "nice" B:)

I hope Codeforces employs some proof readers for the statements. The statements should be better.

Waste so much time in B that could not focus on C even when I kind of had the idea that max 2 answer is possible. Definitely my fault but the statements could have been better.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    can explain what is meant by nice stairs in the statement thanks for help

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    B.png Can you explain why stairs with n = 5 is not nice stairs? We can form 3 squares of size 2, and remaining of size 1

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      In the shape 6 squares are used, but with n=5 (for 5 stairs) 5 squares should be used

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You should for only n squares

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      because we have to use n numbers of squares.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      The nice stairs can be covered by n disjoint squares made of cells, not n types of squares. There are 6 squares in your picture, not 5.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      thank you all for your replies. I'm really stupid

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      i don't see the right reply

      it was given in statement every cube should have one of it's corner as stair. orange cube doesn't have any corner as stair, thus not nice.

      Edit here is statement All squares should fully consist of cells of a staircase.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem C when can the answer be 1 ??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    When average of all arr[n] (arr[n] != x) == x

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    If all elements already sum to zero (after making sure that all elements are not equal to x) or if x is in a

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    when mean is x or there is at least one rating already equal to kjoll's rating

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    When the average of the elements is equal to x (fix each one so and make it x, the net rating change is 0), or when there is at least one other element equal to x (this on is already infected, so all rating changes will go to this one, and change all other values to x)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    it is 0 if everyone has rating x. Otherwise, it is 1 if either at least one other person has rating x or if the sum of the ratings of the n people is n*x. Otherwise, it is 2.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I knew that when sum equal to 0 then it will be 1.But why when x is present in a[] then also result is 1?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      When x is present in A[], then what we can do is make all others as X and add up the rating changes and add it to A[i] where A[i]==X;

      for example 4 5 5 3 6 1

      5(-2+1-4) (3+2) (6-1) (1+4) are the rating changes and all are infected

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

IS following approach correct for E!

find all factors then find all prime factors of it let all prime factor sequence be like a1<a2<a3. then first club all factors divisible by a1 together that is put them side by side then remaining factors divisible by a2 together then by a3 and so on I think then finding minimum answer required is easy!

Please correct me if I am wrong!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Brute force will TLE

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      I guarantee my complexity to be sqrt(n)*log(n) for each case and I think it will pass lets implement later on when sys tests pass!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится

        Your approach will definitely get TLE

        sqrt(n)*2e5 not sqrt(n)*log(n)

        Do some paperwork you will understand how

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          WHy 2e5! Cant we store prime factors of that number in a vector rather than iterating overall primes again and again! I think you didn't get the idea completely! and just iterating over the prime factors and factors in a single go !. By the way correct approach is in comment below!

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            what you are doing now basically is sieve of 1e9

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

              The approach will not TLE.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                It is possible that i am misunderstood and. thinking of a different thing than what you both are trying to say.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                  Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

                  So here is what we do.

                  Given an input n, we find its prime factors in O(sqrt(n)) time.

                  Once this is done, we also find the divisors of n in O(sqrt(n)) time, and classify it in accordance with the smallest prime factor dividing it.

                  Then, we simply print these divisors in a nice fashion.

                  This algorithm takes time O(sqrt(n) + tau(n)). If we sum this across all test cases, we have an upper bound of

                  100*[sqrt(10^9) + (2*10^5)], which is good.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Nice explanation, thanks

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    That is the idea I used. The first thing to note is that the answer is either 0 or 1, because gcd(lcm(a,b), lcm(b,c)) > 1 for a,b,c>1.

    Now, if n has only one prime factor then the problem is easy. Otherwise, suppose the prime factors of n are p_1, p_2, ..., p_k.

    Write n, then write all factors of n that are divisible by p_1, but keep p_1*p_2 for the end. Then, write all factors of n divisible by p_2 but not p_1, but keep p_2*p_3 for the end. Keep doing this.

    For example, if n = 60, we can do

    60,2,4,10,12,20,30,6,3,15,5

    where 60 is written first, followed by multiples of 2 with 2*3 = 6 written in the end, followed by multiples of 3 that are not multiples of 2 but keeping 3*5 = 15 in the end, followed by multiples of 5 that are not multiples of 2 and 3.

    The only case where an issue occurs is when n=p*q for distinct primes p,q.

    So the answer is 0 for n not of the form pq for distinct primes pq, and 1 otherwise.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I don't understand why I fkd up D1 ;'(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    what was your approach?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I thought of putting smaller numbers first in alternate places then the remaining in the places left in case reordering is required. like if n=6 and arr[]=1 2 3 4 5 6 so answer is 2 and order is 4 1 5 2 6 3 if n=5 and arr[]=1 2 3 4 5 so ans=2 and order is 3 1 4 2 5 I still couldn't find anycase giving maximum answer other than this.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I hope you printed a[i], and not i. That is what I did the first time :P

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I just saw your sol; where did you sort the array?

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Enjoyed the problemset. Kept me challenged till the last minute. Thank you!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

deleted

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    If you look closely a stair is valid only when the height of the longest staircase is 2^x - 1, x >= 1

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      how do you even prove it? forget that how to even verify it ? it is inhumane to expect us to draw 15 staircase

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        deleted

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        True that! Very inhuman of me!!!!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I did till 7. next in line had only two possibily 13 or 15 just tried the general terms of both the cases. They made me draw it :(

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        Adding a proof to (B):

        Proving that 2^x-1 works is obvious: note that there is a big 2^(x-1) times 2^(x-1) square with one corner on the lower right; use this, and now we are left with two smaller stairs of parameter 2^(x-1)-1.

        Now suppose n is not of the form 2^x-1 and n is nice. Note that the minimum number of squares needed to cover the stairs with parameter n is at least n, because no two of the top-most cells of the n steps can belong to the same square. Therefore, each square in the decomposition of this stair should cover one top-cell in some stair. Furthermore, note that the bottom right cell and a top-most cell of any step do not belong to a common square except if n is odd, in which case bottom-most cell and the top-most cell of the middle step can belong to the same square. But this square splits the stairs into two stairs of parameter (n-1)/2. Now induct, and we are done.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I really don't get it, can you please explain what is big ? " Moreover, if n is not of the form 2^x-1, then the bottom right cell and a top-most cell of any step do not belong to a common square. " did you mean bottom left cell and why should it be of the form 2^x -1 to fulfill that?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Okay, so each unit square is a cell. Each column is a stair. A square is a union of cells that makes a square shape, as shown in the problem.

          Consider a staircase with n steps. We want to partition the n*(n+1)/2 cells into squares. Let f(n) be the least number of squares required to do so. Consider the topmost cell of each stair; there are n of them . Note that no two of these topmost cells can belong to a common square. Therefore, the answer f(n) is at least n, for all n.

          Suppose the answer is exactly n. Then, the n squares that partition the staircase must cover the topmost cells of each stair; you cannot have a square that misses all topmost cells of all stairs, otherwise we will need > n squares.

          Now, consider the bottom right cell. The square that covers this must also cover the topmost cell of some stair. For even n, this is impossible. For odd n, this is possible only when you take a square that covers the topmost cell of the middle stair and the bottom right cell of the staircase. But upon taking this square, we are left with 2 staircases of sizes (n-1)/2 each. This means

          f(n) = n => f((n-1)/2) = n-1/2. Thus n is nice implies n is odd and (n-1)/2 is nice. From this, you can conclude that n is of the form 2^x-1 for some x.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Thanks but I don't get this
            " Now, consider the bottom right cell. The square that covers this must also cover the topmost cell of some stair " why so ?

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Every square must cover some topmost cell of a stair. Also, no square can cover two different topmost cells.

              So if you want n squares to cover the staircase, it MUST be the case that EACH of the n squares in the decomposition of the staircase covers the topmost cell of some stair. Simply consider the one which also covers the bottom right cell.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            this is elegant

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    u need to figure out the pattern of a nice stair.

    Spoiler
»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

B was more difficult than C +D combined for me, how do you even solve it?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It took me time to realize "What is a nice stair?"

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    may be observation(in my case) . pow(2,i)-1 is the key.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Pure Adhoc bud..

    The valid nice patterns are of sequence 1,3,7,15 .... (1 << n) — 1 for the general term. Just brute force out each value until u have the blocks left. Since the no of blocks required are sigma(n) a n nice staircase hence the values in this sequence grow exponentially. Just didnt like the set today :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for me it was easy . basically what i did is tried every n from 1 to 11. i saw that the answers were 1 3 7 which is basically just multiply with 2 then increase by 1. so i just run a loop until x is small for the next 2 * i + 1.

    code
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Think like this:

    First you have a $$$1 X 1$$$ square only and it is the first nice stair.

    So, you have a nice stair of size $$$1$$$.

    Now, add a $$$2 X 2$$$ square at the bottom and a nice stair of size 1 at its left. Then you get the 2nd nice stair.

    So, you have a nice stair of size $$$3$$$.

    Now, add a $$$4 X 4$$$ square at the bottom and a nice stair of size 3 at its left, and you get the 3rd nice stair.

    So, you have a nice stair of size $$$7$$$.

    and so on...

    Notice that, at each step, the size of the nice stair is $$$2 \times previousSize + 1$$$.

    So, you get a $$$2^n - 1$$$ sized nice stair after n such iterations.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I personally felt that this contest was more about getting the idea and passing the corner test cases. The questions were not in order. D1 was easy. In A, you could just check for the last digit depending on parity of it. For b, it was 1 formula (with a testcase gone wrong which I still haven't figured out). In C, a hit logic (with corner case where you have at least 1 of x in your set of 1-n). In D1, just print the nos like n, 1, n-1, 2,...(you get the idea).

Basically, all the questions could be done in a max of 4-5 lines. No data structure/ implementation knowledge was tested. the questions were good and interesting. But more so as a puzzle and not as a coding contest. Having 1 or at max 2 ques like that is okay. But if all questions are like that, the problem setters need to take a note of this.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

only after system testing can you test right ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please someone check my code for F, i have no idea whats the problem with the code, here is my submission it would be so good if you check my solution : ) https://codeforces.net/contest/1419/submission/93269063

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wtf was b

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My brute force idea for E was working in 3 seconds for number of factors=700. Any idea to optimize it to pass under 1s TL or a more elegant solution?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I have a simple idea:

    Say we organize numbers(except N) in blocks of their spf, first number of each block is the prime, pi, followed by it's divisors where it is the spf, and the last number of each block is always pi*(pi+1), and for the number with no next block, we put N. We get answer as 0 here. And we only get 1 boundary case where a number is of the form p1*p2 where answer is always 1.

    PS : consider primes in increasing order of values

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do the ratings change in this testcase for problem C?

2 3
3 4
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1 step only,

    change rating +1 for first guy and -1 for second guy.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    We can change it to

    4 3 and the answer will be 1. Note that the first one is already affected , so we can change the rating of second and make it infected

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    As 3 is already infected we can use this to change 4,

    to change 4 to 3(x) we need -1 and to compensate we add 1 to 3(A[0]), rating change will be {1,-1} therefore we required only 1 step (Answer).

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

wtf was b

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can any one why my solution for F is not working!? here is my submission it mean a lot if you find its bug : ) https://codeforces.net/contest/1419/submission/93269063

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For E, I iterated over the smallest prime divisor, printed all the divisors of n that are a multiple of it from largest to smallest (besides n), and then printed n. Then, I divided n by the smallest prime divisor and recursed for each successive prime. This guaranteed that all adjacent elements weren't coprime, and I think maybe that the first and last elements aren't coprime (but I got WA). Can someone point out an n where this strategy doesn't work? All the ones I've tried work

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can anyone tell me why I was having TLE in problem D2 ?

My submission: https://codeforces.net/contest/1419/submission/93268164

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    You wrote i<=v1.size()-2, where v1.size() is size_t type(like unsigned int). If n = 1, v1.size()-2 is -1, but because it is unsigned type, (-1) % (unsigned mod) = (unsigned mod-1), which is very big(around 2e9). So you increase i by 1, while i < 2e9. This is TLE.

    P.S. To avoid this, you can simply write something like this: i + 2 <= v1.size()

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    check: 1 1

    v1.size() returns unsigned integer. hence v1.size()-2 becomes 4294967295.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +49 Проголосовать: не нравится

All the questions could be done in 4-5 lines. No data structure/ implementation knowledge was tested. There were essentially two pretests for B-D, you passed one if you got the idea, and failed the other (they made those specific cases where you would fail, like for C, count of x >=1 in the set will give contest max 1 ans, you would print 2).

My point is, having 1-2 questions like these don't hurt. But when all the questions feel like this, something's wrong. In a div2 contest, we need more of algorithm/ data structure based questions, not the puzzle types. And because of the puzzle nature, the difficulty order of the questions did not correspond to the number of solves. I would request the future problem setters to please take a note of this.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Quality of problems has been deteriorating rapidly here.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was hoping one graph problem among C — E, but there was none, instead it was a puzzle game as OP said.

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

D1 < A < B < C = D <<< E << F

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Took me so long to understand C right...

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I don't get how D1 and D2 were different. I barely made any changes to pass D2 after D1

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Exactly lol. After B I solved D1 in 10 mins and since it was too easy i thought it wouldn't work for D2 and went to C. After C when I thought more about D2 I realized all i had to do was calculate answer seperately

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

At first, I was surprised to see the submissions to problem D2 and C1 rising rapidly, this actually makes you panic when you have not solved the problem. But later I felt like someone fooled me. The problems were damn easy. Short statements strong pretests.

»
4 года назад, # |
  Проголосовать: нравится +89 Проголосовать: не нравится

I couldn't understand A and B's English.It seems that I need to study English, not algorithms ...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Screenshot_20200729_205651_com.whatsapp2c900f4644ea10e17.jpg

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

What Problem B actually say

i read it many times but cannot understand that

Can any one say me what they actually want

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can we solve B without searching on oeis. :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Draw out the stair cases. I did till 7 (1,4,7 were only possible) so next in line would be 13 or 15 just check for both the cases which one matches

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yes, look at how height of stairs is changing.

    starts with 1, and then height = (height * 2) + 1

    and they gave us the higher limit of this in sample. look at my submission for more help.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    I did. My approach — First I observed the pattern, nice numbers are 1, 3, 7, 15 ..
    this is enough to come up with formula f(i) = 2*f(i — 1) + 1. Also, if you observe how nice stairs are made, if number x is nice then you need to combine two stairs of type x with a middle square of length (x + 1) resulting in a nice stair of length 2*x + 1. Rest is simple greedy approach.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Wasted a lot of time in question B, Unable to get the Statement specially "n disjoint" but finally solved it.

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Problem $$$A$$$: Digit FST Games

Goodbye, master~

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C: 4 38 -21 83 50 -59 can anyone just EXPLAIN me how answer is 2?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    See if a rating is infected then basically you don't care about it afterwards. So use it to make every other rating to infected.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      suppose I make A[0] infected, then how he will infected others ??

      in the statement, they said all changed need to be 0. then I need to decrease/Increase the same amount of rating from another one.

      can you please explain to me how it's happening? how he will infect others if I infected only one.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        So A[0] is infected, now make all non-infected rating equal to A[0]. For this, you have to increase or decrease other ratings. Calculate the net change and subtract that value from A[0], that's all, other ratings are also infected. See we can do this because A[0] is already infected, and it is mentioned in the problem statement that once a rating is infected, it will remain infected forever, So we change A[0] to any value to satisfy the other condition that, some of all changes in ratings after a contest should be zero. If you still didn't get it I can explain with an example.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    First contest ratings are [38, 38, 38, whatever] so you infect 3 people. And in second contest last person is infected.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how it become -21 = 38, 83 = 38, 50=38 ??

      all rating changes must be equal to zero???

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The total of 4 people ratings [-21, 83, 50, -59] should stay the same yes. -21 + 83 + 50 + -59 = 53 so after the first contest ratings will be [38, 38, 38, X] and 38 + 38 + 38 + X = 53. So X is -61. [-21, 83, 50, -59] became [38, 38, 38, -61] after first contest.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    more simply you can get all ratings to x except for the last guy, and compensate it all on the last guy to make whole difference 0. and then do last guy, make him compete with any one and make last guy infected as he is the only one remaining. that is case for 2, (only 2 operations needed).

    if the last guy == x, he was already infected, that is case for 1 (only one operation needed) else 2.

    more formally

    all elements == x: output 0

    if (count x in array > 0 || sum == x) output 1

    else 2

»
4 года назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

Test Case 68 on A was nasty.

Also, there wasn't enough of a distinction between D1 and D2. They were both just basically greedy brute forces. I solved D1 without even looking at D2, and I then solved D2 by changing 1 line.

Overall, this was a bad round.

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

I did left the contest early because of bad statements A+B.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    True. Read B like 4-5 times and finally did what i could understand from the explanation.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Thank you for your effort.

(750 + 1000) for D1 + D2, but each one of them is actually easier than B. In the previous contests, it is used to be counted as: if you solved D1 you deserve 750, then solving D2 gives you the complete degree because you solved the difficulty that deserve 1750. But today, you can get 1750 by solving two problems, each of them is easier than the problem that deserve 750 in this contest.

In other words, my mind used to think of D2 as 1750 not as 1000 or lower.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Please downvote this round!

List of problems

-A was badly written (all these FSTs on test case 68!)

-Distinction between D1 and D2 was insignificant, they were both just stupid greedies. Many people solved D1 and almost copy pasted their code into D2.

-No data structure/algorithms involved at all: just greedies!!

-Terrible scoring. Why was the scoring on E so high??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    C'mon bro, appreciate the work of the authors, testers and whoever has contributed to the round. Not every round might be to your liking, isn't it? But yes, I see that pretests for A were badly designed :(

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

To be honest, D1 and D2 were much easier than even A. I didn't even look at D2. Just matched the test cases and submitted for both D1 and D2 and pretests passed without even changing a line.

»
4 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Sad round... The description of B and C confused me a lot. The difficult of these problems is how to understand what author mean rather than algorithm.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Lots of people failing system tests on question A , test 61 and 68 mainly. Also, ordering of questions weren't that good. I do appreciate the efforts of the authors ,and testers, but many of us are kind of not satisfied.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just a suggestion. Please next time make tight pretests. It really feels bad when you have think you have solved but after the contest you know that your problem A fails.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

test 61 for A is awesome

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Problem B is hard to understand to me that I waste a lot of time :(

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Problem d is obviously easier than usual d. I thought D2 would be much more difficult than D1, but they’re actually the same.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

B ruined the contest for me, I am not sure about the proof for a "nice staricase", but the proof is definitely not DIV2 level, and even the observation is not that intuitive for a "nice staircase" since there are only 3 samples (1,3,7) and it is inhumane to expect us to draw 15 staircase.

And IMO A+C+D1+D2 was much easier than B,A and C were good,D2 was too easy, was not able to even look at E, thanks to B

»
4 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

Today's contest in nutshell:

Untitled.png

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Totally unbalanced contest, i thought of doing D first so that i can relax and do A, B and C afterwards, turns out i did A first.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    B should be closer to C, and D2 should have been lower than D1. there is no difference. rest is okay.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

This is the first time I have failed System Tests, that too on Problem A. Anybody knows why so many System Fails on A?
EDIT : Weak Pretests and a simple typo made you fail System tests.
Also D2 was greedy? Why? I was thinking greedy only worked for D1 and didn't even give it a thought on D2. A really bad/easy D problem for Div. 2. Only problem I liked was C.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Nowadays Problems Setters are emphasizing more on Problem statements rather than Problems.

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +14 Проголосовать: не нравится

Adding a proof to B:

Each unit square is a cell. Each column is a stair. A square is a union of cells that makes a square shape, as shown in the problem.

Consider a staircase with n steps. We want to partition the n*(n+1)/2 cells into squares. Let f(n) be the least number of squares required to do so. Consider the topmost cell of each stair; there are n of them . Note that no two of these topmost cells can belong to a common square. Therefore, the answer f(n) is at least n, for all n.

Suppose f(n) = n for some n > 1. Then, the n squares that partition the staircase must cover the topmost cells of each stair; you cannot have a square that misses all topmost cells of all stairs, otherwise we will need > n squares.

Now, consider the bottom right cell. The square that covers this must also cover the topmost cell of some stair. For even n, this is impossible. For odd n, this is possible only when you take a square that covers the topmost cell of the middle stair and the bottom right cell of the staircase. But upon taking this square, we are left with 2 staircases of sizes (n-1)/2 each. This means

f(n) = n => f((n-1)/2) = n-1/2. Thus n is nice implies n is odd and (n-1)/2 is nice. From this, you can conclude that n is of the form 2^x-1 for some x.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I've checked for the even position for the second person and got WA at 68. This is silly that this case isn't in Pretest. What a shame! It must be in the Pretest. What's going on in Codeforces! Shame!

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Did you have some kind of intention to prepare such a large number of system test cases for problem A?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What a strange contest. D1 and D2 combined were worth 1750, but most people think that D was easier than B and C. Surely the contest writers knew that 5 ad hoc problems is quite unusual.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Such a disgusting round. Nothing to learn, no use of dsa/algo, unclear statements, weak pretests, poor choice of problems, misleading score distribution, __

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Stop writing CF rounds!. :)

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +20 Проголосовать: не нравится
A
B
C
D
E
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for D,

    look at sample cases and do exactly.
    take two pointers i and j
    initialize i = 0, j = (n / 2)
    now alternatively add them to another vector.
    check answer count.
    print it.
    AC.
    
    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      For D2

      Sort the input and split into 2 parts — low with N/2 elements and high with (N+1)/2 elements. Put to the answer the first element from high. In a cycle try to put the element from low followed by the element from high (put it if it's smaller than the previous element in the answer), otherwise put one element from the high. Once you have no elements in one of the parts, break the cycle and dump the rest to the answer.

      93231855

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I failed at D2 and I don't know why? Can you check my code?

93223419

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I failed at D2 and don't know why. Can you check my code?

93223419

»
4 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Nice round awesome pretests

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

weak pretest

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

While I pretty much agree with complains about the problems

I just don't see what was so difficult about the definition of "nice staircases" everybody mention

"A staircase with n stairs is called nice, if it may be covered by n disjoint squares"

Just what can be misunderstood here?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Misunderstandable are: How much stairs a staircase has? What counts as a square? What exactly is meant by disjoint?

    Of course, once understood what the writer intended to say it is clear.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      "If a staircase has n stairs, then it is made of n columns, the first column is 1 cell high, the second column is 2 cells high, …, the n-th column if n cells high"

      Extremely clear

      It is probably possible to argue about the definitions of a square and disjoint. But I just don't see how else the problem can be interpreted.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, in this case I did not misunderstand the statement at some important detail or the like. I simply did not understand it at all.

        The main detail I missed was that the number of stairs is the number of cells in the diagonal in the surrounding square. Because of this I was not aware that the number of squares (the colored ones in the picture) is equal to the number of stairs.

        Reasons for not getting the idea was maybe the usage of the words stairs and staircase, which where pretty meaningless to me, just two similar sounding words. In that case a somewhat more formal defintion would have helped.

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

In problem B the colors of squares of sample was showing the solution.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Am I the only one who solved D2 like D1

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Currently I am the only one who failed test case 16 on C FST!

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

bad contest With weak pretests

»
4 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

This is the first time I have solved 5 questions in div2. Because I was ill today and had a bad cold and fever, I thought about it and decided to register a new id to participate in div2 tonight to avoid losing rating. But the result of this is that my main id lost an opportunity to record a memorable milestone. (My main id used to solve 5 problems on codeforces, but that was in div3). God knows when I will solve 5 problems on div2 next time. (If you know my main id, don't say it, thank you.) I hope I can have good luck next time, and good luck to everyone.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    I disagree with ur idea of giving contest with a new account. I think if you perform bad in any contest then you would easily regain in the future rounds. Just to have a better graph of rating should not be a reason to make new account.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think you deserved it, there is no reason for anyone to have an alt account in my opinion, let this be a lesson and try to overcome your fear of contest and rating changes.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

so many system test failed ...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really thankful for the first test case of problem C. I think many would have got wrong answer, if this case was not in the sample test case.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Weak Pretest for A & D2. :)

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

What if the problem F is easier than now?

The number of solutions for E is much more than that for F although the number of solutions for D if far much more than that for E.

Maybe make D more difficult and make F easier will provide a better experience.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I suppose there is something I haven't got about how contests work. I saw a green "tests passed" in problem D2 during the contest and now I see an error in test 67... How can it be?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E is an old USAMO (a math contest) problem

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

I didn't submit D2. But my D1 solution was the D2 solution too.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Weak pretest in problem A and D2.Same problem again and again...

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

Useless nasty pretests in A & D2.

They decided just not to cover the last testcase of D2 in pretests which could've made a difference for many people.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    I made such a big mistake in A (mixing the odd and the even indices) and my solution amazingly passed all pretests!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      the pretests of C is the same !

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Luckily I didn't do any mistake in A. But pretests should cover these kinds of obvious errors unless someone intends to mess with the contestants.

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I hope the statements were clear and short

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

one of best contest ever :)

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hey @shishin,

I got flagged for copying with some random guy I have never heard of in my life for Div 2 C. I think it may be because of the brevity of my code:

for _ in range(int(input())):
    n,x = map(int,input().split())
    l = list(map(int,input().split()))
    if all(i == x for i in l):
        print(0)
    elif sum(l) == n*x or x in l:
        print(1)
    else:
        print(2) 

Can I please get unflagged? (I was using a private IDE as well btw)

Thanks.

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Finally become purple thanks for the contest

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

I suppose the difficulty of each question in the contest is similar to the picture below.

I think most participants think the problem A and D2 are a little annoying because they are easy to FST.

Wish that all the participants can FST less!

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

May I ask a (maybe naive) question?

Users like dzh_loves_mjy whose rating is less than 2099 are not rated. Why is it?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I suppose it's possible that the person was discovered to be cheating, or an alternate account? I'm not sure what the policy is now, though I think if it was cheating the account would be banned.

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Just for fun :

Problem A.

my hack was last hack during contest (test 83 last test of systests).

Spoiler

and (> 50) solutions fail on that test in systests.

Spoiler
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, Iam practising from a long time on codechef and hackerrank but iam not able to solve problems what should I do.??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just try to get out of your comfort zone and try solving problems that you are unable to do in the first go. Think hard on such problems. Do this for a few days. Apart from that try virtual contests as well.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain me what to do in Problem A? Its really confusing for me :(.

It says Raze can mark digits from odd positions and Breach can mark digits from even positions. Find who cant cross the last digit if Raze starts. Can anyone explain what am i missing. Thanks!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Raze and Breach mark digits in odd and even positions respectively. They stop when there is only one left. The question is to find whether this last unmarked digit is even(Breach wins) or odd(raze wins).Since both players play optimally, suppose there are more digits on odd places (Raze has high ground) and there is an odd digit in one of those places, he marks the rest of the digits and the odd digit is left and he wins.

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Why so less upvotes ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Me before the contest: Jokes over, you're dead Me after the contest: Need healing, Jett revive me Jett