300iq's blog

Codeforces Round #609, based on ByteDance — Moscow Workshops Online Contest
By 300iq, 5 years ago, translation, In English

Hello, Codeforces community!

I'm glad to invite you to Codeforces Round #609 (Div. 1) and Codeforces Round #609 (Div. 2), which will be held on Dec/21/2019 14:05 (Moscow time). The round will be rated for both divisions.

The problems were taken (mostly) from the ByteDance — Moscow Workshops Online Contest, that's happening at the same time. They were prepared by myself and tested by jqdai0815, Claris, quailty, jiry_2 (camp TA team), and gamegame, isaf27, tmwilliamlin168, mango_lassi, WNG, Lewin, sas4eka, UselessDev, Aleks5d,MrDindows.

ByteDance is a technology company operating a range of content platforms that inform, educate, entertain and inspire people across languages, cultures, and geographies. ByteDance has partnered with Moscow Workshops ICPC and Codeforces to organize a top tier and exclusive training camp for the International Collegiate Programming Contest. The upcoming Programming Camp will be held in Beijing from February 10th to 16th, 2020.

ByteDance — Moscow Workshops Online Contest is an opportunity to participate as teams in this camp.

You can find more information about this training camp, including registration and prizes at https://programcamp.bytedance.com/.

UPD: Editorial

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

Comments Comments (184)
| Write comment?
»
5 years ago, # |
  Vote: I like it +96 Vote: I do not like it

Chinese round.

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

I thought Syloviaely was the one testing the round XD

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

Will you come to the camp in Beijing? Hope our team can qualify though......

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

jqdai0815 choose to wait and let the tourist drop, would it Success?

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

2019 has come to an end and Codeforces contests are a lot and really great. Love that, love Codeforces <3

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

I'm having an HTTP status 403 — forbidden message when trying to register. Cannot login from any other device/browsers as well. Is it an ISP issue?

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

    It has been resolved. It needed to turn off the CF predictor extension. Although I'm not sure whether there is a cause-effect relationship between these, but I don't wanna test it.

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

300iq's problems being tested by Chinese coders. Yet another proof that...

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

It overlaps 1 hour with the topcoder SRM

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

    Are you sure? clist.by says there's a 4 hour gap.

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

      Oh no, they messed up the email they sent for 24 hr reminder with the previous SRM link which occurred at a different time.

      You are right there is a 4 hour gap.

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

So many contests in December! Codeforces is growing to be more and more awesome. Love you Codeforces!

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

Will In div 2 be a lots of greedy?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +116 Vote: I do not like it
when i hear about a chinese something
→ Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Score distribution?? Reaaly want to come expert!

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

Thank you for the short statement problems...!!! :)

→ Reply
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it
When you are sure that it's going to fail system testing
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

Pretests for Problem B too weak!!!

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

