But why did you tag the success guy?

jqdai0815 is tester for this round so he can't give this contest.

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.

That Russia and China ???

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

На всех раундах есть русские условия

Why downvote me?

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

RIP rating

Get ready for change in color.

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.

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.

How to solve C, I got WA on test 7

Could be something like

6 5 4 3 3 2 1

" odd even odd " gets full dominos and do repeatedly using stack;

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)

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.

What's the correct answer to that?

Obviously bro, the pretests were weak. I forgot to update the values to 0 after increasing one digit and got my solution hacked :(

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.

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

my code was failing on : 4 2 1999

One such hack test case : 6 3 199299

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

How is this today's problem B?

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?

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.

Can relate

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

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.

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

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

The shortest solution of Div1B ever)

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.

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

https://paste.ubuntu.com/p/hpxGCPshNp/

This is my solution, hope to help you.

brute force

if n=1 then output "9 8"

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

9*n 8*n

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

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

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.

Nah, not really

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

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

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 .

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.

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.

So now we must clap for your heroic action?

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

I solved C just now.

When div1 A was easy and I got 2 wrong orz When I solve div1 B :D