Codeforces Round 454 (and Technocup 2018 — Elimination Round 4)
By vintage_Vlad_Makeev, history, 7 years ago, translation, In English

Hi all!

This weekend, at 14:05 UTC on December 23rd we will hold Codeforces Round 454. It is based on problems of Technocup 2018 Elimination Round 4 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2018 website and take part in the Elimination Round.

I would like to thank veschii_nevstrui, adamant and DPR-pavlin who authored and prepared problems for Technocup and ifsmirnov, Kostroma, winger, AlexFetisov, 300iq for testing the round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

Congratulations to the winners!

Technocup:

  1. ---------

  2. I_love_Palindromic_Tree

  3. iakovlev.zakhar

  4. IsmagilS

  5. DCNick3

Div. 1:

  1. jqdai0815

  2. Radewoosh

  3. Swistakk

  4. Um_nik

  5. consecutivelimit

Div. 2:

  1. Kammola

  2. ehnryx

  3. LifeCracker

  4. emoairx

  5. laofudasuanbaofushehui

UPD: Editorial

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

Comments Comments (362)
| Write comment?
»
7 years ago, # |
  Vote: I like it +332 Vote: I do not like it

Mike during the contest ... "The round is declared semi-rated because no one thanked me for the platforms".

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    if codeforces had emojis like facebook's, i would give you "haha" instead of upvote

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

    Where does that semi-rated meme came from?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -63 Vote: I do not like it

      from your smart head, bro

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

      There was a 1/2 rated contest because queue.

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

    Sorry for off-topic but...
    why your nick is displayed in grey?

    Newbie Hasan with Contest rating: 1638?
    How is it possible?

    Is it just me? Or others are also seeing this?

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

      You can change your color from 1 Jan to 10 Jan ... see it in your profile, a tab called magic.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +72 Vote: I do not like it

Tomorrow we'll have 2 El Clasicos: -> Real Madrid — Barça * -> Codeforces — AtCoder *

→ Reply
»
7 years ago, # |
  Vote: I like it +114 Vote: I do not like it

I'm concerned about one thing... How many problems were made by adamant, you say?

→ Reply
»
7 years ago, # |
  Vote: I like it -27 Vote: I do not like it

It is rated.

→ Reply
»
7 years ago, # |
  Vote: I like it -95 Vote: I do not like it

Help Post, Why my solution was getting WA? Problem My Solution.

→ Reply
»
7 years ago, # |
← Rev. 6   Vote: I like it +8 Vote: I do not like it

Why does the tourist not attend?

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Hoping short problem statement

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

    Don't be racist bro.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

    I know that most probably I will not be able to solve D and higher in Div2, though I will try to solve.So if these problem statements will be huge I will never mind :D

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

    Maybe the translator translated the problem by its pronunciation, like translate names.

    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

High ratings to everybody! What a sad story...)

→ Reply
»
7 years ago, # |
  Vote: I like it +56 Vote: I do not like it

the truth is, i'm not getting out neither from the gray zone nor the friend zone -_-

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any scoring distribution?

→ Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

The English translation for problem A needs some work.

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

    I can assure you its wording in Russian isn't better as you would suppose.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why so long, man?

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This round is impossible, I can't understand half of the english.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +39 Vote: I do not like it

good job author !!!these nerds who are complaining about the tasks are just mad!!!

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

    Problems are interesting bro, but half of my time is used to understand the statements.

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

    Your original comment complains about tasks, and then when you realize that is a popular opinion you change it lmfao.

    → Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

reading the statements I feel like I must work on learning this type of English rather than coding ..really sucks!!

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

RIP for problem statement __________/_____________

→ Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

In problem 1, the statement is not clear. May be add another example or make the explanation clear. Bad English translation.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I never met a contest like this. Such a large code work???

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Comprehending the questions seems harder than solving them :/

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

English :p Your text to link here...

→ Reply
»
7 years ago, # |
  Vote: I like it +58 Vote: I do not like it

After reading problem A's statement, I'm not sure what I've actually learnt in 10+ years studying English...