How to solve problem DIV2 B and C ?

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

    For B there are O(n) different 'x' possible (Map the first element of A to any one of 'n' element from B). For each such mapping check if mapping is possible in O(n) . It yields an O(n^2) algorithm.

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

      Thanks .How to prove O(n) different 'x' possible ?

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

        one to all is O(n).First element can only be mapped in 'n' possible ways with fixed 'x'. Now check whether this 'x' fits all.

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

      Mapping all elements one to one is O(n^2), isn't it?

      after mapping we got O(n) because of n possible x'es and O(n+n*logn) for checking current x. I got TLE here, don't know how to do it right.

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

    For B, basically find all possible arrays that can be formed from A using differences (this can be done in O(n^2 log n) by sorting the resulting array and comparing with sorted B. For C, just note that you need to make an array that is formed when you repeat the size k subarray of the given array. If it is less than or equal to a, then we are done. Else just increment the repeated array and return the answer.

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

      I didn't understand the meaning of differences can you please explain it a bit ?

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

        Obviously the first number in array a should be equal to a number from array b after adding x. Let me show you an example. n=5 , m=5; a={2,4,3,2,4} b={3,4,3,3,1}

        Then you only need to check if numbers:

        1-> difference of a[0] and b[0]

        2-> difference of a[0] and b[1]

        4-> difference of a[0] and b[4]

        would work as value x

        I hope you understand it . I explained it really bad,Sorry.

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

      Can someone check my solution coz I tried it this way and got TLE.

      67355223

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

        Nevermind, I got it, we can use only one element of first array to get all possible x'es instead of trying all pairs...

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

First 3 tasks in div 2 were rather boring and technical.

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

    How to solve C, I got WA on test 7

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

      Just check if first substring of length k is >= than other k-substrings in s.If that is true then repeat it. If that is not true then its enough just to add 1 to first k-substring and repeat it.

      You might have forgotten to check if at some point digit in s is less then in your k-string, then you don't have to increment it.

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

        what if last digit is '9' while adding? Then do we have to consider carry too?

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

What was pretest 4 in Div2 D?

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

How to solve div2 D?? wa4..

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

    I assumed that each square has a colour similar to the chess boards. Then the answer is the minimum between the number of white squares and the number of black squares because each domino piece has to sit on a black square and on a white square (it cannot sit on two squares of the same colour)

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

      This is an upper bound to the answer. Could you explain why this is achievable (how will you construct an arrangement with the specified number of dominos). Thanks in advance.

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

      Wow！Nice solution！

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

    Do a chessboard colouring of the Young table. Remove the number of excess whites or blacks from the sum of elements of a and then divide by two. That would be the answer.

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

      Elegant thinking. I thought it was some kind of dynamic solution, but anyway went for just throwing a greedy one. What thought process lead you to this coloring idea!? :D

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

        Yeah, really elegant, please explain the thought process.

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

        The easiest way (which is also what I did) is to do so many problems that you have encountered this coloring idea before. You don't even need to think or be creative.

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

        My solution was as follows: Note that if we color the board as mentioned, every domino covers squares of the opposite color. So the answer is at most what I mentioned in the solution. To see that this is achievable, note that the greedy algorithm gives the same number of edges.

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

pretests of C are weak.I did a hack with:-
6 3
129999

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

Can someone explain the idea of problem C?

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

    Notice that the answer will have same number of digits as the original number. Because 9999...999 will always be a beautiful number.

    Well, it is clear that only first k digits need to be decided.

    So, first make a number by taking initial k digits as it is and check if it is greater than or equal to the original number. If yes, that is the answer.

    If no, then find the rightmost position in the first k digits such that it is less than 9 and update all the digits are this position to 0. Then form the beautiful number from this and return this as the answer.

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

    I did in this way:
    Firstly you can observe that the answer will not have more than $$$n$$$ digits.
    Let the number created by the first $$$k$$$ digits is $$$z$$$. First repeat $$$z$$$ (upto length $$$n$$$). Now, we get a number let's say $$$y$$$. If $$$y$$$ is greater than $$$x$$$, then this is your answer. Else, if $$$y$$$ is less than $$$x$$$ then increment $$$z$$$ by $$$1$$$ and repeat this new number (upto length $$$n$$$).

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

what is the hacking case for Div 2 C ?

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

People should google instead of solving problems during contest.
T̶o̶d̶a̶y̶'̶s̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶B̶.̶
A similar chessboard problem of today's B. link.

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

    But any proofs that it is the case in this problem?

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

      Lets color the whole table black and white like chess board

      Lets call the number of black cells B and number of white colors W. It is obvious that you cant place more than min(W,B). Because each domino takes one cell from each color.

      We can also prove that we can place min(W,B) dominos with induction. but it is complicated and long and needs drawing pictures that i don't know :).

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

        I mean, I know the answer is $$$min(W, B)$$$, but the proof is really hard.

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

          Not so hard, see another thread for details

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

          Yes . It was not that easy

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

          Not sure if it true, but we can try to construct in this form.

          There are 4 types of rows, starting with a color x and ending with a color y. So we will have a row in the form x?..?y.

          The difference of the total quantities of black and white, will happen in the types of rows with (x = WHITE, y = WHITE) and (x = BLACK, y = BLACK).

          So if we have more black than white, we can remove the last cell of a row (x = BLACK, y = BLACK). Similar when we get more white than black.

          Now we want to know, how to assign the extra rows (x = WHITE, y = WHITE) and (x = BLACK, y = BLACK), as the others types of rows can be assigned easily.

          Then we find the first position of rows of type (x = WHITE, y = WHITE) and first position of rows of type (x = BLACK, y = BLACK) and remove one cell from start + 2*k of the rows of type (x = WHITE, y = WHITE) and (x = BLACK, y = BLACK) and remove two cell from start + 2*k in the rows in between, where k is the number of column that have been used in the rows in between, the removal part can be tiled easily and repeat until there is no more rows of these types.

          Following this process we can obtain a possible tiling for the remain, and we can check that this removal process is aways possible.

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

    How is this today's problem B?

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

      "The other answer correctly explains that such a covering is impossible because it would require an equal number of black and white squares (since each domino must cover one black and one white square), which the corner-cut board does not have."

      Just paint given board as a chessboard. Alternative black and white in colour. Take minimum.

      I got WA 4. I just googled "place 2x1 and 1x2 pieces on board" this was the first link with that statement as the first answer. Then AC.

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

        Do you have any proof? Or better, did you have any kind of proof during the contest? I think that this problem is too much based on guessing, but I wouldn't say that the link you sent can be negative evidence against this problem at all.

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

          Let's prove it by induction of min(black, white). Base is obvious.

          Let's assume we have any [a0,...an] with transponed diagram [b0..bm]. If we do have a[i] == a[i + 1] > a[i + 2] (a[n + 1] = 0), then we could cut one domino a[i] -= 1, a[i + 1] -= 1 and obtain diagram with min(black, white) 1 cell less. The remaining case is when a[i] all different, so do b[i]. In this case we have very simple diagram (a[i] = n + 1 — i) we could try to divide somehow [if statement is true, it have to be pretty simple].

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

            This particular case have one key observation — it's top cells have the same color. So if we will cut every vertical line independently starting with bottom, we could skip at most one top cell at each. All these cells have the same color, so we won't miss any black (or white, based on min(black, white)) cell.

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

              That is a neat proof!

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

            I did this one right after the contest :) The problem is about finding the size of the maximum matching in a bipartite graph. Then just consider the Hall violators.

            https://en.wikipedia.org/wiki/Hall_violator

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

              Or it's just another kokokoko kind of consideration :)

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

            Will this idea of min(black, white) work if the column sizes are not sorted..??

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

              No, this proof based on easy structure of this kind of diagrams. If you take, say, 1,0,0,1,0,0,1,.. you'll have a lot both of black and white cells, but no domino possible.

              Obviously connectivity should be required, but I can't say if it's enough to whole statement keep true for now.

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

    I did know this that if we remove opposite corners of a chess board, its impossible to cover it with 2x1 dominos, but how does this derive to solution of this problem?

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

    I would expect that specific problem from SO to be known to most of div1 contestants.

    However, I would say there is a long way to go from that problem to solving and proving div1 B.

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

    Can relate

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

    Skill of googling is much harder than what is described in your link.

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

    Unpopular opinion: I have two goals when doing contests: to have fun and to improve my problem solving abilities. Googling doesn't fulfill any of these goals, so I don't do that even though it is suboptimal sometimes.

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

