By MikeMirzayanov, history, 2 years ago, translation, ,

Hello, my dear lovers of algorithms and data structures.

Codeforces Round 380 will start on November 20 (Sunday), 09:05 (UTC). It will be based on Technocup 2017 Elimination Round 2. So, if you are a Russian-speaking high-school student, please take part in the Technocup 2017.

Many thanks to KAN, GlebsHP, fcspartakm, Levshunovma. Hope to extend the list soon because of testers. Also some problem ideas are mine.

I hope you will like problems. It will be 6 problems in each division.

Good luck and bugless code

Scoring:

• TK Elim 2 and Div 2: 500-1000-1750-1750-2000-2500
• Div 1: 750-750-1000-1500-2000-2500

UPD 1: Here are our winners!

Top-5 in the Technocup stage:

Top-5 in Div.1:

Top-5 in Div.2:

•
• +227
•

 » 2 years ago, # | ← Rev. 2 →   +156
•  » » 2 years ago, # ^ |   +744
 » 2 years ago, # |   +13 And if I am not a Russian-speaking high-school student, I should register in Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2) ???
•  » » 2 years ago, # ^ |   +9 Yes, the registration will be open soon.
•  » » » 2 years ago, # ^ |   +28 Great, now I can happily miss another boring university day :D
•  » » » » 2 years ago, # ^ |   +96 Yep, it's usually boring on Sundays in university
•  » » » » » 2 years ago, # ^ |   +35 Believe me, It's always boring :p
•  » » » » » » 2 years ago, # ^ |   0 Me too it's a bad university.
•  » » » » » 2 years ago, # ^ |   +94 Sunday is not weekend in all countries :)
•  » » » » » » 2 years ago, # ^ |   +62 Oops, my bad
•  » » » » » » 2 years ago, # ^ |   -18 That is true, Saturday is also not a weekend in all countries.
•  » » » » » 2 years ago, # ^ |   +7 Now i am saying, boring university is better than negative rating change :p
•  » » » » » » 2 years ago, # ^ |   +3 What will you learn in that case? :)
•  » » » » » » » 2 years ago, # ^ |   +1 NO :3
 » 2 years ago, # |   +6 Does the Division 2 contest get all the same problems as the actual Technocup round or are there going to be unique problems as well?
•  » » 2 years ago, # ^ |   +13 Division 2 will contain the same set of problems as Technocup Round. Division 1 will contain harder problems.
 » 2 years ago, # |   +35 The one didn't write "thank ... and Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon" in contest description.
•  » » 2 years ago, # ^ |   +52 The one actually is MikeMirzayanov...
•  » » » 2 years ago, # ^ |   +67 Just a cold joke, too cold maybe.
 » 2 years ago, # |   +103 The midterm exams start tomorrow, which gives me only two options :(( :A- Participate in the contest and let the exams go to hell. B- Let the exams go to hell and participate in the contest. What do you people think?
•  » » 2 years ago, # ^ |   +1 Participate in the contest :)
•  » » 2 years ago, # ^ |   +4 Go to the exam :) If you don't participate on a div2, nothing will happen, You can do it virtual contest :) But You'll not have a virtual xm or something like that!
•  » » 2 years ago, # ^ |   +6 i would suggest to go for A, because contest comes first :p
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # |   0 Will the problems be in english as well?
•  » » 2 years ago, # ^ |   +7 Sure
 » 2 years ago, # |   0 Codeforces on fire. It's MikeMirzayanov--the elegant one.
 » 2 years ago, # |   +25 Probably got my birthday gift from Codeforces. Div1 Contest on my birthday
•  » » 2 years ago, # ^ |   -8 HB
•  » » » 2 years ago, # ^ |   0 Ty
•  » » » » 2 years ago, # ^ |   0 Happy birthday bhai :)
 » 2 years ago, # |   0 If i will register in Technocup 2017 — Elimination Round 2, would I have rating change or not? The same question about Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 — Elimination Round 2). Will I participate in technocup olymp?
•  » » 2 years ago, # ^ |   +4 If you register for Technocup 2017 — Elimination Round 2, you will get both rating change and participation, if you register for Codeforces round 380, you will get just the rating change.
•  » » » 2 years ago, # ^ |   0 whaaaaat???!!! Besides the rating change , What can I get if I participate in Technocup 2017 and get a high rank :D
 » 2 years ago, # | ← Rev. 2 →   -14 The midterm exams start tomorrow, which gives me only two options :(( :A- Participate in the contest and let the exams go to hell.B- Let the exams go to hell and participate in the contest.What do you people think?