Can't understand a thing.

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

    Please, clarify major mistakes in English in the problem A.

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

      I believe problem statement is enough clear for A. Though I haven't participated but read out the statement.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +54 Vote: I do not like it

      I was over-reacting a bit while commenting this. My apology (if it upsets you).

      In general, this problem statement is kind of... confusing.

      At first, as my expectation (like 95% of the Div2A problems I've come across), I go straight into the examples and criteria, and I was like "3 cars? wait then 4 variables... what is the last bear doing?"

      Then I looked up a little bit.

      Masha came to test these cars. She could climb into all cars, but she liked only the smallest car.

      "Alright, so the cars are there in a way that only the smallest one satisfy Masha, others either can't be climbed or Masha doesn't like them..."

      A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It's known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.

      Three similar sentences, consecutively. I don't know what others may think, but its repetitive state made my head almost freeze.

      A few thoughts clouded my head, such as "wait can papa bear climb on mama bear's car?", "can mama bear climb on papa's?", etc.

      This is not what most of us expect in the easiest problem for Div2. I know my point may be biased, but it's mostly intended to be solvable for almost everyone in quick succession, so one should not make the statement open up a whole possibility for confusion and needs for clarification like this.

      Then I made it to the conditions for liking/being able to climb a car:

      It's known that a character with size a can climb into some car with size b if and only if a ≤ b, he or she likes it if and only if he can climb into this car and 2a ≥ b.

      Took me about 3-4 more minutes to understand (at first glance it seemed like the two inequalities contradicted each other).

      To be fair, it was not some critical errors in spelling, or grammar. The problem lies in the expressions — to me (or at least it is me during bad mood, but I won't think other people share this coincidence with me) it is somewhat unnatural and it may jam contestants' comprehending speed.

      Lastly, thanks for directly responding to my comment. I was a bit astonished when seeing the notification.

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

        I also found this problem statement complex, I think many contestant did

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

        I've spent the same amount of time for reading Problem A statement and solving Problem C completely.

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

        I agree. I delayed more than 20 minutes to understand the statement and it is pretty simple. I don't know why exactly but It is made in a way it makes it hard to understand.

        Last week in usaco I didn't solve any problem but read and understand all of them in less than 10-20 minutes that was the time I delayed to read this problem in this case.

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

      Maybe the problem is that it's too clear xD

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Third pretest is not correct by the game rules because players cant make such moves (in the middle square) without touching middle positions of all squares, but the output of this pretest shows that the right code doesn't give a f*ck to such errors, so WHAT THIS TASK WANTS?

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

    Read the line about the hare. It doesn't matter if the current structure is possible or not, you just have to tell the next possible move

    → Reply
»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Is anyone else finding the problem statements a hell lot more confusing than normal CF rounds? :( :(

→ Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Please tutorial good some provide links to lean English :/

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

worst contest ever

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This contest should at least be semi-rated. RIP English!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My first Div.1 contest!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't even solve A :(

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

    masha as**** should not like fathers and mother car but like only child car.

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

This problem from a Korean judge seems quite similar to Div2F/Div1D, but the value of modulo in this problem is at most 106.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve C?

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

    dp[mask] = minimum number of steps to get clique consisting of vertices in mask.

    Now iterate through each member of mask (provided mask is reachable state) and try to get him to the next step. It is profitable only if vertex has some neighbour outside of mask — it also means that he could have not been selected yet.

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

      I had the same idea, but how to prove it's always optimal to chose an adjacent vertex of the clique at each step?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 4   Vote: I like it +5 Vote: I do not like it

        You choose any of the vertices already in mask and you compare dp[mask + neighbours] with dp[mask]+1.

        In every optimal solution for mask, one of it's vertices had to have been chosen as the last one. We take the optimal vertex and it's neighbours out and the state for the remaining subset is already optimal.

        Edit: You can't select a vertex wchich have set of neighbours (and itself) disjoint with the rest, as it could not construct a clique. dp[mask] is the minimum number of steps to make masks a clique. If you select some 2 disjoint sets there is no way of connecting them, so mask will not be a clique, hence you always have to choose a vertex which is part of the existing clique.

        → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 5   Vote: I like it +15 Vote: I do not like it

    C can be solved in O(2n * n) with brute force. There is no need for DP. We can use the following observations to test whether a subset S of chosen vertices is valid:

    • The order of choosing vertices in S doesn't matter.
    • S is valid iff for every pair (u, v) there is a path from u to v that uses only vertices in S as intermediate vertices.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Didn't notice that the order doesn't matter. Thanks.

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

      How to verify that path requirement in O(n)?

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

        I used BFS. Start from any vertex in S and only push new edges to the queue if the current vertex is in S. Then check if every vertex was visited.

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

          What if every person is friend to every other person ( Like when m = n * (n - 1) / 2 ) Then the answer is 0 and S will be empty.

          And can you please elaborate your algorithm? How will it run on graph like this : N = 5, M = 4

          Edges :

          1 — 2

          2 — 3

          3 — 4

          4 — 5

          Thanks.

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

            I had a separate check at the beginning of the program

            if(n==0 || m == (n*(n-1))/2) {
    cout << 0 << endl; return 0;
}

            For the your example case, it would look something like this:
            - While trying all subsets, we currently have S = {2, 3, 4}
            - Start BFS from 2, add 1 and 3 to queue
            - Visit 1
            - Visit 3, add 4 to queue (not 2 as it's already visited)
            - Visit 4, add 5 to queue
            - Visit 5
            - Now that the BFS is finished, check that all vertices are visited. They are, so update the best subset to be S.

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

              What if S = {2, 4}?

              Then you will be visiting all the nodes although 1 and 5 cannot be friends.

              Correct me if I have mistaken something.

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

                Steps would be as shown:
                - Visit 2, push 1 and 3
                - Visit 1, nothing pushed as it's not in S
                - Visit 3, nothing pushed as it's not in S
                Queue is now empty and not all nodes have been visited

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

          Why is it linear in nodes, not edges?

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

            Yes, BFS runs in O(V+E) == O(E), however this is still fits quite comfortably into the time limit, with my solution running in ~300ms. 33578496

            → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    it's so hard to see ur color...how did ppl make out u were askin div1/2 :P

    → Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I quit

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Seriously, what in the world is pretest #7 for C? I can't think of any corner cases...

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

    Did you unmark letters on ? operation?

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

      If I currently don't know the letter, and it gives me "? x", How will I know if he is shocked or not? I decided to make it the former and only then it passed pretests but I am not convinced that this is right.

      Lot's of ambiguity in this round.

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

        Statement said he only say correct letter at the end. So other '?' are shocked

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

        Because you're guaranteed to know the answer at the end only. It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action.

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

    if something like this occurs

    ". 25 unique characters"

    then you can find the required character.

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

      Yes I took care of that case. Or at least I tried to.

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

    If the query is of third type and it is not the last one, then the guess is wrong.
    So we need to eliminate that character too from the set of possible characters.

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

      I also considered that case :\ Maybe my implementation went wrong somewhere. Thanks.

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

      WTF like seriously he always guesses wrong -_-

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

        yes, until the last query.

        It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action.

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

        It's not that he always guesses wrong. It is only that if he guesses right, the game is over. So every guess before the last one will be wrong

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

    27 . a . b . c . d ... . y ! z ? z

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

    there is no edge case in it . just make two set one of which contain all the character that can't be hidden character and another contain all the possible values of hidden character.and at any time if size of possible values set become 1 or size of impossible set become 25 , then we can uniquely determine the hidden character.

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

      I was using two boolean arrays and simulating something like that, but perhaps it didn't work like I thought it did.

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

    some n

    . b

    ! ab

    .... ?a

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

    Did you initially believed all characters to be a possible special character candidates. Only those mentioned in the strings are possible candidates.

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

      yes initially i considered all char possible then at each time when a string comes with '!' then i remove all the char which are in only one of them (string and possible set ) and put them in impossible.

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

    I think it was when wrong letters are repeated in a word, or at least that was my case!

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B? (And if possible, please tell me how did you find that solution).

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

    I thought about looking at all permutations O(n!) for small values.
    For bigger tables there should be some way to distribute values that always works.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    I used chess coloring, then put all the white numbers to the left part of the table, and black to the right. Numbers with the same color obviosly aren't neighbors, so we just have to find n pairs of numbers with the different color, which aren't neighbors. For m > 4 that is easy ( for example, choose white numbers with j = 1 or 2, and black with j = m or m — 1). For m <= 4... some hardcoding.

    So, the point is, if I see problem about cells that aren't neighbors, I use chess coloring.

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

      Yup, I did the same thing, but I failed to account for the case of a tall and skinny matrix, because I was initially doing it row-by-row.

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

      From what I understand, suppose n =5 , m =5 ;

      so, white cells = {1, 3, 5, 7, 9, ...., 25}, and black cells = {2, 4, 6, ... , 24} ;

      Putting the white numbers to the left part of the table means, filling the matrix column by column, i.e. filling in this order -> {a[1][1] ,a[2][1],... , a[5][1], a[2][1], a[2][2],...), until we have exhausted all the whites.

      Have I understood it correctly?

      Where are you filling the black cells? Do you just fill them right where the white cells end? Also, what do you mean by this -> "so we just have to find n pairs of numbers with the different color, which aren't neighbors" ?

      Thanks.

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

        Yeap, i fill them right where the white cells end. But there is a problem: in a new table there is n neighbors (or n+1, depending on n and m) of numbers with the different color, so they could be neighbors in the first table, so we have to fill these cells so this numbers won't be neighbors in the first table.

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

          Got it. So, basically, when you were saying that we have to check n pairs of numbers, you were talking about the worst case scenario. Isn't it?

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

          One other doubt. Why do we need to hard code the solution for lower values of m and n.

          if (n *m == 1) { return "NO"; }

          else {

          We will do what you said above. If it is not possible to fill the array(i.e. we run out of possible black values to fill in the current matrix cell), we shall declare that there is no solution. Else, we have a solution.

          }

          Correct me, if I am wrong here.

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

    if n < 4 or m < 4, Just checked for 1000 random permutations, if the answer existed or not .

    For all other cases the answer will exist :

    I found the smallest prime which did not divide m(which will be among the first 10 primes) and started placing the numbers at this gap.

    Solution

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

      Any proof/intuition why that works?

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

        The intuition behind this was that if I am placing numbers at the gap which is a prime factor of m, I will get a smaller number around a smaller number. But I want it to be the other way round.

        Suppose n = 4 m = 6 Placing at gap 2 — >

        1.2.3.

        4.5.6.

        Placing at gap 3 — >

        1..2..

        3..4..

        As you can see, that numbers are appearing below each other. To avoid this the gap shouldn't be a factor of m.

        gap 5 — >

        1....2

        ....3.

        ...4..

        As you can see Numbers are not appearing below each other. But there's another case in which the gap may be a factor of n which is pointed below by Omar_Elawady. So we will place the number at a gap of the first prime which does not divide n*m.

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

      Fot the test "5 36", Your code prints 1 next to 37!

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

        Yes, you are right. I didn't think that through. The case you pointed out was that I haven't excluded the prime factors of n. In this case I am placing a numbers at a gap of 5, which is a prime factor of n.

        So instead of placing numbers at the gap of first prime which does not divide m, we will have to place the numbers at the the gap of the first prime which does not divide n*m.

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

Does randomize algorithm work in problem B (and maybe C)?

And what are the deterministic solutions for these problems?

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

    I got pretest passed with a random solution on problem B, but I do have a lot of pragmas. Without them it took at least 6 seconds in some cases. I tried to submit C but I had a bug in the implementation.

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

      Can you share some cases that your program need 6 seconds to run in problem B?

      Thanks a lot!

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 6   Vote: I like it +5 Vote: I do not like it

    I came up with the following deterministic solution: for n & m less than 3, the answers are hard coded, otherwise;

    - for general case, initialize the original grid then rotate even rows 2 positions to the right and even columns 1 position to the bottom.
    - Else if m <= 3, then rotate the even columns 2 positions to the bottom, and the even rows 1 position to the right.
    - For cases where m = 1 or n = 1, I did a special handling by rotating each 3 consecutive elements, with step = 2

    Unfortunately, I couldn't get it AC during contest, and this is harder than the randomized one.
    http://codeforces.me/contest/907/submission/33573025

    → Reply
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The gaming experience is very disappointing.

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I've decided to capture this historic moment. Never been so high in my life :)

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

    All the best for the sys tests :)

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

      Thank you!

      I see that there could be 2 possible pitfalls:
      1. Failed system tests
      2. Too many angry users that force the contest to be unrated ;)

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

        I don't think the contest should be unrated. Even worse(server issue) contests like previous ed #34 and 450 were rated.

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

        I feel your pain if it's the 2nd one :|

        But great job!!

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

    What's your solution to E btw?

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

      I've greedily added new vertices. If the vertex v introduces 10 new edges and vertex u introduces 9 new edges, I choose the vertex v instead of u.

      This solution doesn't work by the way ;)
      33565564

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

        oh wow! A greedy passed all pretests. Very weak pretests.

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

        I wrote a dp solution but unnecessarily resubmit. I had the following error — I initialized my dp state to be 1 for the mask consisting of the vertex and all of its neighbours.

        It is incorrect in case of isolated vertex and vertex with 1 neighbour — it should be 0 in this case as we don't add any new edges when we select such guy to the next step.

        However the case with 1 isolated vertex or an edge are special cases handled by if and the rest of dp seems to ignore such states in an optimal solution. Is there a test, where initialising such values to 1 instead of 0 could provide WA?

        Here is accepted submission.

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

    yeah ... at least you got the chance to get a AC on E pretests . good for you !! and keep it up

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

      Actually, I feel good about this systest failure, because there was nothing clever in my solution and it was just a leap of faith :)
      I'd have been sceptical about my rating otherwise ))

      → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Worst contest I have ever had :(

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Did anyone solve div1B/div2D using random? I was thinkin about it but didn't dare to code it.

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

    I submitted solution that uses random, but I had a bug in my code and got hacked. I think it should work.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I generated solutions for n<=8&m<=8 using random, and solved for other cases :)

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

    I did it without any if's

    repeat 10000 times:
  for every cell of the grid:
     choose a random not yet used number for this cell. If it can't be neighbours with number from cell above or on the left, choose a different number, and so on at most 10 times. If succeeded, move to the next cell. If not, try from the very beginning.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how do you ensure that this will pass in the given time limit?

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Horrible problem statements. The worst contest ever. I wonder how some people understood Div 2 A correctly and got it accepted in first attempt.

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

    the statement was correct, that's why.

    I believe almost noone likes problems like this but it is good to get people who do not read the statement properly and assume things just to be some minutes ahead (this works lots of times for div2A)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't get AC but my idea for div2 E was something like binary search on the ans, generate all combinations of size mid and check.

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

    My idea was to use bitmask of friends.

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

    Nice idea!

    Although this approach is correct but it should TLE in my opinion ( however, it does not ). I am quite skeptical about the time complexity of the approach. According to me, it should be O(2n * n2 * log(22)) where n2 is for checking if the generated subset is feasible and the log factor is obviously from binary search.

    Here is the AC code : http://codeforces.me/contest/907/submission/33579509

    Have I done anything wrong in my estimation of time complexity?

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

      The number of subsets of size k is not 2n, but . So even if you generated these subsets for all the possible sizes, your amortized time-complexity would still be . And because of the binary search, it becomes faster.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, key idea is query(l, r) = query(l, min(l + magic, r)).

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

    How to do Div2 E?

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

    Looks nice, but why so?

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

      In order to know what is you need to know what is and whether b ≥ φ(m). Iterating φ(m) pretty quickly becomes 1.

      → Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

D is bullshit

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

Problem A's english was very unclear. Masha needs to be able to ride all three cars but she has to dislike the first 2 cars and like the smallest car.

Problem B's english was awful. Though they gave me some clarifications in the end, but it was too late for me. After the clarification, I was like "This problem is nothing but the english killed it". This ain't the first time in CF that english has caused major upset in the contest. Please after this, let some normal (knows basic english) people view the statements before posting it for a live contest.

Sorry, but this contest sucked only because of poor english.

I found problem C interesting and passed the pretests but problem B made me suffer and could not complete it in time.

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

    Don't know the situation with problem B, but I have no idea what is it that everyone dislikes about A. To me it seems like the problem is not English, but the fact that it requires a bit more thinking than the usual div2 A. In fact, English in this problem is absolutely fine.

    Let's take a look at your complaint.

    Here's your wording: "Masha needs to be able to ride all three cars but she has to dislike the first 2 cars and like the smallest car."

    Here's problem statement: "She could climb into all cars, but she liked only the smallest car."

    What new information does your wording provide? Why is it better?

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

      Your problem statement says that Masha may not dislike those 2 cars. She does not like it and she does not dislike it. Yes, in some senses, you can say she likes only the smallest car which means she hates/dislikes rest of them. But it is not true always. It could be that she likes the smallest car and she doesn't like the rest ( not necessarily dislike those). This caused the ambiguity. If you ask other people they will say that they made their solution thinking that Masha has to like the smallest car and for the rest she may or may not like it. "She has to dislike the two big ones" is not mentioned explicitly.

      did you get it?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +7 Vote: I do not like it

        "he or she likes it if and only if he can climb into this car and 2a ≥ b."

        Pay attention to "if and only if" here. This means that when 2a >= b and a <= b, then she has to like it. And since it is written that she liked only the smallest one, it follows that the rest do not satisfy these constraints.

        If it's any consolation to you, the Russian statement uses exactly the same wording.

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

      I would rearrange the problem statement in the following way.

      First, define "climbing" and "liking" as in the problem, in order to give the problem statement a more logical ordering. (This isn't an English exclusive issue, this is an issue in the structure of the writing)

      Then, explain problem statement with first and second paragraphs.

      Second paragraph being in the past tense is very confusing, especially since what came before is in the present (Father bear can..., Mother bear can...).

      Rephrase it as: "Misha needs to be able to climb into all cars, but only like the smallest car. Given sizes of the bear and Misha, determine if finding a set of car sizes is possible. If it is, print them."

      I don't think the error in this problem was that it was intentionally misleading (certain problems do this very well). The problem statement was not misleading, but it was structured in such an illogical way that made it really confusing and tricky to understand.

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

How to solve Div1D?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Time limit for Div.1 C was pretty good, really fast n^2*2^n(just the OR(|) operations) did not pass. How to solve it in n*2^n?

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

    O(n) to check if each integer(representing each friend) has value 1<<n — 1. I think the order of making friends do not matter.

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

      yeah but to simulate new friendships you need to do M operation for each case. That's (n^2)*(2^n)

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

        I just ORed the current friend with all friends. That's the O(n). I mean... If the current friend is 2, and he's friends with 3,4,5 then OR 2's friendships on top of 3,4,5 person's friendships

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

    I had 2^n*n^2 lol. Try using bitset.

    → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I don't think those problem should appear in codeforces round(And problem A,B,C are all horrible problem statements), because we have only 2 hours to solve them.

Practice our idea instead of Reading comprehension plz.

Too large statement just make us feel awful.

→ Reply
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I think problem A div2 needs to highlight some points, such as how Masha dislikes the first 2 cars.

Of course it was my fault for not reading the statements clearly, but it should give more of a "competitive programming" rather than "competitive problem reading".

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to avoid MLE in E? I took a matrix of size int[1<<22][22].

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Worst descriptions ever; Ambiguity everywhere.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was there a way to solve div1B without case bashing? There seemed to be so many cases I needed to take into account (1,1), (3,3), (N, M <= 3), (N=2,M>3), (M=2,N>3), (N=2, M=3), (N=3, M=2), (N,M >= 3)

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

    try this. 4 cases: case 1: n > 3 || m>3 case 2 : n==3 && m==3 case 3 n==1 && m==1 case 4: none of above

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

      How would your algorithm handle the cases (6,2) and (2,6)?

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2/A :c

→ Reply
»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I have no interest in solving these problems.

→ Reply
»
7 years ago, # |
  Vote: I like it +180 Vote: I do not like it

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

    If you don't have good idea then solving this problem is an ugly process, but once you realize that it can be done by random then it is completely fine.

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

      I didn't know there is a random solution, all the ones I've seen are case bashes :P. While it's much better, it's still pretty ugly. What's the point of a problem where the solution is just hoping that random passes and implementing?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +12 Vote: I do not like it

        It's not that simple here. You need to have a good understanding whether random can pass or not. Here if I'm not mistaken probability that random permutation is fine is something like which is too small and trying random permutations will not give you AC. However number of bad pairs will be very small (~8), so you can get those bad guys and put them in random place and this process should end very quickly. In my opinion that's an interesting solution far from "let's write naive random and hope it passes".

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

          Yeah that's a very nice solution, thanks for explaining it :D

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

          Could you explain how to calculate these probability?

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

            There are ~m2n2 / 2 pairs of people in total and ~2mn are neighbours in every arrangement. For a particular pair of neighbours in new arrangement prob that they were not neighbours in previous arrangement is ~. Of course these events are not independent, but their independence is so little that prob that new arrangement is fine can be estimated as roughly

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

      It was a huge hint to see first two ACed solutions both working in 1.9 seconds :)

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

    You are a funny guy!

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

    Being libertarian? :D

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

    You only need to handle 3 case:

    • m > 4
    • n > 4
    • m, n ≤ 4

    The first two has deterministic solution, the last one can be done using randomization.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this round is Reading comprehension-Dead do(loop without any algorithms)

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

for problem A, i wanted to hack this solution 33555103, but i could not because contest ended. i think this solution will get TLE on this test case: 100 49 20 5, ironically it got AC on system test ???

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

    I tried your test case and it should've been a TLE.

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

    overflow haha, i didn't think about it

    → Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Shiiit this B and A

→ Reply
»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Thanks, for the fastest system test.

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

    there weren't that much of solutions to test and that is why it was fast,so you should thank for the shitty problems set

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

I kindly recommend that you should rename Codeforces "Readforces."

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    In comparison to other judges Codeforces has the simplest language.

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

      At least for this contest, I wonder it's the "simplest."

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This guy used multiple accounts. { ethereum, yerkimbekov }

Have a look MikeMirzayanov

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

In Div2 Question A In 6th pretest i.e [v1 v2 v3 v4]=[100 99 98 100] why is the answer -1 ? and why is [200,198,100] wrong answer?

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

    Well, it's wrong answer because Masha can't get into the son bear's car.

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

      But, the size of masha is 100, it can easily get into son bear's car according to the question. As, 100<=100

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

        Ohh...Sorry...

        Maybe, the answer is wrong because Masha likes not only the smallest car?

        100 * 2 >= 198.

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

          Yeah, you are right,

          The thing is masha only likes the smallest car.

          But, here it likes the second car and the first one too.

          Thank you for this.

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

    This is wrong because masha liked only the smallest car. But in your case, she also likes the medium and large car.

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

    Because the max size of mama bear's car is 198 and hence Masha will like mama bear's car. However, Masha can only like son bear's car. So answer is -1

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

    Masha also likes the cars of father and mother bear as 200<=200 and 198<=200. He only has to like the son's car.

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

    Oh My bad did not see only in the question.Thanks Guys

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me, please!

I really can't understand, what's wrong with my program.

It seems like only getting N is happening in test 2, Evolution() is doing nothing...

Help me, please, to find out what's wrong. 33571490

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Привет, Всеволод)

    NumbHits++ нужно делать не всегда, а только если он уже мог угадать

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      Рад тебя видеть!

      Но... Я ведь вывожу не NumbHits, a NumbHits — NumbNeed. Как только в массиве Litter[] остаётся ровно одна буква, я кладу NumbHits в NumbNeed и больше не меняю...

      Тут в другом проблема...Функция Evolution() на тесте 2 вообще не запускается. Если добавить вывод в её начало, на экране ничего не появляется.

      И массив себя на тесте 1 странно ведёт... В нём либо все ноли, либо все единицы.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Функция evolution() во втором тесте запускается прекрасно, но есть пара недочётов. Первый баг, который я поправил, чтобы пройти второй тест, состоит в том, что, когда чувак неправильно угадывает букву, ты просто увеличиваешь количество ударов, а надо этот символ прочитать (без сина идёт дальнейший сбой) и в массиве Litter обнулить. Сравни свою посылку и мою 33576279

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        Если тебе интересно, то вот 33576931 полностью исправленное решение

        → Reply
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Sometimes poor problem statement, sometimes bad problem-set, sometimes not maintaining expected difficulty of certain problems, sometimes 20 minutes long queue, unrated, semi-rated contests — Codeforces is frequently failing to maintain its quality contests.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

→ Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

rated . ?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my output is wrong? (Div2A)

input: 99 50 25 49

My Output: 99 99 49

Judge Output: 100 99 49

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Want to see some cheaters? Here are they: Edgration. and Anoxiacxy. Submissions for Div2 D: xlj's:33566367 and Zero_cxy's: 33564264. You can see that xlj replaced some parts of Zero_cxy like dfs -> asfkolasnhf, mt -> map_asfknas..., and Zero_cxy added a tree struct at the beginning but didn't use it to cheat. Those guys should be disquallified from this contest.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I think Codeforces server is having a few issues.

I've just received this announcement recently (one of my friends received it about 5 minutes before me).

In my opinion, this announcement must be presented long before, but for some reasons it won't pop-up in some users' browsers. Perhaps you should have a look.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

div2e

I don't understand why this output -testcase 1- is wrong?!

2 2 4

after 2 introduces all of his friends to each other, all of 1 , 2 , 3 , 5 become friends. Then choose node 4 so all nodes are friends. Someone help me understand this please.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    This is the initial graph (ignore the numbers outside of the circles, they were my drafts actually xD) After you choose guest 2, the link between 1 and 5 will be made. The similar applies to 3 and 5. (as 1, 3, 5 are guest 2's friends).

    When you choose guest 4 afterwards, since he only has 3 and 5 as his friends, and they are friended already, no more links will be made.

    2 and 4 are still not friended yet, so your solution is wrong.

    → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I was screwed up at the testcase n=1,m=1 (Div.2 D)

→ Reply
»
7 years ago, # |
  Vote: I like it -43 Vote: I do not like it

Worst Contest ever!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

now due to problem E, am trying to learn bm + dp. How to start it. i.e as of normal dp is concerned, first thing a brute force solution and then memoize it. But as for bm + dp, i looked into TSP. But there the brute force way is just factorial and it has nothing to do with the subset construction. I also looked into tutorials of hackerrank (Assignment problem). But i could not understand it. So can someone give a detailed explanation of how to approach bm+dp and how to solve it? TIA

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My rating has been 1900.. I do not know should I be sad or happy :-)(

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

    if in next contest (<1900).i think you will change your dp color.

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

    I had 1900 two times and it was ideally for perfectionist, but i am not a perfectionist, haha

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

      1899 is "more perfect" for me. With 1899, you are the best of experts. You know, Expert.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A

TEST Case : 100 99 98 100 Output should be : 200 198 196

Because They can climb 100 < 200 AND 99 < 198 ANS 100 < 196

They can like also 100*2 >= 200 true 99*2 >= 198 true 98*2 >= 196 true

Masha can clim all of them and he can like the smallest one 100*2 >= 196 true

So why the system give WA and give -1 instead of this solution ?

→ Reply
»
7 years ago, # |
  Vote: I like it +61 Vote: I do not like it

AshishYadav are true now :)

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Div2A: For input 100, 99, 98, 100 can someone tell me why 200, 198, 196 is not a correct answer?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV2 people(Pupil) who don't understand problem A and getting low rating :p Your text to link here...

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why the following formula is true, and how to use it to solve D?

when b > phi(m)

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

    Is that (mod m) over the whole power or on just b?

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

    Assumption, m = p * q, Where p is as large as possible such that gcd(a, p) = 1. Applying Euler's theorem for modulo p. For modulo q, because b > φ(m) so the remainder always is 0. That is the purpose of plusing φ(m) in φ(m) + b mod φ(m),

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      For modulo q, because b > φ(m) so the remainder always is 0

      Can you elaborate on this? What remainder that is "always 0"?

      PS: Got it. Since a is divisible by all the prime factor of b, ax will be divisible by b when x is large enough. (φ(m) is just a possible lower-bound, the actual lower-bound can be lower). Is that correct?

      PS2: Also, how to prove that if and , then ?

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

        The rest is quite clear. ab ≡ aφ(m) + b%φ(m) modulo p, q. Because gcd(p, q) = 1) so done?

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

          Got it. Turned out the last piece of proof that I'm missing is Chinese Remainder Theorem.

          Thanks for your help. (I spent the entire morning just trying to prove this formula)

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

    Only one clarification, when b>phi(m) may be exchanged for when b>log(m) I have an empirical not bounded proof, means that I can only prove that in some point that formula works. I unable to give a full proof of one of the two lower bounds, but the boths works nicely.

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

    This solution doesn't seem to be using the property you mention but still gets AC. :/

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Actually, Problem A refers to the famous Russian folk tale about Masha and three Bears, that's why we have such a long statement. So, by solving this problem you can look at the part of out culture. Here is the original text:

