shishin's blog

By shishin, history, 5 weeks ago, translation, In English

Hello, Codeforces!

Artyom123, Kotehok3 and I are happy to invite you to Codeforces Round #671 (Div. 2), which will be held on Sep/19/2020 17:35 (Moscow time). This round will be rated for all participants, whose rating is lower than 2100 (We really hope so).

We would like to thank:

You will be given 6 problems and 2 hours to solve them (or to play Valorant, because the contest is related to it for some reason). One problem has an easy version and a hard version.

You will have to help the agents from the game to grind that rating. Try your best as if you are playing ranked and they are your teammates!

gl hf

Here is the score distribution:

5007501250(750 + 1000)22503000

UPD: Editorial

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

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

I hope that statements are short with strong pretests.

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

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

:(

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

    He tries to tell that if it get unrated like the previous round then no rating change

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

You must remember — peaker has an advantage!

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

The first 6 problem round in such a long time!

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

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

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

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

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

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

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

    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.

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

    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.com/blog/entry/59431#comment-430573

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

      I always forget that people get some score for hacks... Yeah, it does sound bad

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

    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)

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

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

      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.

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

        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, shishin 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.

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

      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

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

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

        Everybody is in equal position

        as you've suggested.

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

    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.

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

Pretty much excited :-D

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

VALORANT!!!!!!

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

Clashes with ioi (

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

Gamers joining Codeforces because of Valorant .

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

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?

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

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

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

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

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

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

I can assure you. ;-)

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

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

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

    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.

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

      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

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

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

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

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

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

            Well the no of accepted solutions also depends on several other factors . Like last time the round went unrated and very few people solved the problems than they would have in normal. Other factors include whether the contest is Div 1,2 or 3.

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

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

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

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

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

        got adhocforces instead

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

          For me it was readingforces. I had to read C again and again until enlightenment

          Btw the contest was a good example of lying score distribution.

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

            Click That's why short and clear statements are always good.

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

              It certainly affected my rating, but I don't think the round was bad because of that. It was for quite different reasons though.

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

Hoping to become expert in this contest.

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

Hey guys i have 20cm cock, wanna twerk? Ladys suck my dhildho

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

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

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

    I guess It hasn't happened this time either. Looks like you'll have to wait more

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

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

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

A very unique and interesting rating graph shishin xD

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

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

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

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

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

Participants after knowing that A is also not easy:

jett.jpg

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

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

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

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

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

I'm waiting for this contest. _

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

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

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

CS:GO themed contest when? :p

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

Subtasks! After a really long time.

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

    but those subtasks were not really subtasks, it was a joke just change 1 line of code and hard version is solved

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

Super excited :D

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

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?

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

intresting.

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

bol fy fca.

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

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

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

    Mumbai Indians

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

    Super Kings

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

    It's your local game, no one outside India watches it, so please never post it here.

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

      Are you sure that no one outside India watches it, if you doesn't watch it?

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

        Even if you post something like champion league or world cup. You will still get downvote because its not related to the blog. And not everyone interested with football

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

      I agree this wasn't exactly the right place to post a pic about IPL, but yeah, IPL isn't limited to Indians only. Even you are most welcome to watch it, in case you don't have other engagements and are simply looking for something entertaining! :)

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

      Its wrong to put it in those words, even though he should not have posted it here

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

    IPL succ!

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

As a novice I always thought, that when the comment has been downrated it has exactly disrespectful words or smth like that, but now I wonder who is just clicking downwote always

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

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

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

Sorry IPL, Not today.

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

Indians be like : Contest or IPL. XD

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

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

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

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

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

      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

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

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

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