What's pretest 7 in Div2 C?

My solution involved taking the first k digits of the number. Then, check if we can just repeat those first k digits and get a valid number greater than equal to the original number, If not, I just incremented the first k digits by one (increment the rightmost digit not 9, and set all the digits to its right to 0), and then repeated it.

Am I right with the observation that the answer will never have more digits than the original number? What else could be wrong with my approach here?

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

    I had WA7 a couple of times because I was lazy to write a proper number comparison and tried to code it fast (and this costed me dear 20 min in the end). My solution was failing on this test:

    9 3
123113133
Answer: 123123123
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Woah, my solution fails on that case. Thanks.

      Guess I made a similar mistake to yours..

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

Prestest are weak for c,My soLn will fail for 7 3 3993998.

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

Difficulty level of B's increasing these days .

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

    I agree, couldn't do B in last contest, couldn't do B today (TLE at test case 5), I did C though. Let's hope it passes system testing today lol

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

Is that solution of Div1B?

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

Is problem "K integers" solvable, without using treaps? btw: "K integers" AKA div1C/div2E

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

    Answer for some k is number of inversions between these numbers, and cost of bringing together the numbers. If number is > k it should go to left of first position, or right of last position, so it's sum of min(cntLeft, cntRight), which can be calculated with two segment trees.

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

    I thought of a solution using segment tree and adding small changes to the change in median of the previous k permutation and the inversion count. Couldn't implement properly in time :(

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