Once upon a time, there was a little girl named Masha. Onу day she went for a walk in the forest. Pretty soon, she came upon a house.  She knocked and, when no one answered, she decided to walk right in.
At the table in the kitchen, there were three bowls of porridge. She tasted the porridge from the first bowl.
“This porridge is too hot!” she said. So, she tasted the porridge from the second bowl.
“This porridge is too cold,” she said. So, she tasted the last bowl of porridge.
“Ahhh, this porridge is just right”.
After the meal Masha decided to have some rest and went into the living room. There she saw the three chairs: large, smaller and the smallest. Masha sat in the first chair and fell from it.
“This chair is too big!” she exclaimed. So she sat in the second chair.
“This chair is too big, too!” So she tried the smallest chair.
“Ahh, this chair is just right,” she said.  But just as she said this, the chair broke!

Then Masha decided to take a nap and went to the bedroom.  She lay down in the first bed, but it was too hard.  Then she lay in the second bed, but it was too soft. Then she lay down in the third bed and it was just right.  Masha fell asleep.
As she was sleeping, the three bears came home.
“Someone’s been eating my porridge”, – growled the Papa bear.
“Someone’s been eating my porridge”, – said the Mama bear.
“Someone’s been eating my porridge and they ate it all up!” – cried the Baby bear.
“Someone’s been sitting in my chair”, – growled the Papa bear.
“Someone’s been sitting in my chair”, – said the Mama bear.
“Someone’s been sitting in my chair and they’ve broken it”. – cried the Baby bear.