Who else is just waiting rn for contest to start?

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

    As an author, I`m waiting rn for the contest to start too.

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

      Great, I am sure its going to be fun and exciting :)

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

I think Gamers are joining Codeforces because of Valorant :P

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

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.

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

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

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

    forget the past, lets live the present :D

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

as a tester you will enjoy this round

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

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

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

Wishing everyone higher rating

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

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

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

i didn't participate but i think this contest could be greater if the problem statement in A & B was better than this

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

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

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

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

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

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

Approach for C??

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

    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.

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

      ohh shit i didnt check if x is in a thing otherwise same logic. :/

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

    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.

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

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.

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

    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.

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

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

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

        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.

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

This was basically speedforces

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

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.

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

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

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

    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

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

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

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

      You should for only n squares

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

      because we have to use n numbers of squares.

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

      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.

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

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

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

      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.

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

        sirearsh hmmm...nice observation. From editorial : "the minimal amount of squares needed to cover the staircase is not less than n, where n is the height of a staircase."

        so if you try to cover any constraints, (count, or making cell of square as staircase), you are actually covering other itself.

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

For problem C when can the answer be 1 ??

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

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

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

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

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

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

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

    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)

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

      Why is it not 2 in test case 3 2 1 1 2 so before the round 1 the 3rd account is infected but how can every account be infected in 1 round?

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

    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.

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

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

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

    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?

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

      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

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

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!

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

    Brute force will TLE

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

      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!

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

        Your approach will definitely get TLE

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

        Do some paperwork you will understand how

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

          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!

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

            what you are doing now basically is sieve of 1e9

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

              The approach will not TLE.

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

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

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

                  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.

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

                  Nice explanation, thanks

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

    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.

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

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

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

    what was your approach?

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

      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.

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

        I think, you did right. I did the same and it passed both D1 and D2. Sort the list. Put first n/2 elements in one vector and last n/2 in another. Now print alternatively.

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

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

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

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

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

      I didn't sort , just printed alternatively straight away. Is this wrong?

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

        Yeah, I don't get why that would give you the optimal solution.

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

      I did the same,I sorted the array and then took one answer arrray and kept filling it (one big one small),so that the pattern is bsbsbsbs

      b:-big

      s:-small

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

        so is your solution right? then why is my failing ?

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

          It is still in pending queue.

          You can check submission.

          username:-namanbhardwaj.official submission:-93254332

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

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

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

How to solve B

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

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

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

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

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

        same

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

        I did it out using OEIS :p but there was no time left

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

        True that! Very inhuman of me!!!!

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

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

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

        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.

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

          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?

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

          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.

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

            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 ?

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

              If it doesn't, then you still need at least n squares to cover the topmost cells.

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

              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.

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

            this is elegant

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

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

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

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

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

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

    same...

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

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

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

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

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

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

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

        I can at least say that no even number can form a nice stair. I hope I'm right

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

          No every non-even number can't form a nice stair

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

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

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

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

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

    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
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

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

      lol, I think you are just describing the diagram mentioned in the problem, how to prove that squares of 3X3 5X5 aren't important?

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

Hi, This was my first contest. And I was able to solve only 1 problem and it passed the pretest. Will I get any ratings? My rating is zero as of now!

Thanks and regards.

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

only after system testing can you test right ?

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

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?

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

    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

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

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

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

    1 step only,

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

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

    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

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

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

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

wtf was b

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

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

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

    its basically just 1 + 3 + 7 + 15 + 31 + .... its the problem statement that confusing..

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

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.com/contest/1419/submission/93269063

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

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

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

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

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

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

    check: 1 1

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

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

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.

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

    Quality of problems has been deteriorating rapidly here.

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

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

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

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

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

    the order of your submission, lol

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

    Lol I think this order- D1=D2<A<B<C<<<<E<<F. D1 and D2 had were just 4-5 lines solution

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

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

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

Took me so long to understand C right...

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

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

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

      Read the statement again. They have explained it pretty clear.

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

      See the color coding in the diagram.There is 1 4x4 box, 2 2x2 box, 4 1x1 box.In totality there are 7 boxes which is equal to n.

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

Could anyone explain the proof of B ?

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

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

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

      If I am not wrong then nice stairs are the stairs with rows = 1,3,7,15... They are 'nice' because they can be constructed using 'square' shaped blocks. Also, it is quite logical to use large sized blocks for larger stairs.

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

    "nice" stairs means a stair consists only of N x N stair cells in this problem.
    If you look at the highest(rightmost) column of i-th "nice" stair set, it's 1, 3, 7, 15 , ... which is 2^i-1

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

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

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

    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

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

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.

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

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

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

Screenshot_20200729_205651_com.whatsapp2c900f4644ea10e17.jpg

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

What Problem B actually say

i read it many times but cannot understand that

Can any one say me what they actually want

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

    its basically just 1 + 3 + 7 + 15 + 31 + .......

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

      Actually i want to understand problems statement it's quiet unclear to me

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

        list of nice stair is 1, 3, 7, 15, 31, .. so on..
        how many different nice stair u can make with n cell you have..

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

      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 colour square will touch.....

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

can we solve B without searching on oeis. :)

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

    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

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

      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 colour square will touch.....

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

    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.

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

    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.

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

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

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

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

Goodbye, master~

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

    im feeling bad for ur C too.

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

    Sorry, but what is FST? Some kind of error?

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

      Answering to myself, it must be Failed System Testing...

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

      Failed System Test

      Solutions which were wrong but passed the pretests, will (almost always) receive FST.

      If you get FST on a task, you'll lose all scores on it.

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

        Yeah, I know. Couldn't figure out the abbreviation

        For some reason I thought it was something like

        Memory Limit Exceeded / Time Limit Exceeded and I search those among the error list

        Or

        StackOverflow / Integeroverflow

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

    looks like we tried same shit for D2 at first attempt lol.

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

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

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

    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.

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

      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.

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

        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.

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

          thanks brother, got it. i just didn't notice the "New ratings can be any integer", I thought rating is fixed for everyone. :( :( :(

          thanks again.

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

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

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

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

      all rating changes must be equal to zero???

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

        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.

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

      or I think I didn't get the problem correctly :(

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

    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

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

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.

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

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

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

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

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

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.

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