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 21.12.2019 14:05 (Московское время). 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 EvenImage, 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
Chinese round.
Very cool round!!!
I thought Syloviaely was the one testing the round XD
Will you come to the camp in Beijing? Hope our team can qualify though......
EvenImage choose to wait and let the tourist drop, would it Success?
But why did you tag the success guy?
Just because to color the success.
orz jjang36524
orz orz
Orz mr master
What?
EvenImage is tester for this round so he can't give this contest.
2019 has come to an end and Codeforces contests are a lot and really great. Love that, love Codeforces <3
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?
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.
300iq's problems being tested by Chinese coders. Yet another proof that...
That Russia and China ???
It overlaps 1 hour with the topcoder SRM
Are you sure? clist.by says there's a 4 hour gap.
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.
So many contests in December! Codeforces is growing to be more and more awesome. Love you Codeforces!
Здравствуйте! А условия на русском языке будут?
На всех раундах есть русские условия
Will In div 2 be a lots of greedy?
Why downvote me?
Огласите разбалловку задач.
You really should thank god you're not in china right now.
thanks, God
Score distribution?? Reaaly want to come expert!
Thank you for the short statement problems...!!! :)
RIP rating
Get ready for change in color.
thank you for the positive words
Pretests for Problem B too weak!!!
Задача Div.2C отстой.
How to solve problem DIV2 B and C ?
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.
Thanks .How to prove O(n) different 'x' possible ?
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.
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.
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.
I didn't understand the meaning of differences can you please explain it a bit ?
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.
Can someone check my solution coz I tried it this way and got TLE.
67355223
Nevermind, I got it, we can use only one element of first array to get all possible x'es instead of trying all pairs...
First 3 tasks in div 2 were rather boring and technical.
How to solve C, I got WA on test 7
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.
what if last digit is '9' while adding? Then do we have to consider carry too?
Yes you need to!
What was pretest 4 in Div2 D?
Could be something like
6 5 4 3 3 2 1
My program gives 8 as output
What is the answer? I got 11.
Answer should be 9
Can you please explain how?
1
1 4
2 4 6 6
2 5 5 8 8
3 3 7 7 9 9
Like this 1-9 are number of domino
Thanx
[Deleted]
How can it be 10... there are 18 blocks. If all are taken then you get 9 as answer.
its answer is 12
" odd even odd " gets full dominos and do repeatedly using stack;
How does odd even odd give full dominos? Eg for a[] = 3 2 1, the answer should be 2. How can it be 3? I identified pattern odd (even even)* odd to give full dominos.
How to solve div2 D?? wa4..
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)
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.
I got it..
Wow！Nice solution！
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.
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
Yeah, really elegant, please explain the thought process.
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.
Can you give me some simillar
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.
pretests of C are weak.I did a hack with:-
6 3
129999
What's the correct answer to that?
130130
Obviously bro, the pretests were weak. I forgot to update the values to 0 after increasing one digit and got my solution hacked :(
Can someone explain the idea of problem C?
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.
Thanks, this helped!
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$$$).
Thanks!
what is the hacking case for Div 2 C ?
my code was failing on : 4 2 1999
Thanks!!
One such hack test case : 6 3 199299
How to solve div-2 D??
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.
But any proofs that it is the case in this problem?
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 :).
I mean, I know the answer is $$$min(W, B)$$$, but the proof is really hard.
Not so hard, see another thread for details
Yes . It was not that easy
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.
How is this today's problem B?
"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.
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.
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].
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.
That is a neat proof!
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
Or it's just another kokokoko kind of consideration :)
Will this idea of min(black, white) work if the column sizes are not sorted..??
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.
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.
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?
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:
Woah, my solution fails on that case. Thanks.
Guess I made a similar mistake to yours..
Prestest are weak for c,My soLn will fail for 7 3 3993998.
The problem statements were concise and clear. Nice work!
Difficulty level of B's increasing these days .
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
Is that solution of Div1B?
The shortest solution of Div1B ever)
I see this and raise you 66611150 (well, Div1C but still).
This Div1F beats them all
62833307 Can't forget this
2 characters xd 16151475
Is problem "K integers" solvable, without using treaps? btw: "K integers" AKA div1C/div2E
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 :(
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 ?
https://paste.ubuntu.com/p/hpxGCPshNp/
This is my solution, hope to help you.
Hackforces yeeeeeeeeah
How to solve div2A ?
brute force
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.
if n=1 then output "9 8"
else output "(3*n) (2*n)"
9*n 8*n
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.
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)$$$.
++j is definitely a bug here.
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.
Yes, I see. That's why I should consider such solutions when solving) At least in no-hack contests)
You already earned approx 30 positions with +300 pts. Good job!
Thanks, but it was just a luck. Hope no fails on systest :)
What is the issue on 28 test of problem Div1D? Swistakk
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.
MathForces!!!
Nah, not really
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..............
How to solve div2 B problem,i am getting time limit exceeded!!
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
Again I will go green
I am always delighted whenever it is useful to determine strongly connected components of tournament in $$$O(n)$$$ knowing degrees of vertices :D
Wow, I didn't know about that, I just wrote dfs in $$$O(n^2/64)$$$ instead.
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.
for div2 B if a=[0,4,5] and b=[1,4,5] and m=7 there is no such x
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.
what are good tests
Hello, dear 300iq, it seems to me that you would be good at doing olympiads for mathematicians!
...
Three things I want to say.
So now we must clap for your heroic action?
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...
The pretests are just sad.
Yeah I wrote i < n instead of i < k by mistake in Div2C and got TLE on system test ):
C was easier than B imo.
I solved C just now.
When div1 A was easy and I got 2 wrong orz When I solve div1 B :D
1417th before sys tests, 813th after
Its true
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
Good for both. You got 100 extra, they got few hundred extra.
Yeah, but it is sad that after my hack noone hacked me. In this case I also could have got a few extra hundreds.
You had already locked it so..hacking others were your best case scenario at that point.
Damn, you are right)
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?) .
300iq request to enable link of contest in " Codeforces Round #609 (Div. 1) and Codeforces Round #609 (Div. 2)," of announcement.
tourist comes again in Div1 and once again consolidates his number 1 rank.
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
You forgot to take in account the complexity for sorting inside the 1e5 loop. It makes the number of operations roughly equal to 2e9.
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 :)
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 :)
It should be *, not +.
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
No, it's not. The sorting algorithm works in $$$O(n \cdot log$$$ $$$n)$$$ time and you run it $$$10^5$$$ times.
Thanks a lot man. SO I think the complexity of my first code is = 2000(2000*log(2000))? Link: https://ideone.com/US2vA8
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?
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
How to solve B via string matching algorithm?
...
Я думаю это будет достаточно сложный контест, т.к. тут замешаны китайцы :D PS:Я никого не осуждаю не принимайте близко к сердцу :(
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. :)