They decided to go to the bedroom. Papa bear growled: “Someone’s been sleeping in my bed”.
“Someone’s been sleeping in my bed, too”, – said the Mama bear.
“Someone’s been sleeping in my bed and she’s still there!” – exclaimed Baby bear.
Masha woke up and saw the three bears. She jumped out of the window and ran away.
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2 B, the problem statement says '.' will be found where there is no 'x' or 'o' but if you check your submission you can see they are passing underscore '_' instead of a period. To find this go to your submissions and click on this problem. Anybody face the same problem?

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it -15 Vote: I do not like it

Thanks to MikeMirzayanov for such a great platform and all the red coders who create such nice problems which i feel are great to improve not only our basic and fundamental skills of core CS but also thinking skills to great extent. but it seems that quality of the problems is decreasing now-a-days .

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

is there any editorial?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any editorial?

→ Reply
»
7 years ago, # |
  Vote: I like it +34 Vote: I do not like it

What's wrong with codeforces again? Why nobody is on first place?

→ Reply
»
7 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Why did you remove GasTheKikes , the winner?

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

    Look up "kikes" on urban dictionary. And if you still not understand it, read about WW2 and the holocaust.

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

For Div2 E (or Div1 C) "Party", is there anyone that has passed it by using the following algorithm?

Lemma: A group of guests is available iff I. their friends cover all people II. without other people, they are still connected

