Hi everyone. I'm trashfirstsearch, and I used to be blue...
Anyways, Codeforces Round #370 (Div. 2) will take place on 10 September 2016 at 19:35 MSK. As usual, Div.1 participants can join out of competition.
Much thanks to GlebsHP for helping me with preparing the contest, MikeMirzayanov for the Codeforces and Polygon platforms, and minimario and Wrong_Answer_Exceeded for testing problems.
This will be my first contest prepared on Codeforces, and I have prepared all the problems with the intent of making them interesting for everyone. It is, as usual, strongly advised to read all the problems.
Good luck, and I hope you will gain rating(and force someone else to lose it >:) ).
Update: Congratulations to the winners:
Div.1
Div.2
Here is the editorial.
I sincerely apologize for the problems during the contest. However, I hope everyone found the problems interesting! Thanks to everyone who participated and helped with the problems!
Round 370 clashes with Topcoder Wildcard Round and Round 372 clashes with Topcoder SRM 698. ;(
Oh come on! after long time we're having a CF contest and now it conflicts with another contest! such life! -_-
TOP 1 — CleverCoder 100 % INFO
TOP 2 — CleverCoder 100 % INFO
Good luck and high rating to all.....
Hope you prepare problems better than solve them
Brutal
Savage
Rekt
I want to upvote you again.
Bad luck For You :P
Good luck, and I hope you will gain rating(and force someone else to lose deep blue >:) ).
That one brought to you by the letter S, as in Snap!
Then we'll see if you can solve them all :)
He didn't participate. But he has more likes on his comment than the whole blog post. :P
Your face. God damn
Sadistic
" and I used to be blue " is pretty unnecessary. everyone had a higher rating once (well, except tourist )
Subregional ACM-ICPC in Brazil will be in same time ;(
Не расстраивайся... порешаешь собственный контест и станешь фиолетовым.
I love you, minimario :)
this contest will be good because minimario is test the problems :)
huh?
I love minimario too
I hope one day i can be a problem setter too :) :)
nowadays, anybody can be a problem setter (wish you be one :) )
Best of luck to all
hope I can solve problem A & B this time
hope you solve A to D! a strong start!
Hope the queue will not be working slowly like on some previous contests
Well After A long time CF Today! Have to do Something Good B-)
Hi, for a few weeks the page is showing me this js errors:
enter:399 Uncaught SyntaxError: Unexpected token <
jquery-1.8.3.js:4680 Uncaught Error: Syntax error, unrecognized expression: href=#
or on anaother page: contests:297 Uncaught SyntaxError: Unexpected token <
It makes difficult to log in (once you are logged out), as the js stops to work, I had to submit the login form from js console manually.
Please also let me know where is better place to discuss such issues.
strongly advised to read all the problems :) :)
Whats the time duration for the contest?
2 hours, according to the contests page.
370 div 2 — (one hour + 5 minute)
Looking forward to interesting problems~ good luck && have fun!
+1s
I like the line "Hi everyone. I'm trashfirstsearch, and I used to be blue..." I hope that I will be blue after today's contest.
EDIT: I still wish to be BLUE
I hoped about being purple. I almost got it but then the round was declared unrated.
excited for the round
Ah
Delayed 10 Minutes
Unrated! ): I was doing pretty well this time too.
Old but gold
Open questions:
1) is P!=NP ?
2) What is the fastest algorithm for multiplication of two n-digit numbers?
3) Can the rotation distance between two binary trees be computed in polynomial time?
4) Will a day come in future that Codeforces server problems be permanently solved?
i don't know the answer for 1 & 2 & 3 but the last one my answer is impossible
Я думал, обычно, после серьезных изменений в системе проводится Testing Round, дабы все проверить. Что же в этот раз случилось? Тем более, что раунд должен был быть рейтинговым.
это уже второй такой раунд(
CF issues aside, the problems were quite nice and interesting
Good luck, and I hope you will gain rating(and force someone else to lose it ) Unrated
Can someone explain B?
take the count of l,r,d,u.
if((l+r+d+u)%2==1) ans is -1.
else
ans is (abs(l-r)+abs(u-d))/2;
Thanks! Awesome solution
why did you divide by two!
(abs(l-r)+abs(u-d))/2;To me, justabs(up-down) + abs(right-left)makes more sense! Any idea?!UPD: I got the idea, sorry for the inconvenience!
Assume that an L is a -1 while a R is a +1. Similarly for D and U. Find the absolute net vertical movement and the absolute net horizontal movement. There is three cases. Let vert = abs of vertical. hor = abs of horizontal then 3 cases are:
Case 1) vert==horizontal: Swap all horizontal to vert or all vert to horizontal, so answer is horizontal =vert Case 2) vert>horizontal: Two cases. Vert-horizontal is even or odd. If it is odd then answer is -1 because you can't make the odd go back to the origin. if they are even then the answer is (vert-horizontal)/2 + horizontal Case 3) Similar as case 2 but horizontal>vert. same logic.
Isn't it simpler just to output (vert + hor) / 2 when the sum (vert + hor) if even, and output - 1 otherwise? In fact, solution is equal to yours, but a little bit shorter.
Комментарий скрыт по причине большого числа негативных отзывов о нем, нажмите здесь для его просмотра
Round is very very exiting, thanks! Only I hate probability in fifth task :P
P.S. I think I won't return in div 1 soon :D
Haven't solve problems for a week and did a bad job in this round. Luckily it's unrated.
Regardless of the server issues and the round being unrated, I have to say, the problemset is really interesting....
How to solve D? I managed to come up with DP solution but it was too slow(by factor of k) and I couldn't get the complexity down.
use partial sum
UPD: This approach will get TLE. I didn't pay attention to complexity. My bad.
Let dp[i][j] be the number of ways of playing i turns such that first player receives atleast j extra points than second. Clearly answer would be dp[turns][b - a + 1].
For negative j, you can have another array dp2.
See my code
Okay, I did my dp iteratively and I guess by doing that I made too many unnecessary caluclations, but I tried doing it the same way, thanks!
isn't this O(t * k * sum) ? Won't that be too slow?
tags : offline increment, dp
let
dp[i][j]be number of ways to gey sumjafteriincrements. for everydp[i][j]we mast increment fromdp[i + 1][j - k]todp[i + 1][j + k]bydp[i][j]. how to do it quicly in O(1). offline increment. just incdp[i + 1][j - k]and decdp[i + 1][j + k + 1]bydp[i][j]. then for everyj (j > 0)dp[i + 1][j] += dp[i + 1][j - 1].so we have dp for
Aand forBnow let's find the answer. let's brute possibleAaftertincrements andif (dp[n][A] > 0) ans = ans + pref[A - 1] * dp[n][A], wherepref[i]is prefix-sum ofdp[n]forBthat is all. so it works in
O(t * mx)where mx ist * kthank you for explanation. I didn't understood the editorial, but your solution seemed easier to understand
This is what I did; let me know if you need any clarifications: http://codeforces.net/contest/712/submission/20515549
It was a nice round.
I think that there should have been a testing round after changing the data center.
Problem A is harder then usually
First of all, contest frequency has greatly reduced. If CF is conducting a round after 10 days, then atleast there should be both Div1 and Div2 contests. The questions were really very nice. I didn't expect the quality to be this good. Hope to see more contests from you @trashfirstsearch.
why it is not rated it should be rated because the technical error involved all participants???
No, I don't think so. For example, when I can load problem A, contest has started more than 10 minutes and a lot of participants AC two first problems!
I want to share one amazing solution for the third task :
20512612
can u please explain it?
I can not explane, I got two unsaccessful hacks on it :D
but it is amazing!
Then how did it came to your mind? :/ I mean what was the approach?
That's not his solution.
Some people still upvoted his comment.
I do.
Let's invert the process and go from small triangle to big one.
Proposal: If we can go from (y, y, y) triangle to (p, q, r) in T steps, and min(p, q, r) ≥ x, then we can go from (y, y, y) to (x, x, x) in T steps (or less).
Let's use following greedy strategy: if we have triangle (a, b, c), a ≤ b ≤ c, we will change it to (b, c, b + c - 1).
Proposal: if we start from (y, y, y) and use this strategy, after T ≥ 1 steps we will have (FT(y - 1) + 1, FT + 1(y - 1) + 1, FT + 2(y - 1) + 1) (FT being Fibonacci sequence). Proof: by induction.
So when we reach min(a, b, c) ≥ x? When fT(y - 1) + 1 ≥ x. As fT is integer, we want
. Linked solution finds exactly such T.
Cool proof !
I understood relation wih Fibonnaci sequence very fast, but I couldn't put - 1 in any of my formulas :)
Basically all +1 and -1 are due to triangle inequality a + b > c being equivalent a + b - 1 ≥ c in integer case. Which in turn is equivalent to (a - 1) + (b - 1) ≥ (c - 1). This problem is equivalent to problem when we allow degenerate triangles (e.g. a + b = c) after substracting 1 everywhere, i.e. original problem for (x, y) is degenerate-allowed-problem for (x - 1, y - 1).
Is there ever going to be a -1?
If x could be 1, then you could not proceed to any other triangle. But the contraint mentions that its not possible.
When x=1 => y=1 (As area is always positive). Answer=0, right? I know constraints don't have x=y=1, but even if there was, it can't be an invalid transformation.
I have added explanation below if you are interested.
Problem E: Quite ironically, 'Memory' couldn't recall its gender
It's genderfluid, m8
Genuinely surprised by the amount of AC's in C and D respectively. It appeared to me that D was much easier than C.
Does C really feature a simple and elegant solution to it? I feel like a retard looking at the number of successful submissions for this problem.
Yes. You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1.
Thanks. Never thought of looking at the problem that way :(
I agree with you. I think D is much easier than C. Simple solutions aren't necessarily easy.
Thank you send_nodes! I like it!
I feel that pretest for C is weak.
Another UNRATED contest!
Recent CF server problem is really taking a toll on everything :/ It totally decreases the enthusiasm and interest of the contest. Last few contests were really nice but this server failure is becoming a frequent issue now. I think the CF team should look into the matter and try to solve this quickly :(
How much time system testing takes ?
Codeforces servers
what does this circuit do?
Cooks potatoes
you know that you can use potatoes as a batteries, I once did that on a university project, but the circuit caught me curiosity, I am interested in such things, if you can understand what i mean :3
Can someone explain problem C. I tried a greedy solution but obviously it didn't pass even the third test case given so I didn't submit. Is it solved by DP?
you need the minimum number of steps to transfer an equal sides triangle to another equal sides triangle with length y and it has a greedy solution but in every step you should form a triangle so that a+b>c where a,b,c is the lengths of the sides
I did, but I got the wrong answer for test 3. (22,22,22) to (4,4,4) Using the greedy algorithm I got:
(22,22,22) (4,22,22) (4,19,22) (4,19,16) (4,13,16) (4,13,10) (4,7,10) (4,7,4) (4,4,4) but this solution takes 8 seconds not 6, the optimal solution.
You should make (x, x, x) from (y, y, y) using triangle inequality, it's a lot easier
Not sure if it's right or not but you can pass pretests by using the same approach with all possible values for the first side.
http://codeforces.net/contest/712/submission/20509385
It fails for 100000 3
Your code : 26
Actual : 25
Yep, it didn't pass system tests
You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1. :P
Why is this correct? I thought of this solution but didn't write it because I couldn't prove it was correct.
once u go from x to y, then u will figure out that this method is reverse of method y to x. it is like greedy. :)
Yeah I was hung up on trying to prove it too & I couldn't, but I wrote it anyway since it felt right. Here's a proof I have afterwards, it's a bit convoluted but main idea is just that each triangle in the reverse process is the biggest possible:
Let's always express a triangle is a triple [a,b,c] with a <= b <= c.
Note first that it doesn't matter which way we go: the optimal number of modifications will be the same going from [x,x,x] to [y,y,y] as with [y,y,y] to [x,x,x].
We'll compute the [y,y,y] to [x,x,x] sequence.
The procedure is to start from [a,b,c] = [y,y,y] and then each step you transform triangle [a,b,c] into [a',b',c'] = [b,c,b+c-1]. You keep going till the maximum side length is >= x. The answer is (# of transformations)+2.
A sequence of modifications that achieves this answer: do the same sequence of transformations, except in the last step, make the largest side x (instead of whatever b+c-1 >= x). Then in additional steps, modify the other 2 sides to equal x.
Proof this answer is optimal:
Property: our transformation [a,b,c]->[b,c,b+c-1] generates the "biggest" of all possible triangle that can result from modifying [a,b,c].
That is, any triangle [d,e,f] that can be produced by legally modifying some side of [a,b,c] is "smaller" than our transformed triangle [b,c,b+c-1]:
d <= b, e <= c, f <= b+c-1.
Formally, this property is true because you're only allowed to change one side per step. So at least two of the the original sides of the triangle must remain in the new triangle: this means d <= b and e <= c. (to be sure of this you can check all three cases: a & b remain, a & c remain, or b & c remain: in any of the cases, the smallest side must be <= b, and the second smallest must be <= c).
To bound f, we can use the triangle inequality & the bounds we have for d & e:
f <= d+e-1 <= b+c-1.
So [b,c,b+c-1] is indeed the biggest possible new triangle.
Applying this property inductively, we see that the triangle produced after k of our transformations from a start triangle [y,y,y] is larger than any other triangle that could have been produced after k modifications from [y,y,y] (any other sequence of k modifications will produce a smaller triangle at each step)
Now we can show that (# transformations)+2 is optimal for [y,y,y] to [x,x,x] with x > y: let k be the number of transformations we did in our process.
By the optimality of the triangle in step k-1, we know that any triangle that is k-1 modifications from [y,y,y] has maximum side < x. This means you need at least (k-1)+3 = k+2 steps to get to [x,x,x]: after any k-1 steps, each side is strictly smaller than x; so then you're going to need at least one extra modification on each side to get to [x,x,x], which is >=3 extra modifications overall; so at least (k-1)+3=k+2 modifications are required to get to [x,x,x], which is what we wanted.
just do brute force...
define all sides=y... increase the smallest sides by maintaining positive area.. while akk the sides are not x, do this operation..thats it..
I did greedy . start with triangle of side Y and in every move pick the shortest side and set it to min(X,sum of other two sides-1) . Break when one of the sides reach X .
Try the greedy solution from backwards.I mean try to get (x,x,x) from (y,y,y). Here is my code : http://codeforces.net/contest/712/submission/20513444
It can be solved simply by taking kinda Fibonacci nos. type of approach.Something Like
arr[i]=arr[i-1]+arr[i-2]-1
It's trivial that a+b<c for a valid triangle, at any time during the transition phase. And, trivially it's observable that whether I go from larger to smaller triangle or vice versa the answer is the same. Hence, if the input is
28 3 The sequence shall be :
3 3 5 7 11 17 28
Rest, is here ..
http://codeforces.net/contest/712/submission/20508329
I think problem E can be solve by SegmentTree. Each node[L, R] consider x is probability dominate [L, R], y is probability to start at R finish by winning at R and never lose at L, then the formula we need to merge two nodes a, b is: result.x = a.x * b.x / (1 - a.y + a.y * b.x), result.y = b.y + (1 - b.y) * a.y * b.x / (1 - a.y + a.y * b.x).
I can confirm for result.x:
which is
which simplyfies to precisely your formula.
I can confirm for result.y too, since it is based on the same reasoning for result.x. Nice idea!
bop turad.
the problems are very nice,but Unfortunately.it's unrated..what a pity...anyway,thanks for prepare the problems
Is it possible to solve 712D - Memory and Scores using Irwin-Hall distribution?
When will pending system testing end ?
If you click on the "problems" tab, the testing progression will show on the right — that should give you some gauge. Generally it also hangs up for a bit when it reaches 100%.
I was about to finish writing Sqrt Decomposition solution for E, but I didn't make it. ;(
Почему я не могу посмотреть тесты на посылку на дорешивании? http://codeforces.net/contest/712/submission/20514680
I was a bit delayed with DIV2-D because I don't understand the behavior of MOD very well. I initially applied it in cases where it should not be (in some of the intermediate calculations).
Can someone share any resources (or explain themselves) briefly how we should think about MOD-ding results? If there are some clear rules, e.g. "MOD-ding in cases X, Y, Z will affect the final result (e.g. if you just MOD-ded the final result after doing all the calculations, it would be different), so don't do it, but in cases A, B, C it's fine" — those would be helpful to know.
Can Div2. D be solved using a top-down dp?
Auto comment: topic has been updated by send_nodes (previous revision, new revision, compare).
Auto comment: topic has been updated by send_nodes (previous revision, new revision, compare).
Pretty interesting problems where I have learned a lot. Maybe it will be more funny when it's rated? :)
Can someone explain, how's number of games played will be (2*k+1)^(2*t) ??
It's (2*k+1) choices for every player in every turn. Hence that number.
2t because t is for each player. Therefore, at the end of the game, the number of ways to choose will be like this:
[ (2k+1)*(2k+1) ] * [ (2k+1)*(2k+1) ] * ...... t times
*2k + 1 * because we must separately count 0.
such fucky