By KAN, 4 years ago, ,

Hi all,

The 8VC Venture Cup 2017 - Final Round is tommorrow at 18:05 UTC. Along with that, Codeforces Round #393 will be held at the same time both for Div. 1 and Div. 2 participants. The Div. 1 Edition will contain the same problems as the Final Round, the Div. 2 Edition will be easier.

Of course, those who have placed in top 200 in 8VC Venture Cup 2017 - Elimination Round should register for the Final Round, all the others should register for Div. 1 or Div. 2 editions according to their rating. All three contests will contain six problems, last two hours and be rated.

The problem authors are Um_nik, Endagorion, Umqra, pashka and me. Also huge thanks to fcspartakm for his help in preparation, and to vepifanov and AlexFetisov for testing the round. I suggest you reading all the problems to find which one you like the most!

I'd like to remind you about the prizes:

• Overall 1st place — $2000 • Overall 2nd place —$1000
• Overall 3rd-5th places — $500 each • Overall 1-50th place — t-shirts with 8VC and company logos • Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar and 8VC) and other Silicon Valley technologists • Local top finishers — Opportunity to meet with leadership from 8VC portfolio companies Please welcome one more company became interested in the Venture Cup, Progressly! Progressly is a cloud-based Operational Performance Management platform allows you to document, collaborate on, and gain contextual insights into core business processes and outcomes in real time. The scoring is usual in all three contests: 500-1000-1500-2000-2500-3000. Congratulations to the winners! 8VC Vecture Cup 2017 winners: Codeforces Round #393 Div. 1 winners: Codeforces Round #393 Div. 2 winners: Editorial • +204  » 4 years ago, # | +54 That's funny, my dad and Joe Lonsdale are really close friends, I get to meet Joe all the time. :) •  » » 4 years ago, # ^ | 0 That's really funny  » 4 years ago, # | +90 Before Joe Lonsdale started 8VC, he worked with my dad in the company: formation8. Sadly, they split up! My dad started a company that has "formation" in it, and Joe started a company that has, "8" in it! So cool! •  » » 4 years ago, # ^ | -72 Joe Lonsdale company make codeforces rounds, your dad's company don't, perhaps that's why they split up :V •  » » » 4 years ago, # ^ | +22 They used to be in an investing company together. They were like best friends. They were the founders of the company, they worked together. •  » » 4 years ago, # ^ | +11 fair division! •  » » 4 years ago, # ^ | 0 That's perfect division, first instance I got to know splitting so perfectly.  » 4 years ago, # | +10 How do I register if I qualified locally but am not in the top 200?Also, I go to the same high school Joe went to ;)  » 4 years ago, # | ← Rev. 2 → -54 Div 2 edition will be rated? UPD1: It is rated, it was unofficial at first thats why I asked. •  » » 4 years ago, # ^ | +3 Yes, it will.  » 4 years ago, # | +205 "Local Winner — Dinner with Joe Lonsdale"This Silicon Valley entrepreneurs think they are the big shit. Someday, I'm going to organize my own programming competition and I will invite the winner to meet me in a tea party in Crimea. •  » » 4 years ago, # ^ | ← Rev. 2 → -49 I agree, I'd like to do the same lol. :) •  » » » 4 years ago, # ^ | 0 Snowden offended Barack Obama as well. He's got big balls. •  » » » » 4 years ago, # ^ | 0 EdwardSnowden, is this true?  » 4 years ago, # | +6 I see the option to register for the Final Round, but I didn't place top 200 in the elimination round. Is it normal? •  » » 4 years ago, # ^ | -18 yap! •  » » 4 years ago, # ^ | +5 There are some people who are currently registered for the final round but did not place in the top 200 in the elimination round, so I'm guessing the option appears for everybody.The CF admins probably just assumed everyone would register for the correct round. I'm not quite sure how the incorrect registrations will be dealt with, so you should just register for the Div 1 version. •  » » » 4 years ago, # ^ | +2 Could you give me examples? We have some exclusions because of local finalists. •  » » » » 4 years ago, # ^ | 0 I'm a local finalist but I still get the "you can't register" message. •  » » » » » 4 years ago, # ^ | +7 Please try again. Anyway no reason to worry, for sure you'll be registered correctly. •  » » » » 4 years ago, # ^ | 0 kyleliu is an example. His rank in the elim round was 852 •  » » » » » 4 years ago, # ^ | +41 I'm also a local finalist •  » » » » 4 years ago, # ^ | 0 In the list of recently registered people I found a few users who did not list their locations as from the USA (I'm assuming local finalist means from the Silicon Valley area), but it's possible they have moved. Here are 2 examples: ctzsm dojiboy9 •  » » » » » 4 years ago, # ^ | 0 I am here at Addepar. •  » » » 4 years ago, # ^ | +2 When I clicked on register button , it's showed me that I am not eligible. So that's not a problem at all.  » 4 years ago, # | -61 Rating will Dowa?  » 4 years ago, # | -11 Hope another exciting contest, interesting problem set :)  » 4 years ago, # | 0 It's always a great learning to participate in codeforces rounds. Thanks to all the problem setters :).  » 4 years ago, # | -9 Contest postponed by 10 minutes? •  » » 4 years ago, # ^ | +49 Sorry, it is because of onsite event. •  » » 4 years ago, # ^ | ← Rev. 2 → -91 damn everyone wants upvote!! •  » » » 4 years ago, # ^ | +36 No, some people just want to stay informed on what's happening with the contest •  » » » 4 years ago, # ^ | +45 Ah yes, imaginary internet points. They truly are what make the world go round.  » 4 years ago, # | -12 Delayed !!  » 4 years ago, # | -12 Why delay?  » 4 years ago, # | 0 Damn, contest delayed by 10 minutes.  » 4 years ago, # | -20 delay in a contest, kills the excitement to some extent :(  » 4 years ago, # | ← Rev. 3 → -55 Please ignore this comment.  » 4 years ago, # | -40 tourist GK hope u will 1st today , best of luck . zscoder u are just awesome zi song •  » » 4 years ago, # ^ | +10 hoping is for us. he is first normaly  » 4 years ago, # | +52 R.I.P. English  » 4 years ago, # | +47 am i the only one failing to understand problem c statement ? •  » » 4 years ago, # ^ | +14 I've read it multiple times and I still don't understand what the questions wants :( •  » » » 4 years ago, # ^ | 0 the only way is to submit wrong and wrong til it gets pretest passed ! •  » » » » 4 years ago, # ^ | 0 The question could have definitely be worded better. Everyone who doesn't how barbecue is made is going to have a tough time to understand it.  » 4 years ago, # | +44 Will you upload English statements?  » 4 years ago, # | +71 Unable to understand Div 2 C. Never cooked barbecue. :/  » 4 years ago, # | 0 Awful contest, problem B in russian was not full, so i couldn't solve it. Hope it will not repeat. •  » » 4 years ago, # ^ | -19 I think it wasn't too difficult to understand the statement. Also samples can help. •  » » 4 years ago, # ^ | 0 Same shit  » 4 years ago, # | +2 Awesome contest, hope that i will pass system tests. •  » » 4 years ago, # ^ | 0 What was your logic for C? •  » » » 4 years ago, # ^ | +14 Imagine it's a graph. You need to make it into a single cycle, and have an odd number of bs. If you have x > 1 cycles, you need exactly x operations to transform them into just 1 cycle, and then 1 more operation if the sum of all bi's is even. •  » » » » 4 years ago, # ^ | 0 My bad I visualized it in terms of components. •  » » » » 4 years ago, # ^ | 0 Why is the number of 1's should be even? Why is this bad b[4] = {0, 1, 0, 1}? •  » » » » » 4 years ago, # ^ | +1 Basically, after traversing the cycle, we need to up at the same node in the opposite direction. Only then it can visit all n positions in both directions.Even number of 1s will always lead to same direction after traversal. •  » » » » » 4 years ago, # ^ | 0 If you start from a node, and walk exactly N times, you should end up in same node because ending graph should be one big cycle. Then, it follows that you can't have visited a node more than once. If you start at node X, and when you again visit it after N times, the sum of b[i] encountered is 0 mod 2, your state hasnt changed, meaning you're going to repeat the exact same cooking(no reversing really occurs). •  » » » » » 4 years ago, # ^ | 0 Even number of ones means that by the time each skewer makes a full round and returns to its original spot, it will have been flipped an even number of times, meaning it will be in the same position as it started, which is not good since we want it to be in the flipped position •  » » » » » 4 years ago, # ^ | 0 Imagine a cycle with any number of nodes n.Now, if you start at a node say x, then you will travel in this order :x -> y -> .... -> xSo, once you start at x, if the total number of inversions of the skewer is even, then you will end up at x with the same direction of the skewer because any change made in the direction will be reversed also. So, even if you traverse this cycle multiple times, you will reach each node with the same direction.But, if there are odd number of 1's, then after 1 traversal of the cycle, you will reach x with the opposite direction of the skewer as to what you started with. Now, with another traversal of the graph all nodes have had both the directions. •  » » » 4 years ago, # ^ | +3 The graph is combination of cycles, you need to make graph a single cycle. And if there is even number of 1's you should change something. •  » » » 4 years ago, # ^ | 0 I counted the number of cycles in permutation and then calculated the number of changes we need to make in order to combine all of these cycles into a single cycle.If all of the numbers in b were zeros I added 1 to the answer.This approach is failing at test 8. Either my logic is completely wrong or I made a mistake in my implementation. •  » » » » 4 years ago, # ^ | ← Rev. 2 → 0 Your approach will fail for the following case. 3 2 3 1 1 1 0 Correct answer is 1, not 0. •  » » 4 years ago, # ^ | 0 Oh no, tl on 80 test.  » 4 years ago, # | +54 Will Div 1 and Final Round results be combined for the rating calculations or are those calculated separately? •  » » 4 years ago, # ^ | -13 This won't. There would be a combined contest for div1 and div2 if that was the case.  » 4 years ago, # | 0 The Contest was good, spend a lot of time on B but still unable to come up with a solution... •  » » 4 years ago, # ^ | +11 Binary Search on answer. •  » » » 4 years ago, # ^ | 0 what was the right limit? (the left limit was 1, sure) •  » » » » 4 years ago, # ^ | +3 I used M i.e number of pillows given as right limit. •  » » » » » 4 years ago, # ^ | ← Rev. 2 → 0 I used it too, but I didn't succeed to pass the pretests... :( •  » » » » » 4 years ago, # ^ | 0 code I used Binary search. but it didn't succeed.. Can you please see my code (what is wrong) •  » » » » » » 4 years ago, # ^ | 0 Paste it somewhere else i can't see from here •  » » » » » » » 4 years ago, # ^ | -8 •  » » » » » » » » 4 years ago, # ^ | +3 Your check function logic is not right. Here is link to my accepted code : here •  » » » » » » » » » 4 years ago, # ^ | 0 What about this one ? •  » » » » » » » » » 4 years ago, # ^ | 0 Thank you :) •  » » » » » » » » » 4 years ago, # ^ | 0 Noo, mine gets wrong answer too. XD And I don't know why. •  » » » 4 years ago, # ^ | +2 Can you explain your logic for div 2b ? •  » » » » 4 years ago, # ^ | ← Rev. 2 → +8 First give everybody a pillow. Then binary search from 1 to m to see if you can give the kth position some r pillows. You can easily calculate how many pillows required in O(1) [just give the (k-1)th and the (k+1)th hobbit r-1 pillows, the (k-2)th and the (k+2)th hobbit r-2 pillows and so on..this can be calculated with the knowledge that sum of all elements from 1 to n = n*(n+1)/2 in O(1)]. •  » » » 4 years ago, # ^ | +5 Binary Search was not necessary. You could brute-force by computing the number of pillows that you need for the answer to be at least 1, 2, 3... until p, where p = max(n-k+1, k), and then you could divide the number of remaining pillows (if there are some remaining) by n and add the result to p to get the answer. •  » » » » 4 years ago, # ^ | +1 I did it the same way. Any idea what the complexity would be? •  » » » » » 4 years ago, # ^ | +7 Roughly O(sqrt(M))  » 4 years ago, # | +4 good contest  » 4 years ago, # | +129 Me when I read div2C •  » » 4 years ago, # ^ | +4 I need some SAT Reading skills to understand this problem :))))  » 4 years ago, # | +8 How to solve D div1? •  » » 4 years ago, # ^ | -10 Hint* Dynamic programming + binary search •  » » » 4 years ago, # ^ | +25 I guess I need some extra hints :)Also are you sure you aren't talking about Div1 B? •  » » » » 4 years ago, # ^ | 0 So sorry, missread •  » » » » 4 years ago, # ^ | 0 Try solving the problem "Find the number of distinct subsequences of some string S (of any length)". You can use similar ideas to solve D. •  » » » 4 years ago, # ^ | 0 Div 1  » 4 years ago, # | ← Rev. 2 → +10 is there anyone who passed div1 D with 26*n^2 solution instead of n^2 ? because if there is then #%#%@#$@#@
•  » » 4 years ago, # ^ |   +13 Yes, it runs in 1300ms. Use int instead of long long and do if (dp[i][ii]==0) continue;
•  » » » 4 years ago, # ^ |   +26 Strangely, this gave TLE with C++11 and passed in 1263ms with C++14. Never knew C++14 had so much better optimizations.C++11C++14
•  » » » 4 years ago, # ^ |   0 Never would have thought there is such a big difference in speed between int and long long.
•  » » 4 years ago, # ^ |   0 Mine failed
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I did, 1900ms.edit: And yeah, I also spent 30 minutes optimizing it..
•  » » 4 years ago, # ^ |   0 I did, but I solved that in 13 mins and then have been optimizing it for 20 mins. I needed to change a bit flow of my algorithm to gain better use of cache and erase my beloved macro "#define int long long" and it passed in 748 ms. Maybe that cache thing was not necessary because deleting that macro sped up my program from 3,5s to 750ms on CF >_>...
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Did almost everyone else do O(σ N 2)? I just wouldn't imagine this passing along with modulo operations. I did waste some time figuring out how to reduce to O(N 2). I did like D as a problem though.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 You can do the dp in O(N 2) by using a prefix sum table.
•  » » 4 years ago, # ^ |   +10 I did, with no optimizations at all. It passes in 1840ms.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +20 Got it passed in 1.5 seconds.The code running O(n 2) times was the following (3.5 seconds locally on a random test): code 1 int cur = f[!b][pos]; foreach (let; 0..26) { int dest = next[pos][let]; f[b][dest] += cur; if (f[b][dest] >= mod) f[b][dest] -= mod; } First, branching gets in the way of instruction-level parallelism. So, get rid of branching by switching f to int64 (it was int32) and taking the remainder in an O(n 2) outer loop (down to 3.05 seconds): code 2 auto cur = f[!b][pos]; foreach (let; 0..26) { f[b][next[pos][let]] += cur; } This was still not enough: my compiler is dmd which sometimes produces suboptimal code. Locally, this is already fast with gdc or ldc, but they are not present on Codeforces.So, the next thing was to streamline accesses to the transition table (1.55 seconds): code 3 auto cur = f[!b][pos]; auto ptr = next[pos].ptr; foreach (let; 0..26) { f[b][*(ptr + let)] += cur; } This looked fast already. But I added manual loop unrolling, just to be sure it happens (1.3 seconds): code 4 auto cur = f[!b][pos]; auto ptr = next[pos].ptr; f[b][*(ptr + 0)] += cur; f[b][*(ptr + 1)] += cur; f[b][*(ptr + 2)] += cur; f[b][*(ptr + 3)] += cur; f[b][*(ptr + 4)] += cur; f[b][*(ptr + 5)] += cur; f[b][*(ptr + 6)] += cur; f[b][*(ptr + 7)] += cur; f[b][*(ptr + 8)] += cur; f[b][*(ptr + 9)] += cur; f[b][*(ptr + 10)] += cur; f[b][*(ptr + 11)] += cur; f[b][*(ptr + 12)] += cur; f[b][*(ptr + 13)] += cur; f[b][*(ptr + 14)] += cur; f[b][*(ptr + 15)] += cur; f[b][*(ptr + 16)] += cur; f[b][*(ptr + 17)] += cur; f[b][*(ptr + 18)] += cur; f[b][*(ptr + 19)] += cur; f[b][*(ptr + 20)] += cur; f[b][*(ptr + 21)] += cur; f[b][*(ptr + 22)] += cur; f[b][*(ptr + 23)] += cur; f[b][*(ptr + 24)] += cur; f[b][*(ptr + 25)] += cur; Overall, the optimization effort took 5.5 minutes between the two submissions (one, two). Actually solving the problem took way longer for me.
 » 4 years ago, # |   0 How to solve Probelem E? Is that sth like keep the value of sum for each suffix,-1 for pop and +1 for push, and query where the last sum which is exact 1 is?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +19 I used segment tree with lazy propagation (range add update & max query). Add -1 to [0, pos] if pop, 1 to [0, pos] if push and do binary search to find the rightmost positive number. O(n lg^2 n)