So just use a bit-dp, generating all states and check that if each of them satisfies the lemma above, and choose one with the minimum number of people.

Total Complexity is O(2^n*n)

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

    Of course one can do some pruning in the dp-process, and it'll be much quicker.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    In particular, for each state(that is a bit-representation of people) I, maintain 2 data, one is whether it is connected (a bool), the other is their friend (using a int to represent it by bit-representation)

    and just check every friend J of them who is not among them, and update the state I|(1<<J), set its "connected" to true, and set its "friend" to (friend of I)|(friend of 1<<J)

    and when a state K, its friend covers all, then it is an available group of people, and one should use it to update the answer.

    and it can be proven that the answer will have nothing to do with the order of the guests.

    So it's O(2^n*n) in total.

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

      Is it easy to prove the order is not important?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 4   Vote: I like it +1 Vote: I do not like it

        I think it's pretty easy though, don't know how is it to other people.

        consider 2 series, representing the same people but in different orders, let's call it A and B,obviously A and B are permutations to each other.

        consider an operation in a series, which is swapping 2 neighbouring person, and we can do some finite steps of such operations to transform series A into series B(like bubble sort).

        so we just have to prove that in one such operation, their is no difference between the final outcome, and then, because A can transform to B by some finite steps of those operations, and in each steps, the outcome won't change, so in the end, A and B are equivalent in outcome.

        and I'll prove that such operation won't make difference to the outcome. consider two series, satisfying series 2 is transformed by series 1 after doing one such operation. they'll have the formations as below: series 1: ab..zXYa'b'...z' series 2: ab..zYXa'b'...z' (swapping X,Y) when we have performed the common prefix ab..z, their outcomes are same. when a person P have introduced all of his friends to each other, the friends of only P's friend maybe changed, but the friends of any person who's not P's friend will stay unchanged. so if X and Y aren't connected currently, performing X will not change Y's friend, and what Y do next will be have no difference, so as performing Y first and X next,so there's no difference between ab..zXY and ab..zYX and if X and Y are connected currently, performing X will let all X's friends know each other including Y, and then performing Y will let all Y's new friends(from X) and Y's old friends(not from X) and X and Y, all know each other, the outcome is all of X or Y's friends including themselves knowing each other, and the friends of people who aren't X or Y's friends stay unchanged, so if we performing Y first and X next, it's the same outcome. so no matter whether X and Y is connected currenty, performing X then Y, is equivalent to performing Y then X, so ab..zXY is the same to ab..zYX after doing the common suffix a'b'..z', ab..zXYa'b'..z' is equivalent to ab..zYXa'b'..z' so it's proved that such operation won't make difference to the outcome.

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

          Thank you! I had the intuition of your proof but I couldn't formalize it.

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

    A group of guests is available

    Could you, please, elaborate what do you mean by available?

    their friends cover all people

    And this.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      I think he means that if you use that group then all people will be connected

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

      a group guests that satisfied the constraints: after one by one they come to introduce their friends to each other, all people will be familiar with each other.

      that's what I mean.

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

    I've used google translation to translate the Russian version of editorial, and found the idea for this problem is just the same as I posted.

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

      Where can i find the editorial?

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

        enter the contest interface, and the link "Tutorial" is at the right-bottom corner.

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

          When i click tutorial, it says "You are not allowed to view the requested page" What can I do?

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

            oh I've just found what you said. the link is available earlier when I enter from it.

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

