300iq's blog

By 300iq, 9 months 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 wxhtxdy, Claris, quailty, jiry_2 (camp TA team), and gamegame, isaf27, tmwilliamlin168, mango_lassi, WNG, lewin, sas4eka, Feynman, 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

»
9 months ago, # |
  Vote: I like it +96 Vote: I do not like it
»
9 months ago, # |
  Vote: I like it +70 Vote: I do not like it

I thought Syloviaely was the one testing the round XD

»
9 months 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......

»
9 months ago, # |
  Vote: I like it -53 Vote: I do not like it

wxhtxdy choose to wait and let the tourist drop, would it success?

»
9 months 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

»
9 months 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?

  • »
    »
    9 months 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.

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

It overlaps 1 hour with the topcoder SRM

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

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

    • »
      »
      »
      9 months 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.

»
9 months 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!

»
9 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Will In div 2 be a lots of greedy?

»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Please make the problem statement short and clear. :)

»
9 months ago, # |
Rev. 3   Vote: I like it +116 Vote: I do not like it
when i hear about a chinese something
  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    You really should thank god you're not in china right now.

»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Score distribution?? Reaaly want to come expert!

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

Pretests for Problem B too weak!!!

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

How to solve problem DIV2 B and C ?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks .I got your point

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't the time complexity O(m*n) ?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No .That will give TLE since m can be as large as 10^9

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

          And is it not possible in 3 second?

    • »
      »
      »
      9 months 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.

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So does it mean that it was a simple brute force? I mean, checking for all the value of x and comparing the output with array B

    • »
      »
      »
      9 months 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 ?

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, I understood Now) Thanks alot :)

    • »
      »
      »
      9 months 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

      • »
        »
        »
        »
        9 months 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...

»
9 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

What was pretest 4 in Div2 D?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2 D?? wa4..

  • »
    »
    9 months 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)

    • »
      »
      »
      9 months 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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow!Nice solution!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to prove it cannot be less than minimum of both colors ?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

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

        Yeah, really elegant, please explain the thought process.

      • »
        »
        »
        »
        9 months 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.

      • »
        »
        »
        »
        9 months 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.

»
9 months 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

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain the idea of problem C?

  • »
    »
    9 months 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.

  • »
    »
    9 months 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$$$).

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the hacking case for Div 2 C ?

»
9 months 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.

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

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

    • »
      »
      »
      9 months 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 :).

      • »
        »
        »
        »
        9 months 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.

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

          Not so hard, see another thread for details

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

          Yes . It was not that easy

        • »
          »
          »
          »
          »
          9 months 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.

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

    How is this today's problem B?

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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].

          • »
            »
            »
            »
            »
            »
            9 months 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.

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

              That is a neat proof!

          • »
            »
            »
            »
            »
            »
            9 months 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

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            9 months 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..??

            • »
              »
              »
              »
              »
              »
              »
              9 months 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.

  • »
    »
    9 months 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?

  • »
    »
    9 months 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.

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

    Can relate

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

»
9 months 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?

  • »
    »
    9 months 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
    
    • »
      »
      »
      9 months 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..

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

    Did the same. Got my mistake last second but couldn't submit. My problem was with:

    7 3
    5984990
    

    Basically I was not doing the comparison correctly for remaining k length strings within a. My incorrect soln gave 5995990. Highly unlikely you'll commit the same mistake too but still..

»
9 months 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.

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Difficulty level of B's increasing these days .

  • »
    »
    9 months 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

»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Is that solution of Div1B?

Code
»
9 months 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

  • »
    »
    9 months 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.

  • »
    »
    9 months 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 :(

»
9 months 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 ?

»
9 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Hackforces yeeeeeeeeah

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2A ?

»
9 months 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.

  • »
    »
    9 months 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)$$$.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months 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.

»
9 months ago, # |
  Vote: I like it -48 Vote: I do not like it

MathForces!!!

»
9 months 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..............

»
9 months ago, # |
  Vote: I like it -6 Vote: I do not like it

good contest :D

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months 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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Again I will go green

»
9 months 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

  • »
    »
    9 months 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.

»
9 months 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.

»
9 months 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

  • »
    »
    9 months 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 .

  • »
    »
    9 months 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.

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

what are good tests

»
9 months 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!

»
9 months ago, # |
Rev. 7   Vote: I like it -48 Vote: I do not like it

...

  • »
    »
    9 months 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.
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    So now we must clap for your heroic action?

    • »
      »
      »
      9 months 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...

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

The pretests are just sad.

  • »
    »
    9 months 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 ):

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

C was easier than B imo.

»
9 months ago, # |
  Vote: I like it +27 Vote: I do not like it

1417th before sys tests, 813th after

»
9 months 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://codeforces.com/contest/1269/room/251

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

»
9 months 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?) .

»
9 months 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.

»
9 months 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.

»
9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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 :)

      • »
        »
        »
        »
        9 months 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 :)

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It should be *, not +.

          • »
            »
            »
            »
            »
            »
            9 months 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

            • »
              »
              »
              »
              »
              »
              »
              9 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months 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

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve B via string matching algorithm?

»
9 months ago, # |
  Vote: I like it -12 Vote: I do not like it

The contest is too good. I loved contest .The sums are not so easy but every problem has some bit of logic. i thank to codeforces..

»
4 months 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. :)