•  » » 2 years ago, # ^ |   -14 That you copy pasted this.
 » 2 years ago, # |   0 Will division 2 in English? :/ when I registered, I saw Russian sentence :/ so,if the contest will be taken in English please make the reg. page in English.
•  » » 2 years ago, # ^ |   -12
 » 2 years ago, # | ← Rev. 2 →   0 How hard will it be compared to a div 2 round ( like round #379 )? I wanna know if i can solve anything or not
•  » » 2 years ago, # ^ |   +1 I think it'll be like 379 or a little bit harder. You can solve something I assume! :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +12 You can see problems from the Technocup 2017 Elimination Round 1.
 » 2 years ago, # |   -47 Is it rated?
 » 2 years ago, # |   +96 The System testing should start now because it takes long time
 » 2 years ago, # |   -29 Is Div 1 rated?
•  » » 2 years ago, # ^ |   +6 yes
 » 2 years ago, # |   0 I would be sad to miss this contest due to Zonal Computing Olympiad being held at same time in my city ...
 » 2 years ago, # |   0 i've waited this round for 2 weeks, wish it will be an excellent round LOL
•  » » 2 years ago, # ^ |   0 It happens; )))))
 » 2 years ago, # |   +5 great :) what a hurry contest where just ended one Regional :) by the way All the best to all
 » 2 years ago, # |   +7 It's "TLE" when I used "cin" for Problem B(div2)! Sad ~,~!
•  » » 2 years ago, # ^ |   0 Same here... Had to use ios..
•  » » » 2 years ago, # ^ |   0 worse than that passed pretest with excution time = 880ms and noticed after 1 hour
•  » » 2 years ago, # ^ |   0 Strange..used cin but didn't get TLE, 22345324
 » 2 years ago, # |   0 Can anyone hack any submission during contest???
 » 2 years ago, # |   0 Strongest pretests in DIV1 — rare hacks :(
•  » » 2 years ago, # ^ |   0 t < s in A brought me down by 100+ ranks already :D
 » 2 years ago, # |   +1 How to solve Div 2 D and E?D seemed like binary search to me but couldn't get anything concrete in time. :/
•  » » 2 years ago, # ^ |   +1 I solved D using greedy and C using binary search, dunno about E.
•  » » » 2 years ago, # ^ |   0 How?
•  » » » » 2 years ago, # ^ |   +15 In C use binary search to find the least powerful engine that will fit into the time. In D find the maximum number of ships that can be placed in the board. The answer is the maximum number of ships minus real number of ships + 1. Then just shoot so that you remove a possible ship with each shot.
•  » » » » » 2 years ago, # ^ |   0 It's funny how C problems are harder to pass than D problems now. :D
•  » » » » » » 2 years ago, # ^ |   0 They had the same score. But yeah, this D was easier to code than the A imo lol.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Find all the empty segments, and the max. number of ships placeable in the field is sum of (length of segment i / b). Let the number be x, and you need to shoot at least x-b+1 times to ensure a hit. Then just shoot at places where the number of placeable ships will decrease for a sure.
•  » » 2 years ago, # ^ |   +1 D — greedy — one should take every kth consecutive zero if a=1, dont take last a-1 such places. E — consider height of tree to be 1..n-1, calculate answer as function of distinct values not present and values lying outside, take min overall.
 » 2 years ago, # | ← Rev. 2 →   +6 Worse div1 contest ever!no interesting problemno hack
•  » » 2 years ago, # ^ |   +40 Boring contest
 » 2 years ago, # | ← Rev. 2 →   +24 If I don't fail system test, this round will be my best round ever.Good luck to me.UPDATE: Failed E T T
•  » » 2 years ago, # ^ |   0 Still top 100 so nice job anyways!
 » 2 years ago, # | ← Rev. 3 →   -136 OMG !!! I hate all problems where arrays length is not standard. For example why in problem C array G is '2e5' ???? I had -200 for this mistake. HATE NOT STANDARD ARRAYS LENGTH PROBLEM.UPD #NOPROBLEMWITHNOTSTANDARTARRAYSLENGTH
•  » » 2 years ago, # ^ |   +73 What exactly do you consider 'standard array length'? You have different constraints in each problem, it literally takes a second to look at them. Don't whine.
•  » » » 2 years ago, # ^ |   -59 I'm saying that there's no big difference in length 1e5 and 2e5. So I can't understand why they took 2e5?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 .
•  » » » » » 2 years ago, # ^ |   -17 Can you explain me?
 » 2 years ago, # |   +14 How to solve Div1 D? I used DP[left][right][k] and it passed pretests with 1.7 sec, but it doesn't seem to be a correct solution..