Is the editorial up?

→ Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

System test for problem B (div 1) is too weak. For example, 33583372 this code will surely get TLE with 3 33333, in custom test it ran for ~6s.

→ Reply
»
7 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Good contest, the problemset was perfect, We want more contests like this. but please use better problem statements.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    You didn't even participate

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      and you did? by the way i read the problems.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        LOL I didn't say I participated. You said this contest was good but you didn't solve problems in contest environment.

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

    Why do you use "we" instead of "I"?How do you make sure it's everyone's feeling about the contest but not only yours?

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why everyone always complaint about Codeforces. But it is not only happening with you others are also facing it. I think it is due to you are not able to perform well in the contest and same is happening with me but complaining according to me will not solve that problem. Try to perform well in the contest. See people like KAN and other more who are red and even purple also. The difference b/w them and us is that they try to not commit the mistakes that they have committed earlier. I hope my message is clear to all and if u don't wanna give a shit to this then u are different :(

→ Reply
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

vintage_Vlad_Makeev Please upload the editorial.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

div2e My approach is greedily pick the node that can create as many as possible edges among friends. Got Wrong answer on test 51 :'( Code: http://codeforces.me/contest/907/submission/33589732

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

    a concise counter-example to the greedy algorithm you said above is like this: 9 13 7 8 8 9 9 7 7 1 7 2 7 3 9 4 9 5 9 6 8 2 8 3 8 4 8 5

    (the answer will be: 2 7 9 ) that's because of the person 1 and 6, the person 1 just know 7 in the beginning, and 6 just know 9, so (7 or 1) and (6 or 9) must be chosen, and if you just choose 7 and 9, they will be an answer to problem, without 8(although initially he knows the most number of people comparing to 7 or 9)

    → Reply
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

