Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

romanasa's blog

By romanasa, 4 years ago, translation, ,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #329 (Div. 2). It'll be held on Wednesday, November 4 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Writers are Stanislav Naumov (josdas) and Roman Korobkov (romanfml31). There will be 5 problems and you'll have 2 hours to solve them. I hope you enjoy the problems.

Great thanks to GlebsHP (Gleb Evstropov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon.

The scoring distribution will be announced later.

Good luck and high rating!

UPD: The round will use the dynamic scoring with 250 points step.

UPD2: Editorial

Tutorial of TEST

• +124

 » 4 years ago, # |   -14 gl & hf!
•  » » 4 years ago, # ^ |   +62 I'm so sorry, it seems like no one enjoys this problems...
•  » » » 4 years ago, # ^ |   +5 No one except div1 guys and div1 guys with div2 accounts :D
•  » » » » 4 years ago, # ^ |   +19 There are even some Div1 contestants that can't solve these problems
 » 4 years ago, # |   +11 hope to see short statement .... and good luck to every one :)
•  » » 4 years ago, # ^ |   +13 short statements are not always clear , right?
•  » » » 4 years ago, # ^ |   +1 Short Clear Statements*
•  » » 4 years ago, # ^ |   +6 Shortest doesn't mean the simplest :D
 » 4 years ago, # |   +64 Is there any punishment for those who doesn't write this,"thanks to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon." in their contest blog???,, Just curious to know..!!!
•  » » 4 years ago, # ^ | ← Rev. 3 →   +21 Look at the previous contest description. It is quite concise and yes, it doesn't include the phrase. So ask galois, I hope he is able to answer after that:)
 » 4 years ago, # |   0 Good Luck!
 » 4 years ago, # |   -33 Your text to link here... How can i solve this problem....Editorial of this problem says "Binary search over the answer. With a fixed length now try to count three values over the whole string from first to last, number of ^ found, number of ^_ found and number of ^_^ found."...I have already faced that kind of problem twice in the contest area......both time i was fail to solve this...if you can...then please give me a correct solution for this problem....thanks!
 » 4 years ago, # |   -16 Does anyone want to guess how long will system testing take? What about rating changes? Hopefully they won't take very long.
 » 4 years ago, # |   0 is this contest was in gym before :D see tags Tutorial of ыфф Announcement of Либо баг, либо фича. Announcement of Короб лучший Discussion of Короб не голубой
•  » » 4 years ago, # ^ |   +8 As I understand anyone can attach any phrase to blog if he creates mashup with this name. :)
 » 4 years ago, # | ← Rev. 2 →   -14 Excited!!My First Contest On CodeForces.
•  » » 4 years ago, # ^ |   +39 Exited!! It should be excited instead.Sorry for being picky :)
•  » » 4 years ago, # ^ |   0 Welcome to codeforces :).Wish you best luck!!!
•  » » 4 years ago, # ^ |   0 welcome bro
 » 4 years ago, # |   +3 Why?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 And the last 5 link are linked to this page :-| And i can't read russian and is there any one to tell me what does they mean?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 It says "You are not allowed to view the contest" when I click on the links. Does anyone one know why?
•  » » 4 years ago, # ^ |   +23 successful hack
 » 4 years ago, # |   +1 First round from blue coder?)
•  » » 4 years ago, # ^ |   0 Color revolution
•  » » » 4 years ago, # ^ |   0 division revolution !!
•  » » 4 years ago, # ^ |   +7
 » 4 years ago, # | ← Rev. 3 →   +4 Hello all, why are regular rounds not scheduled for the weekend if possible? It seems that by moving contests to the weekend, more people (especially students or employees of different time zones) could participate.Thanks, and I hope everyone enjoys this round.
•  » » 4 years ago, # ^ |   +4 weekend itself isn't a common thing :D
 » 4 years ago, # |   +22 Hope see good translation :3
 » 4 years ago, # |   +2 completing whole contest, hacked on A being like :'D
•  » » 4 years ago, # ^ |   +6 ┬─┬ノ( º _ ºノ)We learn from our mistakes :)
 » 4 years ago, # |   +27 Am I the only one who thinks its funny that fml stands for f*** my life :pSorry romanfml31.
•  » » 4 years ago, # ^ |   +19 lol. Physics and Mathematics Lyceum. In russian language "fiziko- matematicheskiy litsey"
•  » » » 4 years ago, # ^ |   0 Haha :D
•  » » » » 4 years ago, # ^ |   +9 Nothing H-HUMILIATING about it then ;)
•  » » » » » 4 years ago, # ^ |   +3 My avatar is about color revolution, I didn't change it just to write a comment ;)
•  » » » » » » 4 years ago, # ^ |   +3 Hey!!! Blue is not humiliating
•  » » 4 years ago, # ^ |   +12 Actually it means: ФизикоМатематический Лицей (Physics and Mathematis Lyceum) -> ФМЛ -> FML -> Well :D
 » 4 years ago, # |   +3 Why dynamic scoring :'( why why
•  » » 4 years ago, # ^ |   +6 What does dynamic scoring mean?
 » 4 years ago, # |   +15 Problems will be sorted by expected difficulty or shuffled?
•  » » 4 years ago, # ^ |   +11 Problems will be sorted by expected difficulty
•  » » » 4 years ago, # ^ |   0 But it was random :|
 » 4 years ago, # |   +16 shocked it seems that "The score distribution will be announced later" better than early announcement with dynamic score :(we can wait man :D
 » 4 years ago, # |   +8 Best wishes to all participants !By the way, Soccer fans will be happy cuz there will be European champions league after the contest:)
 » 4 years ago, # |   0 What about order of problems? Are they will be sorted from easy to hard by authors? Or random?
 » 4 years ago, # |   +6 It's okay too be dynamic scoring, but I hope the round will not be the battle of speed.
 » 4 years ago, # |   +13 short Blog = Long problem :| (I I learned from contest 328)
 » 4 years ago, # |   0 In fact, why is the scoring distribution "announced later" every time?
 » 4 years ago, # |   +12 The site is quite slow now, my solution was being evaluated for something like 5 minutes and when I want to click on some link it loads longer than it usually takes. I hope this will not be the case during the contest, at least :)
 » 4 years ago, # |   +1 For being good in dynamic scoring contests it is very good to solve first problem B or C but it is a big risk because if you don't solve it fast or wrong then the contest will go on very bad. You can choice to risk or not BUT I THINK DYNAMIC SCORING CONTESTS ARE NOT GOOD FOR TESTING CODING ABILITIES !!!!
•  » » 4 years ago, # ^ |   +3 If you solve all five problems in any order and in any time I guarantee you will do good in the contest and get a big rating increase.
•  » » 4 years ago, # ^ |   +3 If you solve all five problems in any order and in any time I guarantee you will do good in the test and get a big rating increase.
 » 4 years ago, # |   +26
•  » » 4 years ago, # ^ |   +19 Better than lags for all contest.
•  » » » 4 years ago, # ^ |   0 Как дела?
•  » » » » 4 years ago, # ^ |   0 Вообще четко, жду, как и все.
 » 4 years ago, # |   +3 Delay as expected!!!
 » 4 years ago, # |   0 Hope I will solve atleast one problem today!
 » 4 years ago, # |   -50 10 min delayOK, I don't participate
•  » » 4 years ago, # ^ |   +88 Nobody cares.
•  » » » 4 years ago, # ^ |   -18 waste your fucking life with more delays
•  » » 4 years ago, # ^ |   +17 Thank You :) You just increased my probability of getting a higher rating :D
•  » » » 4 years ago, # ^ |   0 you're welcomeall your's
 » 4 years ago, # |   +5 It's loading really really slowly...
 » 4 years ago, # |   +1 Delay again ????
•  » » 4 years ago, # ^ |   +11 TC admins are DDOSing CF ^^)
 » 4 years ago, # | ← Rev. 3 →   +6 .
 » 4 years ago, # |   +8 Do you guys think its a good idea to participate in a contest when you're sad about something in your life?
•  » » 4 years ago, # ^ |   +1 I think it is one of the best ways to relax and forget about problems(not CF, problems of life=)).
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The delay got me thinking...... maybe today I should pass it....but you guys have a point.
•  » » 4 years ago, # ^ |   0 In my opinion sometimes concentrating on something amusing like a contest can make your mind have a useful distraction from annoying thoughts !
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Cf contests makes you forget all your problems and just think about the problem..
•  » » 4 years ago, # ^ |   0 Being sad => After a while => Becoming Angry + Mad at the world => Trying to get revenge or prove yourself => Feeling competitive => Doing a good contest => Going to Div.1 => Feeling AWESOME! :P
•  » » 4 years ago, # ^ |   0 No. You won't be focused as you expect.
•  » » 4 years ago, # ^ |   +1 "Be Obsessed. Do something which you are passionate about. Do it because you love to do it. Everything else is secondary."
 » 4 years ago, # |   +19 It looks like we should donate again.
 » 4 years ago, # |   +3 what an unruly contest!!!:(
 » 4 years ago, # |   +54
•  » » 4 years ago, # ^ |   +22 dynamic delay
•  » » 4 years ago, # ^ |   +46 wtf am I doing in this stupid hentai picture?
 » 4 years ago, # |   0 CONTEST IS BEGINNING LATE! 10 MINUTES DELAY :/What's wrong?
•  » » 4 years ago, # ^ |   0 Not 10 minutes,AlreadY 15 minutes.
 » 4 years ago, # |   +1 AlreadY 15 minutes late. After system testing....................?
 » 4 years ago, # |   -6 Thanks for the delay ;) I had talked with my gf 10 minutes more :D
 » 4 years ago, # |   +1 delayed why?
 » 4 years ago, # |   +18 The longest delay everrrrrrr. :/
 » 4 years ago, # |   0 15 min delay. wow
 » 4 years ago, # |   +10 You mean: "as usual Div. 1 participants can join with fake accounts"Bec that always happens in every Div. 2 only contestsThere are more than 750 new accounts participating this Contest!Many contestants are honorable and participate as "out of competition"But unfortunately some of them are not!
•  » » 4 years ago, # ^ |   0 How cares about that!!! It is their business. I am focus on my own performance.
 » 4 years ago, # |   +9 delayed 10 mins delayed 5 mins
 » 4 years ago, # |   0 is there going to be another delay??
 » 4 years ago, # |   +32 Unknown language round?
 » 4 years ago, # |   +70 These Problems should be in Div.1.
 » 4 years ago, # |   +66 Is it div 2 or div 1?? I am confuse.
•  » » 4 years ago, # ^ |   +55 Div2 contest with Div1 problems :(
 » 4 years ago, # |   +55 what a HARD contest !!!
 » 4 years ago, # |   +20 contest is hard or I very weak :|
 » 4 years ago, # |   +30 Not complaining, but there's a reason why there is a separate category on CF here called Div 2.
 » 4 years ago, # |   +22 A very steep difficulty curve indeed..
 » 4 years ago, # |   +39 Bad contest :|
•  » » 4 years ago, # ^ |   +11 dynamic scoring is a nightmare
•  » » » 4 years ago, # ^ |   -8 The worst contest I've ever seen, it couldn't be worse. Sorry for my bed English :(
•  » » » » 4 years ago, # ^ |   +110 you mean this ?
 » 4 years ago, # |   +41 div 2 ????!!!!
•  » » 4 years ago, # ^ |   0 :)
 » 4 years ago, # |   +31 OMG!!! C problem with 3000 pts
•  » » 4 years ago, # ^ |   0 Dynamic scoring.. :/
 » 4 years ago, # |   -46 The new coordinator sucks. :)
 » 4 years ago, # |   +2 What a hard contest! I couldnt solve even problem A completely! This is frustrating and I lost 150 points in resubmissions!! wtf
 » 4 years ago, # |   +12 Respect to Problem C!
•  » » 4 years ago, # ^ |   +4 How to solve B?
•  » » » 4 years ago, # ^ |   0 so easy, just sort!
•  » » » 4 years ago, # ^ |   0 put each line intersecting with line x1 and x2 in a vector pair then sort it and iterator from the begining to end and find the solution.
•  » » » 4 years ago, # ^ | ← Rev. 13 →   +20 If you try a brute force method of checking each pair you wont pass because its a O(n^2) algorithm.Instead of lines think of them as line segments from X1 to X2You have to find the y intercepts at X1 and X2. Create a pair vector of the form { line_number , X1_Y_intercept} Create another pair vector of the form { line_number , X2_Y_intercept}Sort them both based on X1_Y_intercept and X2_Y_intercept.Now if the ordering of the line_number is the same in both vectors then there is no intersection else there is an intersectionUPDATE : Since I got lot of upvotes I thought I shall make it clearer by an image
•  » » » 4 years ago, # ^ |   0 oh and make sure to use long long (unlike me) cuz input may overflow integers
•  » » » » 4 years ago, # ^ |   0 Shit ... Im screwed :/
•  » » » » 4 years ago, # ^ |   0 el3el2, and make sure to use doubles cuz input can be decimals too :D Problem B. Anton and Lines ***** x' is NOT guaranteed (and is NOT required) to be integer 
•  » » » » » 4 years ago, # ^ |   +1 That just means the points of intersection need not be integers. The input is all integers. They just wanted to discourage trying to go through the x-axis checking whether two lines cross at that vertical line.
•  » » » » » 4 years ago, # ^ |   0 no, that's the "intersection"; which is neither the input nor the output. I actually got AC 30 sec after system test was done and content was open for practice. Touch luck.
 » 4 years ago, # |   +24 Thank God that contest has finished
 » 4 years ago, # |   +5 i enjoyed this div-1 contest....!!!!!
 » 4 years ago, # |   0 I think this contest is like a Div-1 contest.
•  » » 4 years ago, # ^ |   +6 Not really Div 1 problems are hard but these problems are ugly !
 » 4 years ago, # |   +22 I feel bad for the people who are taking part for the first time. They will probably think Div 2 people are expert programmers after seeing such problems :P
•  » » 4 years ago, # ^ |   -12 Interesting how you are more concerned about the fact of whether DIV2 coders are expert or not. You are supposed to be worried about the expression it would have on them after a relatively not so simple contest. I think you are a narcissist, egotistical maniac.
•  » » » 4 years ago, # ^ |   0 That was.. Quick..
•  » » » » 4 years ago, # ^ |   0 Yeah I noticed
 » 4 years ago, # |   +11 Geometry contest ?
•  » » 4 years ago, # ^ |   0 NOOOOOOOO. line equation. :)
 » 4 years ago, # | ← Rev. 2 →   0 How to solve B?I solved x = (b[j]/(k[i] — k[j])) — (b[i]/(k[i]-k[j])) and check if x > x1 && x < x2 and got TLE on test 16.
•  » » 4 years ago, # ^ |   0 Something like this (lines[1,...] — k, lines[2,...] — b): temp1:=lines[1,i]-lines[1,j]; temp2:=lines[2,j]-lines[2,i]; if temp1<>0 then temp3:=temp2/temp1 else temp3:=0; if (temp3x1) then .... And TLE too...
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 This is my ideaI have two vectors where I save the interception with x1 and x2 for each line. The tricky part is that I am saving in the vector a pair> where the first element is the y_intercept value and the second value is a vector with the other y_intercept and the index of this line in the input.Then, I sort both arrays and for each element from the sorted array, I check if it is the same element. If at position i, there is not the same index line then, we have an interception between 2 lines. If the order in both arrays is the same, there is no interception between any two lines.I hope this solution passes the systest. PS: PASSED SYSTEST, LOL!!!!!
•  » » 4 years ago, # ^ |   +6 This Image should explain it :)
•  » » 4 years ago, # ^ |   0 try it with long long int :D
 » 4 years ago, # |   +14 Lets hope Arsenal wins today. Its already a bad day after such a hard contest.
•  » » 4 years ago, # ^ |   0 beaten handsomely mate
 » 4 years ago, # |   0 15 minutes delay + dynamic scoring + extremely difficult problems -> a disaster!
 » 4 years ago, # |   -6 Even O(n^2) solution passed B . I lost a few points trying to hack, not cool at all :)
•  » » 4 years ago, # ^ |   +5 how O(n^2) pass?
•  » » » 4 years ago, # ^ |   0 it is an old trick. they just check the first 6000 elements... if YES print yes else it prints no (because these tests are made by system).
•  » » » » 4 years ago, # ^ |   0 LOOOL, WHAT.
•  » » » » » 4 years ago, # ^ |   0 99% the answer is no when the answer is no in 6000 elements.
•  » » » » 4 years ago, # ^ |   +8 so they may TLE in system test?
•  » » » » 4 years ago, # ^ |   +3 It's easy to make hacks for those solutions, though.
•  » » » » » 4 years ago, # ^ |   0 I made a case where the input consisted of 1e5 parallel lines, but the solution passed in about 850s . However, someone else hacked it using increasing slopes lines.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Mmh I was talking about the "N^2" solutions that only consider first K points for some K. By the way, take a look at the loop conditions in the submission you tried to hack, specifically the inner loop in solve(): 14073024. It doesn't actually run for N^2 operations on the case you tried. Looks like the author's two mistakes (doing N^2, but with incorrect implementation) cancelled each other out on your specific test case. :|
•  » » 4 years ago, # ^ |   +8 no it got TLE
•  » » 4 years ago, # ^ |   0 No, solutions that have O(n^2) time complexity didn't pass system test, and it failed also when checking just the first 6000 elements .If you saw such a solution please link to the submission .
 » 4 years ago, # |   -6 hahahahahahahahahahahahahahahahah
 » 4 years ago, # |   +1 How to solve Problem-D?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Just some thoughts. You can observe that you need to divide Y by at most O(log(MAX_VALUE)) numbers greater than 1. So now I think you can use HLD to quickly answer queries "Which is the next number in this chain which is greater than 1?". However, I didn't implement that. And a friend of mine told me we can solve it using LCA-like approach (with powers of 2) with union-find but I don't really understand that :D
 » 4 years ago, # |   +9 Participated in div1 in a div2-only contest.
 » 4 years ago, # |   +1 I had never spent this much time on Div 2 B Nice problem :)
 » 4 years ago, # |   +17 What a hard contest:problem A: harder than usual, took me >10 minutes to solve it.Peoblem B: Passed pretest with ~0.6 seconds. I'm not sure if python can pass 1 second time limit with full 100K input.Problem C: Are you kidding? I have no idea how to solve it.Problem D: I know it's HLD but I never and can't implement it.Problem E: Time to learn C++! ugh getting compilation error. :p
•  » » 4 years ago, # ^ |   +8 Seems problem D can be solved by DSU and LCA.
•  » » 4 years ago, # ^ |   +1 not sure if python solution for B will pass for given time limit. yeah, time to learn C++ seriously.
•  » » » 4 years ago, # ^ |   -7 Python is good at developing real world applications C++ is good at competitive Coding
•  » » 4 years ago, # ^ |   +5 Even using HLD problem D is very tricky. I thought pre-computing the multiplication of the edges and use HLD but... Xi <= 10^18 :(
•  » » » 4 years ago, # ^ |   0 The Yi<=10^18,too.Maybe you can limit the multiplication of the edges in 10^18:p
•  » » » 4 years ago, # ^ |   +12 This could be avoided by carefully checking for overflows. Take a look at my solution: http://codeforces.com/contest/593/submission/14073334 (lines 256-258, or ctrl+f "__builtin_smulll_overflow"). I think you could also replace the check ab ≥ 2 × 1018 with something like .But yeah, avoiding these kind of overflows is definitely not fun and I think it would have been better to put limits of the form x ≤ 109 instead of x ≤ 1018.
•  » » » » 4 years ago, # ^ |   +5 :o I didn't know about that function! Thanks :D
•  » » 4 years ago, # ^ |   +5 Can anyone explain DSU-LCA approach for problem D?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 I never thought this solution in contest-time but I'll try to explain:If node a and node b has edge weight = 1 you can merge node a and node b since multiplying or dividing by 1 has no effect.Otherwise because edge weight is an integer so number of multiplication or division will not exceed ceil(log(10^18)) = 60 operation. I guess this can be done without LCA(?), just save the parent and depth of a node(?)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You must have LCA. How else could you tell how far should you traverse up the tree?Edit: My bad — you don't need an LCA.
•  » » » 4 years ago, # ^ |   +3 First observation is that if you keep dividing y, you'll quickly get 0. (Of course, if you divide by a number bigger than 1)This is the basic idea // a path from a to b. Initial value is y. lca = getLca(a, b) while (y > 0 && depth[a] > depth[lca]) // an edge e connects a and a's parent if e.weight > 1 y /= e.weight a = parent[a] else a = parent[a] // *** // do the same thing with b This is too slow because of *** part. It's too slow when we have a lot of edges whose value is 1. Basically, we want to skip all edges whose weight are 1.For that we can use DSU. Initializing... (This must be done before processing query) for each node u for each child v of u if e(u,v).weight == 1 g[v] = find(u) Every time you update the cost, we can do the same. // update an edge e = (u, v). u is a parent of v. // new cost = c if c == 1 g[v] = find(u) 
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone please explain why this output is wrong for C: (0+(t-1)*(10+0*(t-2))) (10+(t-1)*((0-10)+10*(t-2))) I consistently got WA in pretest 1 and I think pretest 1 must be the sample.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 10 + 0 * (t - 2) is invalid, it should be 10 + (0 * (t - 2)). Look at the examples under the testcases.
•  » » » 4 years ago, # ^ |   0 You are right.
•  » » » » 4 years ago, # ^ |   -16 I'm always right!
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 You aren't right always, correct is only: (10  +  (0  *  (t  -  2))) (without spaces of course)
•  » » » » » » 4 years ago, # ^ |   +9 I'll go sit in a corner and be quiet now.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Okay, let me see
 » 4 years ago, # |   +6 TodaY most of the hacker are <=300. (Hacked B).
 » 4 years ago, # | ← Rev. 2 →   +9 18 solutions for problem C, seriously?
•  » » 4 years ago, # ^ |   +3 I was not able to solve B :3
 » 4 years ago, # |   +67 this my first div1 contest
 » 4 years ago, # |   0 How to solve problem D?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 Notice that we will pass not more than ~64 edges with something greater than 1 written on them. Therefore, the only thing we need to do fast while travelling on a tree is to pass sequences of edges with 1 written on them (because they don't change your yi anyhow). This can be done by DSU — merge two adjacent vertexes (u, v) if you get request "write 1 on (u, v) edge, and simply update number on edge if the number  ≠ 1. Also you need to update the topmost vertex for this set in DSU. Now we answer on every request by checking if there are more than 64 numbers on path  ≠ 1 or by finding all these numbers and consequently applying all the divisions to yi.
 » 4 years ago, # | ← Rev. 3 →   +117 .
•  » » 4 years ago, # ^ |   +3 I'm dying :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 LOL me too. I was hoping I could hack someone like me. xD You should have been in my room.
•  » » 4 years ago, # ^ |   +3 отличные претесты. Можно было что угодно запихать
•  » » » 4 years ago, # ^ |   +18 Delinur please translate to english. :)
•  » » 4 years ago, # ^ |   +1 hahahahahh .... are you serious :D ?
 » 4 years ago, # |   +4 It is sad, but I have to downvote :(
 » 4 years ago, # |   0 Don't even care about the system testing. :D
 » 4 years ago, # | ← Rev. 3 →   +18 Kudos for problem C! I spent the whole first hour writing my solution, and I'm still a bit worried about the full system tests, but I really liked it. I'm really fond of problems where you have to construct an object that satisfies certain properties, no bullshit 'find the shortest path with a twist' problems, but something you actually have to think about.EDIT: yay, passed the systests! It also seems my solution finds much shorter answers than the jury solution :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I tried to use polynomial interpolation on the axes independently, what did you do? I dont understand the part of your code where you are taking modulo 50
•  » » » 4 years ago, # ^ | ← Rev. 6 →   +4 I exploited this function: W|A plot. It's zero for all x ≤ c and for x > c it satisfies f(x) = 2(x - c). In other words, this function only becomes relevant after position c. Let's denote this function by fc(x). If you pick for your function g(t) = a0 + a1 * f0(t) + a2 * f1(t) + a3 * f2(t) + ..., then this function will satisfy g(0) = a0, g(1) = a0 + 2 * a1, g(2) = a0 + 4 * a1 + 2 * a2, g(3) = a0 + 6 * a1 + 4 * a2 + 2 * a1. If you pick your coefficients ai appropriately, you can reach any even value you want (or equivalently, exclusively odd values if you pick a_0 odd). Since the cirles have at least radius 2, this is sufficient jump into any circle.I also thought about polynomial interpolation but the fact that you couldn't do division was a bit unfortunate.EDIT: As a bit of background, the idea for this came from the beautiful identities: max(a, b) = (a + b + |a - b|) / 2 min(a, b) = (a + b - |a - b|) / 2(verify this yourself! hint: consider $a \geq b$ and separately)It would be great if you could use these functions directly so you could make the step function max(0, min(1, x - c)), but unfortunately we cannot divide by 2, so this step function would make jumps of size 4. So I dropped the minimum, ending up with f as described above. Then you have to mess around with your coefficients, and poof you have a working solution!
•  » » » » 4 years ago, # ^ |   0 Nice solution :D I'll try to implement this
 » 4 years ago, # |   +187 Sorry community, I must accept that this round was too hard for div. 2. I will try to better evaluate the difficulty in the future.
•  » » 4 years ago, # ^ |   0 I have 1 suggestion for C: Why do you need to have so many brackets? I don't think it is that hard to write judge that works without those extra brackets, but it makes life of contestants much easier.The problem is already quite hard, and you're making it much harder for contestants that could come up with some complicated functions but failed to insert brackets correctly.
 » 4 years ago, # |   +4
 » 4 years ago, # |   +7 Ok, you should definitely lower Div2 problem difficulty... Problems A and B were excellent. Problem C... i don't even know what to say about problem C. It's difficult to even understand what is asked. Problem D should at least move to most difficult and problem E is for Div1 ...This is my humble opinion, but i think others will agree.
 » 4 years ago, # |   0 D was standard HLD. Just the overflows had to be taken care of. But how to approach E?
•  » » 4 years ago, # ^ |   +3 I think it doesn't need HLD.
•  » » » 4 years ago, # ^ |   0 May be there are simpler approaches, but what came first to my mind was HLD.
•  » » » 4 years ago, # ^ |   0 Can you please explain how to solve it without HLD?
•  » » » 4 years ago, # ^ |   0 How did you approach D? and what is the intended solution of E?
•  » » » » 4 years ago, # ^ |   0 E: (I'm using zero-based index, which is different from problem statement)This can be solved by dynamic programming with matrix multiplication.In a nutshell, make a vector V that keeps the number of ways to get to each cell and make a square matrix C such that C*V is the information about 1 second later. And basically keep doing (C^n)*V with some changes on C. Here is a more detailed solution.Let f(i, j) = i * M + j. (This maps location (i, j) to an integer, and it's bijective.)First make a column vector V such that f(i,j)th element has the number of ways to get to (i, j) at some point. Initially, V is filled with zero except f(0,0)th element is 1.(Because we have 1 way to be at (0, 0))And make a square matrix C whose size is (N*M) x (N*M). Fill 1 in matrix C such that C*V is going to be a column vector such that f(i,j)th element has the number of ways to get to (i,j) 1 second later. More specifically, for each (i, j), we need to fill C[f(i,j)][f(i',j')] = 1 if you can move from (i',j') from (i,j).Now to get the information of n seconds later, we just need to calculate (C^n)v. (C^n) can be calculated very fast by using Exponentiation by squaring. Cats can be handled by changing the elements in C. When a cat shows up at (i, j), every element of f(i,j)th row of C is going to be 0.
•  » » » 4 years ago, # ^ |   0 Can you explain how to solve it without HLD?
•  » » » » 4 years ago, # ^ |   0 http://codeforces.com/contest/593/submission/14078235Check it out. :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Solution without HLD.First observation is that you need to make at most 60 / with numbers >1 to make it 0. I note 1 edges>1 and 0 edges=1.So I want all 1's on path from a to b,if there are more than 60,the answer surely is 0.So starting from a,b I go to lca and should have a function that gives the first ancestor of x that has 1 to have no more than 60 steps on each query.The brute force is using disjoint sets.The problem is the updates on edges,but update is of form x[pi] to ci with ci
 » 4 years ago, # |   0 System testing please?
 » 4 years ago, # |   +4 lol i wish this contest as unrated
 » 4 years ago, # |   +3 Too hard for me... Only able to solve the first problem.
•  » » 4 years ago, # ^ |   +12 And failed on the system test..... :(
 » 4 years ago, # |   +1 Maybe stupid question, but how solve A? :)
•  » » 4 years ago, # ^ |   +1 Try all of the combinations of two letters and check what length of the text we'll have if we take only words with these letters :-)
•  » » » 4 years ago, # ^ |   0 Thx :) I have tried more complicated way: bruteforce only those pairs of letters that used in text. But I have not enough skill to implement)
•  » » 4 years ago, # ^ |   +1 Count the maximum number of words that can be formed with every pair of letters
 » 4 years ago, # |   +17 I_love_Hoang_Yen didn't solve C :'D and I am expected to?
 » 4 years ago, # |   0 What is wrong with this approach for B?Take xi = x1+EPSILON and xf=x2-EPSILON for EPSILON = 1e-7. Find the indices of the lines with the highest value at xi and xf. If these indices are the same, print NO. Else print YES.
•  » » 4 years ago, # ^ |   0 Draw two intersecting lines and then draw another one well above them.
 » 4 years ago, # |   0 This contest was...WA
 » 4 years ago, # |   +1 seems I miss great contest!
 » 4 years ago, # |   0 Editorial?
 » 4 years ago, # |   +18 2 solved problems + 2 hacks = 67 place. NICE.
 » 4 years ago, # |   +8 Can codeforces show recent comments at the top instead of bottom of the page. We need to scroll down to find recent comments.Also it would be best to too negative comment all together as it doesn't serve much purpose on this forum.
 » 4 years ago, # |   +10 Are there any a, b, c such as [[a/b]/c] != [a/(b*c)]?
•  » » 4 years ago, # ^ | ← Rev. 4 →   +13 No. Let be the remainder of after division by , so we have and such that . Then . Now let be the remainder of after division by , so we have and such that . Note that , since . Then , and since , . So .
•  » » » 4 years ago, # ^ |   0 After that announcement I decided that HLD was bad idea)P. S. To be honest I didn't even try to implement it.
 » 4 years ago, # |   +6 The thing I liked the most is "Yes" and "No" were case insensitive. :D
 » 4 years ago, # | ← Rev. 2 →   +9 Could have had such a good rating ... Problem B...Failed System Test...changed int to long long int...Got Accepted :'(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 I feel the same way with such stupid mistake. On D i have MAX=1e18+1 instead of MAX=1e18 and that made my program fail system tests.
 » 4 years ago, # |   +5 I miss PrinceOfPersia 's contests :D
•  » » 4 years ago, # ^ |   -16 excellent contest provider ♥
 » 4 years ago, # |   +23 I wonder how many solutions of problem E fails at this test case:5 4 100001 1 1 i*10000 + 100There is no restriction in the statement that forbids using this test case, right?
•  » » 4 years ago, # ^ |   -7 I don't see what is special about this case?
•  » » » 4 years ago, # ^ |   +28 Yes there is nothing special about it. It is just an ordinary maximal test case. For instance, your code with that input, gets TLE on custom test.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +11 You are right. It seems either the test cases are extremely weak, or the constraints and restrictions are misleading. Here's a more extreme version of the worst test case:5 4 10000(Followed by 10000 lines, i = line number)1 1 1 i * 200000I can pass this in 3 seconds but my implementation is heavily optimized. I'm certain most solutions will fail in this case. I got accepted in 156 ms and that's a joke, considering I can generate test cases quite easily where it takes > 3 seconds.
 » 4 years ago, # |   0 problem D A Big Trouble I use quick_mul to judge the num is exceed 1E18 or not,and this solution has no accuracy error!But someone may use log function to solve the problem,but we know the double only has 15~16 bits of accuracy,but the problem can have 18 bits,so this solution has no accuracy error! When I submit my solution,I get WA.Just a big data,the answer requires 0,but I output 1.But I think whether my answer is wrong.Because if standard procedure use log,I think may the data is wrong because of accuracy! So does everyone know standard procedure uses which method?
 » 4 years ago, # |   0 I didn't accept no one problems.This round was not Div2
 » 4 years ago, # |   +6 This contest was very difficult, but I must admit I overthink problems like B :( always seeing "geometry" problems like demons ...
•  » » 4 years ago, # ^ |   +3 If I remember it right, this blog should have gotten nearly 70-80 down votes after the contest ! I think you're not alone with the vision
 » 4 years ago, # |   0 First round from blue coder, they saidEasy contest gunna be, they said :P
•  » » 4 years ago, # ^ |   +4 Actually the lower rated the coder, the harder the contest. They are just trying too hard.
 » 4 years ago, # | ← Rev. 2 →   0 Some bug in my code for Problem B Anton and Lines, please, thanks youmy submissions WA on test 24
•  » » 4 years ago, # ^ |   0 Just change the variables to long long
 » 4 years ago, # |   +10 It's so difficult that those whose scores are around 1700 can only solve the first two problems,and the third problem is so difficult that I don't think it's a successful problem.So sad.
 » 4 years ago, # |   +19 Finally Experted!
•  » » 4 years ago, # ^ |   +31 hope see you in red ;)
 » 4 years ago, # | ← Rev. 4 →   0 7
 » 4 years ago, # |   0 :-)