In C Div2 , I think the main idea is to have k chains or k components , each of them has one digit but you have to intersect between them to get the minimum number I tried but i couldn't solved it ... any help ?

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

Hackforces yeeeeeeeeah

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

How to solve div2A ?

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

    brute force

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

      lol, my idea was just: print 99999999 and 99999999-n if n is odd. and print 1000000000 and 1000000000-n if n is even. I hope she passes systests.

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

    if n=1 then output "9 8"

    else output "(3*n) (2*n)"

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

    9*n 8*n

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

Nice contest, thanks!

Two incorrect hacks on A because of possibly passing $$$O(n^2)$$$ solution (link). Looks like a traditional for me rule "if $$$n \ge 100000$$$, no $$$O(n^2)$$$" should be revised.

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

    This is not $$$O(n^2)$$$, right? One of the cycles always goes up to $$$k$$$ and the other one goes by multiples of $$$k$$$, so it's just $$$O(n)$$$.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it 
       bool ok = true, nine = true;
    for (int i = 0; i < k; ++i) {
        if (s[i] != 9) nine = false;
        for (int j = i + k; j < n; ++j) {
            if (s[i] != s[j]) ok = false;
        }
    }

      ++j is definitely a bug here.

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

        But these are simple and fast operations.

        There are n*n/2 of them, and these are simple requests to neighboring memory cells, which is very good for the CPU cache.

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

          Yes, I see. That's why I should consider such solutions when solving) At least in no-hack contests)

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

    You already earned approx 30 positions with +300 pts. Good job!

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

What is the issue on 28 test of problem Div1D? Swistakk

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

    I simply got a stupid bug, I sorted not this vector which I was supposed to, so I don't know in what way it can be tricky. It was in the part of determining which vertices when flipped lead to strongly connected graph.

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

MathForces!!!

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

For me always most of the competitions were worst as I performed poorly in the contests but this contest led me to think that googling out is better rather than thinking and applying the logics. 300iq wasted my day today..............

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

How to solve div2 B problem,i am getting time limit exceeded!!

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

    Try all possible x that is b[0] — a[i]. That's 2000 candidates

    For each of 2000 candidates Create the new array (2000 operations) Compare (2000 operations)

    -> O(N^2) passes

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

Again I will go green

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

I am always delighted whenever it is useful to determine strongly connected components of tournament in $$$O(n)$$$ knowing degrees of vertices :D

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

    Wow, I didn't know about that, I just wrote dfs in $$$O(n^2/64)$$$ instead.

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

I locked my solution for B and later realised that I never read that minimum x was asked, and also that I didn't make x positive. RIP rating.

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