When will we get the editorial ?

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Where can I find the editorial of this contest?

→ Reply
»
7 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Any plans of publishing the editorial in near future? :)

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In div2 E what if m=0 then even if do operations in any order then also we can't make all of them know each other??

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

    It's guaranteed that each pair of friends is described not more than once and the graph of friendship is connected.

    → Reply
»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

please upload the editorial :/

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

For question 1 of div. 2 test 4 is input "99 50 25 49" my output is 99 50 25

which I think is correct because mama bear fits and likes her car, just like papa bear and Masha can fit into son bear's car because son bear's car-size limit is 50, and Masha is size 49.

The correct output is apparently 100 99 49 which is also correct as all bears and people can fit into their cars, but this is not the only solution and in the question, it is stated that "multiple answers are allowed" if you want the source code for my solution the link is https://pastebin.com/AK8yXQPN . Thank you for posting any solutions/ answers to my question.

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

    Think about it: the problem asks you to output the size of the cars of the three bears. The condition is that Masha should be able to fit into all three cars (which means that Masha's size should be <= all three bears sizes), but only like the small car (which means that Masha's size *2 >= only the small bear's car's size). In your output, neither condition is met, since Masha (size 49) cannot fit into the small car (size 25) and Masha likes both the small car and mother bear's car (since 49*2=98 which is >= both the small and medium car)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Where exactly did the problem state that Masha should fit into all cars? It is implied that Masha HAS TO fit into all cars larger than her (including mama and papa's) and she does like the son's car.

      Overall the question was very confusing in both languages (I read it in Russian and it made no sense at all) and it was the reason I was stuck on this one question for the whole round.

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

        The same issue all of us are complaining about: badly written statements. I read the problem in English and it stated in the problem description.

        "Masha came to test these cars. She could climb into all cars, but she liked only the smallest car"

        I also got stuck in this one for the first 50 minutes of the contest.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so...random_shuffle works for D-Seating of Students, this is interesting.

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

    Just random_shuffle doesnt work as I explained above and indeed I tried it after contest and it is too slow, as expected.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I have a question.

I send this 33572495 for problem A dive2 in problemset and got AC.

and output for this testcase is:

input : 100 10 9 15

output : 200 10 15

but answer is -1.

why this code got AC! :)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the answer to this test case of DIV 2 C

6

! codeforces

! hello

? e

! e

? o

? e

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

i think you should never publish an editorial if you want to keep this contest as the worst contest ever !!

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I cannot wait to see the editorial!
Hope it will be published soon.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Can you Please publish the editorials?

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Came for the tutorial again. Found nothing again.

Please upload the tutorial :( Thanks a lot

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vintage_Vlad_Makeev (previous revision, new revision, compare).

→ Reply