•  » » 2 years ago, # ^ | ← Rev. 3 →   +54 You may notice, that k <= 100 and -100 <= right - left <= 100 UPD: where 100 is surely = O(sqrt(n))
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 So, will pass?
•  » » » » 2 years ago, # ^ |   +13 I don't think so. But with understanding of this constraints it'll be O(n2)
•  » » » » » 2 years ago, # ^ |   0 Thanks, I will think about it
•  » » » 2 years ago, # ^ |   0 Ah, so the number of states will be less than 4000 * 200 * 100 = 80000000.. Thx for explaining!
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 In fact, this can be done in O(N^2) memory if you just memoise using a map. This is because the number of papers Igor and Zhenya have taken in total differs by at most O(sqrt(N)) (To increase the difference after they have made an equal number of moves, you have to increase k, and k is O(sqrt(N))). So this actually runs in O(N)*O(sqrt(N))^2= O(N^2). Memoisation ensures that you only use memory proportional to number of states visited.
•  » » » » 2 years ago, # ^ |   0 I read your solution submitted during the contest, is there any trick on implementing? I did almost the same thing as in your code but just got TLE
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +6 I always add "fflush(stdout); _Exit(0);" in the end of the main() function. When I use many maps or sets or the elements are too many, it reduces the running time about a few hundred milliseconds. Consider branching like this: if (k <= mem) { ... } else { ... }instead ofif (k <= rem) { ... } if (k + 1 <= rem)because it is unnecessary to check "k + 1 <= rem".I submitted your solution with these two micro optimizations, and it was accepted. 22377001
•  » » » » » » 2 years ago, # ^ |   0 Wow! That works! Thank you!!!It seems that I have to be very careful with the constants of solutions when their complexity is near the boundary.
 » 2 years ago, # |   +1 Looks like O(n*k) solutions passed pretests in div2 C. I should have hacked...I wonder how many of these were submited.
•  » » 2 years ago, # ^ |   0 My solution with binary search didn't pass until I wrote .sync_with_stdio(0). How could O(n*k) pass then?
•  » » » 2 years ago, # ^ |   0 What is the time of this solution: http://codeforces.com/contest/738/submission/22354478 ?
•  » » » » 2 years ago, # ^ |   0 O(nlogn + klogn) I think.
 » 2 years ago, # |   0 Lets hope system testing isn't late today?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Now it's running!UPD: uh-oh... It seems that queue is stopped?!
 » 2 years ago, # |   0 How to avoid TLE in DIV2 B? Tried ios.. and scanf but couldn't pass.
•  » » 2 years ago, # ^ |   0 Use prefix sums.
•  » » » 2 years ago, # ^ |   0 I used prefis sums with cin and got TLE, that's really annoying
•  » » » » 2 years ago, # ^ |   0 prefix sums for Div2 B?
•  » » » » » 2 years ago, # ^ |   0 Yes, so you can know if there is anything on the right,left, up or down
•  » » » » » » 2 years ago, # ^ |   0 Oh. I used a different method.I was able to get AC using normal cin. You can refer to my way here:(Ignore the functions before main() ) 22349678
 » 2 years ago, # |   +8 _how can get the solution or tutorial ?
•  » » 2 years ago, # ^ |   0 They'll publish it tomorrow or later.
 » 2 years ago, # |   +14 Div1 systest paused???