•  » » » 4 years ago, # ^ |   0 We can also get rid of binary search by can starting from the root and going to the right child if it's maximum is positive. It's O(N log N) this way.
•  » » » 4 years ago, # ^ |   0 Um, I'm confused, Why do you need lazy propagation for this?
•  » » » » 4 years ago, # ^ |   0 kraskevich We commented at the same time :P
•  » » » » 4 years ago, # ^ |   0 To update a range in O(log n).
•  » » » 4 years ago, # ^ |   0 ..... I came up with this idea and then forbade it.... that's too stupid
 » 4 years ago, # |   0 Good contest B question was good
 » 4 years ago, # |   +11 struggled to debug div1 B for 40 min because of misreading 1440 as 1140 T T
•  » » 4 years ago, # ^ |   0 Same here. I had WA 6 and was looking for a bug, but only looked at the 1440 place after your comment :(
 » 4 years ago, # |   +145 Problem F: wow, such idea, very insight.
•  » » 4 years ago, # ^ |   +48 Can't agree more. Who thought it is a good idea to put it on a contest? On ACM it wouldn't be that bad because we will have more time and I will have mnbvmar in team, but as a most valuable problem during a 2 hour CF round it sucks hard.
•  » » » 4 years ago, # ^ |   +41 It is good when people complain only about problem FAt least problems A, B, C and D weren't bad which is not the case for many other contests
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +20 EDIT: I refer to problem E here :D.Not sure whether this comment was sarcastic or not, but if you really want to than I also think that bignums is a lot of fun, especially when TL is very strict (I didn't solve that problem, but heard that from friends), so that you can't use Python.
•  » » » » » 4 years ago, # ^ |   +13 I solved F without using any bignums.
•  » » » 4 years ago, # ^ |   -32 I think W4yneb0t's comment is sarcastic.
•  » » » » 4 years ago, # ^ |   +110
•  » » » » » 4 years ago, # ^ |   -10 Sorry, I do not understand your previous comment context correctly.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +61 (Want to get my -100 comment)I'm the author. What is the problem? Swistakk is also welcomed. bignums is a lot of fun Really? It is a problem about bignums?
•  » » » 4 years ago, # ^ |   +18 The problem is that arriving at the solution is straightforward and the difficulty lies entirely in coding it. I personally don't find that very fun.
•  » » » » 4 years ago, # ^ |   +62 Wow. I was thinking about 2 hours on how to avoid O(n 2) for case 1 - 10 n. You are very smart person.And when I was writing then solution about a half of the time I was sitting with pen and paper.
•  » » » 4 years ago, # ^ |   +17 Lol, I referred to problem E when telling about bignums xD. Should have mentioned it :D. F is surely not about bignums, but I don't like F because it has very low ratio of "difficulty of getting idea right : difficulty of coding it" and that is more or less what I use to sort problems by how fun they are. We need to parse everything (hooray) and what is left to do is to make some rules producing (length of expression mod P-1, value mod P) for every expression. Only rule which I didn't figure out was those intervals, but I didn't think about it for longer than 15 seconds, but I guess it still can somehow be done without some brilliant ideas.Btw, I do not predict your comment to get downvotes ;p.
•  » » » » 4 years ago, # ^ |   +38 E: Division bigint by int isn't very hard, is it? Also I think that there is something else in this problem (not only bignums) and this something is what the problem about.F: Well, I added this parsing part to 1) combine some ideas in one problem 2) make it harder to code. But yes, the only hard part is those intervals and yes, it still can somehow be done. Maybe not brilliant but some ideas are needed.
•  » » » » » 4 years ago, # ^ |   +47 F: Then maybe the part about the intervals would make a good problem D or E.
•  » » » » » » 4 years ago, # ^ |   +37 I get your idea that "all this other stuff like parsing and other operations are kinda boring" and I partially agree. But it was hardest problem in a not usual round (finalists should be stronger, right?). So I decide to add some coding part (but you should agree that parsing is relatively easy in this problem).Maybe it is just unusual to see "parsing" problem in a short individual competition.
•  » » » » » » » 4 years ago, # ^ |   +20 "(finalists should be stronger, right?)" — do you expect tourist in round called "something's final" to be stronger than tourist in a usual round ; p?
•  » » » » » » » » 4 years ago, # ^ |   +38 Good point :)But rounds are made not only for tourist. Also I've expected much more AC for problem E. I'm sorry that E appeared to be more difficult than I've expected.
•  » » » » » 4 years ago, # ^ |   +30 E: Surely, E is pretty OK, this problem is by far not straightforward (however it is easier if you are not a retard like me and read that sum of b's is <=3e5). And dividing bignum by int is indeed lot easier than typical division, I thought that much more involved operations will be needed which led me to disliking this problem prematurely. Probably that problem without bigints wouldn't make much sense, so their existence here is very well justified.F: OK, if you say it took you 2 hours to tackle the case 1 - 10 n then I guess it is not easy, so it significantly increases ratio I mentioned :p. However I wouldn't call parsing "combining some ideas in one problem", that's very nice expression for that ;p.
 » 4 years ago, # | ← Rev. 2 →   +3 For DIV2 -C , I am counting the number of cycles and if they are != 1,I am adding it to the answer. I dont know how to handle the second array consisting of 0's and 1's. Any hint?
•  » » 4 years ago, # ^ |   +3 if the bitwise xor of all b i is 0 then you should add 1 to the answer
•  » » » 4 years ago, # ^ |   0 I did that but got WA.http://codeforces.com/contest/760/submission/24051551
•  » » » » 4 years ago, # ^ |   0 I am not allowed to see your submission, upload it somewhere else
•  » » » » » 4 years ago, # ^ |   0
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I got my mistake. In line 43, it should be i<=n.
•  » » » » » » 4 years ago, # ^ |   +1 too sad...
•  » » 4 years ago, # ^ |   +3 Parity
•  » » 4 years ago, # ^ |   +4 If my idea is correct, you need to have an odd number of 1's in the second array
•  » » 4 years ago, # ^ |   0 If the sum of b[i]'s is even, 1 more operation is needed.
•  » » 4 years ago, # ^ |   0 Just count the sum of ones, and if the sum is even, add 1 to the answer (you need to flip 1 bit), if the sum is odd it's ok.The sum of the flips has to be odd because once you make 1 cycle, if the flips are odd, the next cycle every piece will be flipped, but if the sum is even, they will pass every cycle with same orientation.
 » 4 years ago, # |   -10 How to solve Div1 D?
•  » » 4 years ago, # ^ |   0 Similar to counting number of different subsequencesHere you need subsequences with distinct adjacent symbols and for each k you should count how many such subsequence you can have with length k
•  » » » 4 years ago, # ^ |   0 Well I got that we can transform the problem to counting different subsequences, but I do not understand why do we need to find this number for every length. Can you explain in a bit more details.
 » 4 years ago, # | ← Rev. 2 →   +15 Understanding A-B div 1 took me the whole contest a even now i can't even understand the samples.
 » 4 years ago, # |   0 Nice taskset, but could anyone explain how to solve Div2E?
 » 4 years ago, # |   0 Can anyone explain, how to solve Div2_C?
•  » » 4 years ago, # ^ |   +6 Count the number of cylces in the graph, if the number of cycles > 1, then add that number to the changes.Furthermore, if the number of 1's in the second array is even, add 1 more to your changes.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 How does that works for this test : 72 3 4 7 6 1 60 1 0 0 0 0 0
•  » » » » 4 years ago, # ^ |   +3 The case would be invalid since array p needs to be a permutation.
•  » » » » » 4 years ago, # ^ |   0 Holy Shit I didn't saw that fucking permutation thing :(
•  » » » » » » 4 years ago, # ^ |   +1 I feel you lmao, reading is hard sometimes.
•  » » » » » » 4 years ago, # ^ |   0 didn't see*
•  » » » » 4 years ago, # ^ |   0 Your p i values don't include 5, so this isn't a valid input.
•  » » » 4 years ago, # ^ |   0 I understood the cycle part during contest... however didn't get the part about even number of 1's ... please explain why even number of 1 won't work
•  » » » » 4 years ago, # ^ |   0 If you have an even number of 1's, by the time a skewer gets back to its original position, it will be in the same orientation as it was, however if there are an odd number of 1's, it will get to it's starting position in the reverse orientation.Idk how good that explanation was, tell me if you need me to come up with an example.
•  » » » » » 4 years ago, # ^ |   0 Your explanation is great, but an example would be even more awesome :)I still have difficulty visualizing how all this permutation stuff works.Let's give names to 5 skewers: a, b, c, d, e. Rotated skewer a can be named as A. How will this original configuration change with time?
•  » » » » 4 years ago, # ^ |   +2 Imagine the skewer that starts at position 1. If p i makes one big cycle, then after n steps, this skewer will be back where it started. At this point, we would like the skewer to go through all these positions a second time in the opposite orientation. This only happens if it ends up back in position 1 after being flipped an odd number of times.
 » 4 years ago, # |   +9 I think understanding problem C was a harder challenge than solving it. (I made barbecue before but u know, it was horrible ...) Also I think preparing sth like A is not good because sb don't know about English calendar so they can't solve it as fast as other people!
 » 4 years ago, # |   0 Does anyone have any hack cases for Div. 2 A?
•  » » 4 years ago, # ^ |   0 I used m=2 and d=2 to hack one solution.There was off by one error in his code
•  » » 4 years ago, # ^ |   0 try these tests:input:7 6 correct output:6input:3 6 correct output:6input:1 5 correct output:5input:4 1correct output:5
 » 4 years ago, # | ← Rev. 2 →   0 The problems' statements weren't easy. I can't understand div2 D till now.
•  » » 4 years ago, # ^ |   0 I agree Div2 E was really hard to understand
•  » » » 4 years ago, # ^ |   0 I still don't understand Div2 E till now. Anyone care to explain?
•  » » 4 years ago, # ^ |   0 And Div 2 C
 » 4 years ago, # |   0 before 8VC cups. i would like to change my color.(to yellow(i was too close)).8VC cups changed my color, but to blue :/.why !?! ;_;.
 » 4 years ago, # |   +6 After I clicked on someone's solution on the Hacking panel, the solution turned red/ green. What does that mean? I couldn't find that in any FAQs.
•  » » 4 years ago, # ^ |   +21 red is solution that you read last.green are all other solutions you read.
 » 4 years ago, # |   +89 A moment of silence for those very few people who failed the system test :D
•  » » 4 years ago, # ^ |   +7 really sad when we use correct logic but just a silly = sign ruins it all up :|
 » 4 years ago, # |   +12 I had trouble understanding the problem statements (especially Div2 D), but the questions were really fun! Really happy about finding the DP solution for D.
•  » » 4 years ago, # ^ |   +3 do you mind sharing your approach for D? (div 2)
•  » » » 4 years ago, # ^ |   +7 Sure!First of all, imagine that the time ranges on the tickets work backwards (ie: buying a 90 minute ticket at time 100 covers all trips from times 11 to 100). Then, for trip t i, we would like to calculate the minimum cost c i. There are three options: Buy a ticket for one trip. This costs c i - 1 + 20. Buy a ticket for 90 minutes. Use a binary search to find the earliest trip t m that would be covered by this ticket. This costs c m + 50. Buy a ticket for 1440 minutes. Again, find the earliest trip that happened in the past 1440 minutes. This costs c m + 120. Total time is because of the binary search at each step.
•  » » » 4 years ago, # ^ |   0 Another way is to do exactly what statement says.  vi a(n); for (int & t : a) cin >> t; vi his(n, 0); his[0] = 20; cout << 20 << endl; for (int i = 1; i < n; ++i) { his[i] = 20; int paid1 = 0; for (int j = i - 1; j >= 0 && a[j] + 90 - 1 >= a[i]; --j) paid1 += his[j]; if (paid1 + his[i] > 50) { his[i] = max(50 - paid1, 0); } int paid2 = 0; for (int j = i - 1; j >= 0 && a[j] + 1440 - 1 >= a[i]; --j) paid2 += his[j]; if (paid2 + his[i] > 120) { his[i] = max(120 - paid2, 0); } cout << his[i] << endl; } No DP, no binary search. 144kk operations worst case = 500 ms.
•  » » » » 4 years ago, # ^ |   0 Maybe I'm misunderstanding your code, but this looks like DP to me — you're using the previous outputs (his[j]) to calculate the latest output (his[i]). Nice that there's no need for a binary search, though.
•  » » » » » 4 years ago, # ^ |   +3 thanks both of you, I understood the question now. I was trying greedy so couldn't get sample case 2 correct.
•  » » » » » 4 years ago, # ^ |   0 Well formally this is DP. But, come on, sum[i - 1] - sum[j] would be real DP :)
•  » » » » 4 years ago, # ^ |   +3 That is definitely DP, and instead of binary search, you just do linear search, so wouldn't work for slightly tighter constraints :)
•  » » 4 years ago, # ^ |   0 Now it will send you into space :)
 » 4 years ago, # |   +86 Nice time limit in E.
•  » » 4 years ago, # ^ |   0 My solution works about 350 ms. Have you ever heard about numbers in base 109?
•  » » » 4 years ago, # ^ |   -7 Once or twice. Look at times of AC's, they're kinda close to limit. But I know, that it's fair, one limit for everyone and things like this...
•  » » » 4 years ago, # ^ |   +15 TL of 1s is fine if the intended solution is 350s but bigger difference would be better (why not?), unless there exists a solution in slightly worse complexity that you wanted to fail. Also, I would say that the ratio TL/intendedSolutionTime should be bigger in problems with small time limit, because simple things take more percent of time there (e.g. reading or iterating over 1e6 values). Though, now I think that I don't consider such things/aspects myself when I'm choosing TL :D
•  » » » » 4 years ago, # ^ |   -10 Don't get your point. Suppose that reading takes time X. So we are probably interested in ratio (because X is independent of solution). . The lesser TL is, the greater will be.Also, I've consciously chosen TL to fail solutions like Radewoosh's one.
•  » » » » » 4 years ago, # ^ |   0 Your calculations are correct but I meant something else. You may assume that reading is constant but sometimes there are many ways to do something simple — so simple that participants don't care about it. For example, pushing numbers from the input to a vector (it's slower that writing to an already allocated array/vector) or using set instead of vector & sort & unique to count different values. So I meant a non-constant X that matters more for small TL. Also, I would expect bigger language differences for times close to 0 — I wouldn't set TL 0.1 if the intended solution is 0.03. Also, I've consciously chosen TL to fail solutions like Radewoosh's one. Ok, it explains an unusually small TL. I don't think choosing a good base for calculations was important in this problem but I won't argue about that (your decision was fine IMO).
•  » » » » » » 4 years ago, # ^ |   0 1 second isn't an unusually small TL for me.
•  » » 4 years ago, # ^ |   +33 Codeforces exceeded time limit when going through all the zeroes in hardcoded constants in your code.
 » 4 years ago, # |   +37 Upsolving!!!
•  » » 4 years ago, # ^ |   +5 waiting for problems to added in practise.
•  » » » 4 years ago, # ^ |   0 Does that happen immidietly ?
 » 4 years ago, # |   +11 Is there a time limit after which you can see other's solutions ?
 » 4 years ago, # |   0 Can anyone suggest how to solve Div2 B?
•  » » 4 years ago, # ^ |   +2 binary search the answer. allocate the answer to k. allocate k-1 to adjacent guys etc etc.. if not able allocate, search for lesser answer.
•  » » 4 years ago, # ^ |   0 there is already a discussion here.
•  » » 4 years ago, # ^ |   0 try to use BinarySearch :)
 » 4 years ago, # |   +6 Will these problems be added to archive, and when?
 » 4 years ago, # |   +7 So I was trying to access the problem for practice and suddenly this happened. Some kind of bug or hidden feature? o.O
•  » » 4 years ago, # ^ |   +14 This happend with me too, wtf
•  » » » 4 years ago, # ^ |   0 You went to my account? o.O
 » 4 years ago, # |   0 Div-2 D is written so badly . I am still not able to understand it. Can any one help?
•  » » 4 years ago, # ^ |   0 discussed here! already
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The analogy of trip was badly written I believe. The trips are instantaneous are point in time so to say. So if trips happen at 1 30 50 minutes. its better to take a 90 minute ticket/pass than 3 individual tickets. so I was doing.. min( dp(i-1)+20, dp(last trip 90min ago) + 50, dp(last trip 1440 ago + 120) ) etc.. Finished coding 5 mins after contest end :(
•  » » » 4 years ago, # ^ |   0 Yeah, I thought this was a little misleading.I understood the question as: You only pay for a bus ticket when you board a bus, and the length of the trips don't matter The t i values are the times when you board a bus The 90 minute ticket lets you pay once and board an unlimited number of buses for 90 minutes
•  » » » » 4 years ago, # ^ |   +2 If only the problem could say these words, I would have been better rated today :P
 » 4 years ago, # |   +68 Waiting for rating update...
•  » » 4 years ago, # ^ |   +7 Only few people have their ratings updated till now like tourist. Does the process of updating take too much time??
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Rating of Final Round participants is updated, not other two.
•  » » » 4 years ago, # ^ |   +3 i think there is a problem with the site right now.i see the updated rating of tourist when i open a profile and the previous rating when i open the contest section on profile.
•  » » » » 4 years ago, # ^ |   +11 They are looking for cheaters before computing rating. There are definitely no cheaters on the onsite event, so they have immediately calculated rating for them.
 » 4 years ago, # |   +2 When will be editorial?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 The editorial is here.
 » 4 years ago, # | ← Rev. 2 →   +111 Thank you, C++, for being so tolerant to typos... if (sums[left >= time]) -- passed pretests(!), WA 21 if (sums[left] >= time) -- AC
 » 4 years ago, # |   +4 Why the hell codeforces hides comments with too many negative votes? They are more interesting for me :D
•  » » 4 years ago, # ^ |   +2 Exactly like the problems, the interesting ones are harder to get.
 » 4 years ago, # |   +17 Congratulations to winners!The onsite participants only standings page is available by the link http://codeforces.com/contest/756/standings?list=2c7ac9b338b4906db6d101641a3b06b4.
 » 4 years ago, # |   +15 Codeforces rating system is kinda odd. If I had participated in div 1 round I would got a good increment (like +50), but with final round I get only +4. If there is no mistakes then the only conclusion I can make is not to participate in small-amount-of-participants rounds in future.
 » 4 years ago, # |   +58 Still waiting for rate changes
 » 4 years ago, # |   +5 Div1 version: Few failed systest, few hack attempt (and no successful hack), and few active participant (391 active of 656 registered) :/ Fortunately the problem is not bad :)
 » 4 years ago, # | ← Rev. 2 →   +49 I want t-shirts but I forgot participating in elimination round lol
•  » » 4 years ago, # ^ | ← Rev. 2 →   +46 You would have got 1000 dollars if you participated in the right contest and your problem is the T-shirt? :)) I think CF should implement a system such that you can't register at the wrong contest. And now, just for the record, was it possible for unqualified contestants to take part in the official round?
•  » » » 4 years ago, # ^ |   +20 I hadn't participated in elimination round so it was impossible to participate in final round. (Because I hadn't placed in top 200)I know I could have got \$1000 if I participated in both contests. It also makes me sad but t-shirts are more (because 50 participants won them)
 » 4 years ago, # |   0 Who are the local winners?
 » 4 years ago, # | ← Rev. 4 →   +34 I wonder,how fair is it to a guy , who attain 7'th place (world wide) in Codeforces . And gets 195 minus rating .. It even hearts me :'vAnd I also sometimes wonder how it feels to be Tourist . :)
 » 4 years ago, # |   +10 very good contest