for div2 B if a=[0,4,5] and b=[1,4,5] and m=7 there is no such x

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

    It is guaranteed that there exists some non-negative integer x . this was written in problem statement . so , your example input is not valid input , In a valid input you must find x .

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

    The question says — "It is guaranteed that there exists some non-negative integer x ... ". Hence, the test cases are made such that the answer exists.

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

what are good tests

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

Hello, dear 300iq, it seems to me that you would be good at doing olympiads for mathematicians!

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

...

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

    Three things I want to say.

    • You need to be able to handle success as well as failure.
    • Being expert and stabilising as expert are two completely different things.
    • Don't leave when you reach certain rating. Leave it, when you got bored of cp.
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    So now we must clap for your heroic action?

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

      nothing like that bro..sorry for posting it and wasting ur valuable time..i wish i could delete it..but i am not able to...

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

The pretests are just sad.

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

    Yeah I wrote i < n instead of i < k by mistake in Div2C and got TLE on system test ):

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

C was easier than B imo.

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

1417th before sys tests, 813th after

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

I hacked div2.C of the guy who was at the top of my room and I took his place. After it he made another submission. Finally, his second submission passed the system tests, but mine didn't. LOL! https://mirror.codeforces.com/contest/1269/room/251

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

    Good for both. You got 100 extra, they got few hundred extra.

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

      Yeah, but it is sad that after my hack noone hacked me. In this case I also could have got a few extra hundreds.

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

        You had already locked it so..hacking others were your best case scenario at that point.

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

Just before the end of this contest, my rank is 70 and it became 776 after system test. Anyway, It's first time for me to get two FST in one contest, so it's a fruitful contest (maybe?) .

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

300iq request to enable link of contest in " Codeforces Round #609 (Div. 1) and Codeforces Round #609 (Div. 2)," of announcement.

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

tourist comes again in Div1 and once again consolidates his number 1 rank.

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

Can anyone tell me why my codes gets TLE. 10^5*2^3 = 2*10^8 should have been passed within 3 second? Code Link: https://ideone.com/US2vA8 Thanks

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

    You forgot to take in account the complexity for sorting inside the 1e5 loop. It makes the number of operations roughly equal to 2e9.

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

      10^5*(2^3+log(2^3))= 200996578.428 (roughly 2*10^8)Then I think its the exact complexity. Can you explain a bit why its 2e9? Thank you :)

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

        ow sorry for my previous comment here my 2^3 = 2000. It should be 2e3. upd version: 1e^5*(2e^3+log(2e^3))= 200996578.428 (roughly 2*1e8)Then I think its the exact complexity. Can you explain a bit why its 2e9? Thank you :)

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

          It should be *, not +.

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

            Thanks man. I really messed up time complexity. I need to learn more about it. According to your talk this code time complexity is 0(n*(n*n))? Code Link: https://ideone.com/qY6WM9

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

              No, it's not. The sorting algorithm works in $$$O(n \cdot log$$$ $$$n)$$$ time and you run it $$$10^5$$$ times.

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

                Thanks a lot man. SO I think the complexity of my first code is = 2000(2000*log(2000))? Link: https://ideone.com/US2vA8

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

                  In inner loop except sorting we run two extra o(n) loop but here sorting cost is higher so we take higher value for calculate complexity thats why we avoid that extra two loop for complexity?

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

                  First comment: No, it's 1e5*2000*log(2000); you do O(n log n) operations 1e5 times, not n times.

                  Second comment: Yes, $$$O(n*2+n\cdot log$$$ $$$n)=O(n\cdot log$$$ $$$n)$$$.

                  Anyway, your code is wrong:

                  1 100002

                  0

                  100001

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

How to solve B via string matching algorithm?

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

...

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

submission — 79465012

problem — 1269C - Long Beautiful Integer

submission

Anyone who can tell why this failed in test case 7 ?

It will be a great help if someone can take time out from their busy schedule and help a co-learner. :)

→ Reply