•  » » 2 years ago, # ^ |   +274 They noticed that systest today is a little bit fast, so they paused it a bit because CF traditions says it should be slow.
•  » » 2 years ago, # ^ |   0 I think so.
•  » » 2 years ago, # ^ |   +5 They started div2 testing. Looks like they can't do both at the same time...
 » 2 years ago, # | ← Rev. 5 →   -12 .
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 What does on fuel mean? If you mean tank capacity, my binary search works in 0.2s (it's 0..1e9 but it should not matter)
•  » » » 2 years ago, # ^ |   0 Maybe I have done some mistake but Sampson's comment implies same. See lots of binary search solutions failing — http://codeforces.com/contest/737/submission/22346839
•  » » 2 years ago, # ^ | ← Rev. 2 →   +52 I am pretty sure that the reason for your TLE is integer overflow: int lo = 1, hi = 2 * s; . . . int mi = (lo + hi) / 2; 
•  » » » 2 years ago, # ^ |   +5 Oops :( Thanks.
•  » » » 2 years ago, # ^ |   0 Had the same problem, forgot that it would be ~4*1e9 which makes more than 2^31.
 » 2 years ago, # | ← Rev. 2 →   +38 Honestly I don't see any point setting TL = 1s for Div 1 A so that log(2e9) or slightly slow binary search can't pass.Edit: My apology. This solution actually fails because of integer overflow when computing (lo + hi) / 2 as pointed out by -Secta-.
•  » » 2 years ago, # ^ |   +21
•  » » » 2 years ago, # ^ |   +15 My apology. Thank you for pointing out my mistake.
•  » » 2 years ago, # ^ |   +64 It is not because of slow binsearch, but because of hanging binsearch. They have overflow or other mistakes in implementation.Even solution with extra internal binary search (e.g. O(n·log2n)) passes the tests and fits in half of TL.
 » 2 years ago, # |   +12 Feels bad when failing 3 contests in two days. :'(
 » 2 years ago, # | ← Rev. 2 →   +19 My wrong solution 22349543 passed systest, but it will fail on this test: 1 1 10 18 5 6 5 Correct output: 5 My output: -1I just noticed it just after contest end that I forgot to handle that case, to fix that I should add else x-=V[n]*(llu)h-S[h-1]; on 34th line.Edit: Wow so fast rating change =)
 » 2 years ago, # |   0 my solution for problem B(div 2) in pyth2 is giving TLE and same solution in pypy2 is accepted,,poor testing in python
•  » » 2 years ago, # ^ |   +1 Pypy is much faster than python I think.
•  » » » 2 years ago, # ^ |   0 Yes, i think it uses JIT compilation, so it usually should be faster.
•  » » 2 years ago, # ^ |   +18 that's why there's pypy compiler
 » 2 years ago, # |   +16 What is the test that does this? :)
•  » » 2 years ago, # ^ |   0 I think 1oThis is where I got WA. -_-
 » 2 years ago, # | ← Rev. 2 →   -52 Nice contest !
•  » » 2 years ago, # ^ |   +1 Sure.
•  » » 2 years ago, # ^ |   +2 lol
 » 2 years ago, # | ← Rev. 2 →   -6 I got TLE on systest on the same test I got accepted in pretests with 920 ms. I used prefix sums on line and columns.this
 » 2 years ago, # | ← Rev. 4 →   -6 Mysterious TL in problem A for div 1, test 9Why is there TL on test 9 in my this solution? http://codeforces.com/contest/737/submission/22357999 It has return code -1, but still even checker should print RE, I don't understand why is it so. Maybe some of you know?
•  » » 2 years ago, # ^ |   0 Probably slow IO?
•  » » » 2 years ago, # ^ |   0 Dunno, it could have been IO, but some of my friends solved it with cin's and they have 250 ms on this test.
•  » » 2 years ago, # ^ |   +5
•  » » » 2 years ago, # ^ |   0 Oh, ok. Thanks, I'm lol.
•  » » 2 years ago, # ^ |   0 If the size of input/output is large enough and you want to use cin/cout, you have to call "std::ios_base::sync_with_stdio(false)" first.
 » 2 years ago, # |   0 I had TLE using cin and cout, but after I used scanf I got AC.
•  » » 2 years ago, # ^ |   +1 Welcome to CodeForces buddy.If you insist on using cin, cout make sure you are using c+14 and use ios::sync_with_stdio(false) .
 » 2 years ago, # |   +20 Potato quality pretests making my tomato quality codes to fail since 2 onion type of contests.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +7 Pretests are actually meant to be potato quality
•  » » » 2 years ago, # ^ |   0 You must be fun at LAN parties.
 » 2 years ago, # | ← Rev. 2 →   0 Could anyone help me to find my mistake in problem C ?http://codeforces.com/contest/737/submission/22349523I am very eager to know...UPD : FOUND
 » 2 years ago, # |   0 22356216 What is the problem a***b != a***b ?
•  » » 2 years ago, # ^ |   +2 You also output "?".
•  » » » 2 years ago, # ^ |   -6 No I didn't run my code,it's ok for all sample tests..
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +8 No. Stop spamming. http://codeforces.com/contest/738/submission/22362803 (last line difference)
•  » » 2 years ago, # ^ |   0 you outputed "a***b?", not "a***b"
 » 2 years ago, # |   +29 The participation was rather low today, and I assume the reason for this a slightly more difficult problem A(div 2). People have come to the contest and decided against submitting I presume. Wouldn't it be great to have a topcoder like system, where u are on the leaderboard if u open the contest ?Its much more difficult to get a positive rating change with such low participation.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +38 That could be the case for div2; however, for div1 main reason of low participation seems to be a lot of other contests clashing with CF round — OpenCup stage, bunch of regionals (SWERC, CERC, NWERC); also some teams are on their road home from MIPT training camp.Issue you mentioned has been discussed a lot of times already, and I don't think there are going to be some changes on it in near future. This system itself is really vulnerable (simply register another account to read problems I guess). It needs a lot of harsh actions — like checking IP addresses of contestants etc. Nowadays people aren't even banned for having multiple accounts or competing in teams using single account (when one account sometimes makes submissions from 2 or 3 cities during a contest). I'm personally fine with it in case we have to choose between platform improvement or having more contests — and improving "fair play" system :) I'm sure that I'm not at the top not because of cheaters but because of other contestants being much better than me :)
 » 2 years ago, # | ← Rev. 2 →   -31 Is the rating system broken?I was ranked 995 and my rating changed from 1448->1446(-2). Edit:Nvm, I guess it's due to low participation.
 » 2 years ago, # |   0 22356216 What is the problem a***b != a***b ?
•  » » 2 years ago, # ^ |   0 you print something strange at the end! I think it's '/n';
•  » » » 2 years ago, # ^ |   0 Please help,i tried on all sample tests and answer is ok,you can run it if you want..
•  » » » 2 years ago, # ^ |   0 It's actually '/0', he has array out of bounds.
•  » » » » 2 years ago, # ^ |   0 Ohh thank you,I'm new on CF,sorry for spamming I thought my message wasn't sent so I clicked it too many times..
 » 2 years ago, # |   +11 Didn't pass C because I didn't sort the array in which I binary searched. How the hell did it even work?
•  » » 2 years ago, # ^ |   +3 I was wondering why my solution to (div2)B wasn't working until I noticed that I'd erased the part which was reading the data and that I'd been processing uninitialized 2d array. :D
»
2 years ago, # |
-32

I am very heated up right now(actually, not really) I was solving 729A - Интервью с Олегом. I thought I had did answer and submitted my code, and I got a "wrong answer". I looked at the test cases, and tried it on my program, but in my program, it printed the right answer.

# include <stdio.h>

char d[101]; int N; int f(int n) { for (int i = n; i < N; i += 2) { if (d[i] == 'g'&&d[i + 1] == 'o') continue; else return i; } } void fill(int a, int b) { int cnt = 1; for (int i = a; i < b; i++) { if (cnt > 3) d[i] = 0; else d[i] = '*'; cnt++; } return; } int main() { scanf("%d", &N); scanf("%s", d); for (int i = 0; i < N — 2; i++) { if (d[i] == 'o' && d[i + 1] == 'g' && d[i + 2] == 'o') fill(i, f(i + 3)); } for (int i = 0; i < N; i++) { if (d[i] == 0) continue; else printf("%c", d[i]); } } this is the code. I've got stuck on test case 2. What is wrong with it???

•  » » 2 years ago, # ^ |   +5 f doesn't return anything if it goes on until the end of the string
•  » » » 2 years ago, # ^ |   0 thank you very much :D
•  » » 2 years ago, # ^ |   +6 Hi, it's more convenient to post your whole submission. Let's say: 22363876. Also, as tfg has noted, your function f doesn't return any number if the control gets out of for loop without ever evaluating else clause. The behaviour of function f is therefore probably undefined and it just so happens that it returns correct value on your (and mine) computer, but not on the OJ. One way to modify this could be for example: Codeint f(int n) { int i; for (i = n; i < N; i += 2) { if (d[i] == 'g'&&d[i + 1] == 'o') continue; else break; } return i; } That being said, it might not be the most beautiful solution to your problem. By the way, if you compile your program with "-Wall" flag, it gives you a warning: Spoilerg++ -Wall we.cpp ... ... ... we.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type] 
•  » » » 2 years ago, # ^ |   0 thank you very much :D, I'm new here, so I didn't know how to ask... Sorry
 » 2 years ago, # |   0 Hey, how to solve Div1B?Thanks.
•  » » 2 years ago, # ^ |   +9 We have to change as few zeroes as possible to ones so that it is impossible to place a ships on the zeroes. Calculate for the initial configuration how many ships can be placed. After that, greedily remove the possibility of placing a ship, whenever there are b consecutive zeroes (i.e. change the b-th consecutive zero to one). Do it until fewer than a ships can be placed.
•  » » » 2 years ago, # ^ |   0 Got it. Thanks a lot!
 » 2 years ago, # |   +1 Any suggestions for div2E?I used this idea: consider it to be a tree, so each node has it’s depth (number of superiors) If the tree has it’s total depth K, then there should be all integers in range 0 – K and not any deeper than K.So, for each K in range 1 — N I check how many changes I need to make in order to make the tree with depth equal to K. Any idea why it wouldn’t work?Here is the link of my try.
•  » » 2 years ago, # ^ |   +5 That's the right idea.You check how many changes you need to make to create a tree with total depth from 1<=K<=N-1 (a tree with only a 0 has depth 0). All numbers from 1 to K must be present (there will be only one 0) so to do that you check if you can use the numbers > K to fill the gaps since you will have to change them anyway (to K or some other number lesse than K). If it still isn't enough, you will have to use the numbers from 1 to K to fill any missing gaps. If you consider the numbers that are 0 and aren't the chief as N, you will get the right answer since they are wrong and you need to change them.
•  » » » 2 years ago, # ^ |   0 Thanks!My wrong was that I used only those who had 0 depth to fill the gaps, didn't use those which are > K
 » 2 years ago, # |   +5 When will be editorial?
 » 2 years ago, # |   +5 When will the editorial published? I couldn't figure out the solution of C. Can anyone explain it please.
•  » » 2 years ago, # ^ |   +3 Sort the cars by their volume of fuel and use binary search to find the first car that can arrive to the destination in time, lets say it's the k-th car. Then just itterate through all cars from k to n and pick the one which costs the least.My code. Sorry but it's pretty ugly :D
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thanks a lot i got it.
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 creepersteve7Could u explain / prove these lines of code ?d2=a[p].first-d;d1=d-d2;time+=(2*d1+d2);thanks in advance !
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 D1 is the distance he will travel normally and D2 is the distance he will travel accelarated. So we have D1+D2=D, where D is the total distance. Also he uses 1 l/km in the first case and 2 l/km in the second so D1+2*D2=V, where V is the volume of fuel. So we have D2=V-D, D1=D-D2. The we just find the time. I'll leave proving the time formula as homework :D
•  » » 2 years ago, # ^ | ← Rev. 2 →   +9 We can binary search the least fuel f we need to get to the destination in time. And the answer is the cheapest car whose fuel limit is larger than or equal to f. Now the question is: how to check if we can get to the destination in time with a certain fuel limit.Denote the distance between a pair of adjacent gas stations as d, the distance we need to drive in accelerate mode as a, the distance we need to drive in normal mode as b, the fuel limit as v, and the shortest time we need to get to the destination as t.In order to get to the destination as fast as possible, we should use as much fuel as we can. If 2d ≤ v we can always drive in accelerate mode, i.e. t += d;. If d > v then we don't have enough fuel even if we always drive in normal mode, so return false; in your check function.Now we only need to consider the case when d ≤ v < 2d. Because we need to use as much fuel, so we have the following two equations:2a + b = v and a + b = d.Solve them, and we get a = v - d and b = 2d - v, i.e. t += (v-d) + 2*(2*d-v);You can check my code for more details. Remember to use long long type or set the upper limit of the binary search to a little bit more than 1e9. I set the upper limit to 2e9 during the contest and it overflows :(My code: 22361702
 » 2 years ago, # |   0 I try to use an unordered_map to solve Div1.D during the contest but got TLE on pretest 9. After the contest I checked some successful submissions made by others and found that they also use unordered_maps. Are there any tricks when using unordered_map to speed it up?
•  » » 2 years ago, # ^ |   0 Not sure if this is the case here, but sometimes they have testcases that specifically catch unordered_maps. I think it's stupid, but it's happened in the past that you need to use the normal map (which is a bst) to pass the test-cases which are designed to specifically beat unordered_maps.
 » 2 years ago, # |   +5 When will the editorial be published? Or is it published already? The last round of technocup didn't link it's editorial to the problem page so I am concerned that the same thing might happen again.
•  » » 2 years ago, # ^ |   0 Looking for help in solving div1E.I have drafted the minimum time should be max single machine/child play time, and I should rent second machines greedily by the length of play time queue. However, I have no idea how I should cope with providing a valid schedule.
 » 2 years ago, # |   +13 mfw practicing a day after the contest was held