By scott_wu, 6 years ago,

Hello everyone!

The final round of the 8VC Venture Cup will be held on Feb/28/2016 18:10 (UTC). ecnerwala and I are the problem setters. We want to thank GlebsHP and vnovakovski for help in preparing the contest, stella_marine for fixing the statements, and MikeMirzayanov for creating the Codeforces platform.

The contest is by invitation only to the top 200 contestants and top local contestants from Round 1 and contains six problems. We will also hold rated, out-of-contest participation for both div1 and div2 contestants — all three groups will feature slightly different problemsets. Local contestants will compete onsite in Silicon Valley. OpenGov, one of the featured 8 | VC companies, has been generous to host this competition at their offices; see more details about this awesome company below:

OpenGov transforms the way the world analyzes and allocates public money. With more than 700 government customers across 45 states in a rapidly expanding network, OpenGov is the market leader in cloud-based financial intelligence, budgeting, and transparency for government. The OpenGov platform transforms government financial data into intuitive, interactive visualizations for both internal government users and citizens.

8 | Partners, which consists of Joe Lonsdale (co-founder of Palantir) and his core team from Formation | 8, is a Silicon Valley venture capital firm that invests in industry-transforming technology companies. The team's investment portfolio includes companies such as those featured below, and a host of other top technology platforms that leverage modern algorithms and data science to power their core business processes. If you are interested to connect, please take a look at http://www.codeforces.com/8vc/apply.

##### PRIZES
• Overall 1st place — $2500 • Overall 2nd place —$1000
• Overall 3rd-5th places — \$500 each
• Overall 1-50th place — t-shirts with 8 | VC and company logos
• Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar, & 8 | Partners) and other Silicon Valley technologists
• Local top finishers — Opportunity to meet with leadership from 8 | VC portfolio companies

The scoring distribution will be standard for all three divisions: 500 — 1000 — 1500 — 2000 — 2500 — 3000

Good luck!

UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest.

Congratulations to the top overall contestants:

As well as the top onsite contestants:

Editorial can be found here.

Thanks for participating!

• +165

 » 6 years ago, # |   +56 Will problem set be same for both division and top 200 contestants ?
•  » » 6 years ago, # ^ |   -63 Базара нет.
•  » » » 6 years ago, # ^ |   -65 হালা বাংলায় লেখ
 » 6 years ago, # |   +21 what about difficulty of problems ?
•  » » 6 years ago, # ^ |   +27 As mentioned in a previous blog, the problems today is harder than in a regular Codeforces round. Since it alao has one more problem than usual, I'm afraid 2 hours is a bit short :((
•  » » » 6 years ago, # ^ |   +16 regular codeforces round means Div2 and Div1 combined rounds or Div1 rounds ?
•  » » » 6 years ago, # ^ |   +11 Will the Div.2 version be easier?
 » 6 years ago, # |   +20 I was invited to onsite though didn't get into top-200 in the Round 1. System doesn't allow me to register to "Final Round" because I am not in top-200. Should I go to onsite but compete in "Final Round (Div. 1 Edition)"?
•  » » 6 years ago, # ^ |   +55 Please, do not register on Div.1/Div.2 Editions. I'll register you on "Final Round" manually.
 » 6 years ago, # |   +66 stella_marine for translating the problems Where is Delinur then?
 » 6 years ago, # |   +24 what about the format of unofficial div. 1 and div. 2 rounds? how many problems in each, and will they contain the same problems, or some will be different?
•  » » 6 years ago, # ^ |   +64 The problemset for div. 1 will be a bit easier than from problemset for final round. Same, the problemsset for div. 2 will be a bit easier than the problemset for div. 2.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +212 "problemset for div. 2 will be a bit easier than the problemset for div. 2."Not really sure how that's possible...
•  » » » » 6 years ago, # ^ |   +30 He might mean that "The problemset for div. 1 will be a bit easier than from problemset for final round. Same, the problemsset for div. 2 will be a bit easier than the problemset for div. 1."
•  » » » 6 years ago, # ^ |   +26 div 1, div 2, div 3
•  » » » » 6 years ago, # ^ |   +108 better — div0, div1, div2
 » 6 years ago, # |   +67 Please let me register in div1 edition, I don't want to lose my ratings
•  » » 6 years ago, # ^ |   0 I am sure you will do great...
 » 6 years ago, # |   0 How will be the rating system distribution? :/I mean, will it be combined for all contestants, separated between Div1-Div2, or even Final-Div1-Div2?
•  » » 6 years ago, # ^ |   +4 Since problem set is not same for all 3 variants it can't be combined
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 ow, you caught me there... oh no :')(thanks anyway!)
 » 6 years ago, # |   -20 New srm awesome!!!!!!!
 » 6 years ago, # |   -10 My internet speed is fluctuating today, so I want to participate unoffiaclly (without registration). Is it possible?
•  » » 6 years ago, # ^ |   +9 Try virtual participation after the round maybe? I think that is the only way.
•  » » » 6 years ago, # ^ |   -18 Actually, I remember once solving problems without registration during contest, but there was recently a contest unofficial participation was disallowed because of large no. of official registrants. That's what I was confirming about, if the same will happen today.
•  » » 6 years ago, # ^ |   +3 You can wait 2 hours and then participate virtually
 » 6 years ago, # |   +75 Wow, official finals are harder than Div1 set and only the top 200 are participating, hello rating loss.
•  » » 6 years ago, # ^ |   +18 I'm also afraid of it.
•  » » » 6 years ago, # ^ |   +47 Who isn't? Good news is at least some of us will have a positive rating change :p
•  » » » » 6 years ago, # ^ |   0 The violet participants most likely will.
•  » » » » » 6 years ago, # ^ |   +26 Good!
•  » » » » » » 6 years ago, # ^ |   +44 Bad :/
•  » » » » » 6 years ago, # ^ |   +10 it seems you were not accurate, reds have the biggest rating change
 » 6 years ago, # |   +17 ?
 » 6 years ago, # |   -31 why contest will be started too late? Now it is mid-night.so...............
•  » » 6 years ago, # ^ |   +104 You might find it hard to believe, but the world has different time zones. I believe it's morning for the contest creators.
•  » » » 6 years ago, # ^ |   -18 if contest will be started codeforces usual time,i think most of them will be helpful.bcoz participant will be high .
•  » » » » 6 years ago, # ^ |   +29 If I got the right timezones, the usual Codeforces time is too early morning for the organizers. The current time allows for both Americans and Europeans as well as parts of Asia to have it at reasonable (not like 3am) time.Also I hope participants are not high while coding, doesn't seem like a good idea!
•  » » » » 6 years ago, # ^ |   +84 Oh God, how I like to be high while at contest.
•  » » » » » 6 years ago, # ^ |   +71 After an hour of making div.0 E fit into TL I actually feel high.
•  » » » » 6 years ago, # ^ |   +57 bcoz participant will be high Don't do drugs, kids!
•  » » » » 6 years ago, # ^ |   0 Lol You mean number of participants will be high haha
•  » » » » 6 years ago, # ^ |   +2 One has to wonder about the meaning of the term "High Elves".
 » 6 years ago, # |   +23 You can see onsite finalists only by link: http://codeforces.com/contest/627/standings?list=b0ba514e26c9f1c73337415d0f8927e6
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 Em, I think you have a bug there. I'm on the list, but I'm not an onsite finalist.
•  » » » 6 years ago, # ^ |   +15 It seems it shows finalists + current user. It will be fixed, but you can easily compare your result and onsiters!
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +75 It's not a bug, it's a feature!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 For some reason I can see myself in this list, despite not being onsite. Is it OK?P.S. Nevermind. It seems every contest participant can see himself even if he is not in the list.
•  » » 6 years ago, # ^ |   +3 Please remove me from that list. It seems somewhere I clicked the button that I don't supposed to click :-)
 » 6 years ago, # |   0 Please modify the problem statement of DIV2 Problem B, it's confusing and difficult to understand :(
 » 6 years ago, # |   +3 Not sure what to feel about the problemset
•  » » 6 years ago, # ^ |   -16 Problems were extremely derivative. Not original.
 » 6 years ago, # |   +3 Does anyone know what pretest 5 for Div2 C was? (task with XOR, sum given)
•  » » 6 years ago, # ^ |   +3 Probably a high integer value > 10^9 I got WA at it just because I was making sums till 30 bits only!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 You're right, just tested my solution with large numbers and it messed up, though I have no idea why at the moment =/Oh goddamnit got it. There I was thinking I was clever by using __builtin_popcount() to count the number of 1 bits in X. Turns out it takes int as a parameter, so it's cast down, disregarding the higher part. WAAH!
•  » » » » 6 years ago, # ^ |   +3 Ya you need to use __builtin_popcountll(). (Just figured this out yesterday)
•  » » » » 6 years ago, # ^ |   +13 Same thing happened to me. :( I spent some 45 minutes debugging it, when it struck me. FML.
•  » » 6 years ago, # ^ |   +8 Something like 10^12 10^12. My error was because of integer overflow.
•  » » 6 years ago, # ^ |   0 I failed this pretest many times.My mistake was that when sum == xor I divided the result by 2 and it's supposed to subtract 2 from the result because only the pairs (sum, 0) and (0, sum) are invalid.It passed pretests after that, hopefully systests too.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 I'm almost certain it was of the form (2 ^ i - 1) (2 ^ i - 1) for some positive integer i < 40. For instance: 65535 65535. I added a check in my code for this particular case (the answer is 2 ^ i - 2), and it passed the pretests.
•  » » » 6 years ago, # ^ |   0 If after removing the 1s in xor from s, we get 0, then we subtract 2, otherwise, answer=2^no. of 1s in x
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Why is that case different from other tests of the form i i? In all those cases you're supposed to subtract 2 from the answer.
•  » » 6 years ago, # ^ |   0 try 4 4 answer is 0
 » 6 years ago, # |   0 Somehow someone failed Div 2 C with the test : 7 5
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 correct answer 0?
•  » » » 6 years ago, # ^ |   0 Ya the guy in my room returned 4
•  » » » 6 years ago, # ^ |   0 Yes
 » 6 years ago, # | ← Rev. 4 →   +113 Holy shit, this went well. I really really hope I won't fail systests on anything (and that I'll become IGM).UPD: Epic win.My (short) solutions for A-E:A: Process odd bits of X first, even bits afterwards. If the k-th bit of X is 1, what does it contribute to the sum S? If it's even, what can it contribute to S? Special case: subtract 2 if a = 0 or b = 0 is possible.B: Straightforward, remember the number of orders per day ord(i) and compute a prefix sum of min(ord(i), B) and a suffix sum of max(ord(i), A) for every query — using Fenwick trees.C: Process the fuel stations from cheapest to most expensive, compute the optimal amount of fuel when exiting that station (you only want to reach the first cheapest); from that, we can find the amount when entering that station and thus the cost.D: Binary search. Special case: answer = minimum Ai. If we forbid some vertices, we can split the remaining tree into rooted connected components with roots hanging from "forbidden" edges. The DFS-traversal forms a path with some fully traversable subtrees hanging from it. We need tree DP for size/full traversability of subtrees and for a part of the path which goes down, and then merging those <= 2 downward paths + some fully traversable subtrees.E: The answer is the total number of submatrices — number of submatrices with sum  < K. For every left side of a submatrix, increment the right side, add violas and recompute the number of ways W to choose the top+bottom side. Remember the number of violas at every y-coordinate in a map<>, W is the sum of intervals in which they're the topmost. Small K means those intervals won't span more than K entries in the set<>, so just a few of them need to be recomputed.
•  » » 6 years ago, # ^ |   +3 Thanks for your quick mini-editorial! :DPlease, can you explain me why there is the special case in A?In test case S = 3 X = 3, the statement says that there are only two correct solutions ( (1,2) & (2,1) ). Why (0,3) & (3,0) are not good solutions?
•  » » » 6 years ago, # ^ |   0 Read the problem statement.
•  » » » » 6 years ago, # ^ |   -33 "Two positive integers a and b have a sum.."That 'positive' means greater than 0? I thougs 0 was positive too :(
•  » » » » » 6 years ago, # ^ |   +12 You learned something from math-English, then.
•  » » » » » » 6 years ago, # ^ |   +29 Yes. Thanks for your help! :)
•  » » 6 years ago, # ^ |   0 Congrats... they all passed :D
•  » » 6 years ago, # ^ |   +20 For D I implemented something like you describe, taking O(N) for each iteration of binary search, but it kept timing out on pretests (although I couldn't find a test case to make it take more than 1 second on my machine).
•  » » » 6 years ago, # ^ |   +30 Argh! Just realised that it isn't O(N) at all: a vertex with high degree will kill it. Somehow I neglected to test that.
•  » » 6 years ago, # ^ |   0 Hi! Could you please explain your approach to B? What about leftover production which can be used on later days? What are your fenwicks storing exactly ( prefix sum of min(ord(i), B) and a suffix sum of max(ord(i), A) ) because I don't understand how to find the answer from these. Please explain.I found an approach with 5 fenwicks, so I want to understand your approach, you only use 2 fenwicks :) thanks in advance
•  » » » 6 years ago, # ^ |   0 Production can be used only on the day it was produced, so no leftover.
•  » » » » 6 years ago, # ^ |   0 Whaaaat???? Each order requires a single thimble to be produced on precisely the specified day I misinterpreted it as Each order requires a single thimble to be delivered on precisely the specified day
•  » » » 6 years ago, # ^ |   0 I committed exactly the same mistake. How did you solve the mis-interpreted question with 5 Fenwick Trees?
 » 6 years ago, # |   0 10s too slow to submit F :(
 » 6 years ago, # |   +3 Solution for Div 2 C?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +24 dynamic programming on the bits. Let f(i, carry) be the solution considering the first i bits and if we have a carry (from the previous bits (0 , i - 1)).Now depending on the value of the ith bit of the sum and the ith bit of the xor we call the appropriate recursive calls.for example (assume carry is 0) if the value of the ith bit of the xor is 0, then we can put either (0, 0) or (1, 1). now if the ith bit of the sum is 0, then the first choice (0, 0) will have the solution f(i + 1, 0) and the second choice (1, 1) will have the solution f(i + 1, 1). and the rest of the cases are similar.Hope it helped.
•  » » » 6 years ago, # ^ |   0 And till how many bits do you call f? max(number of bits in S, number of bits in X) or some constant?
•  » » » » 6 years ago, # ^ |   0 I did it till number of bits of x. However, it might be wrong. I think it should be till the end of the max and to check finally if we have a carry or not.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Until the MSB of S is good enough. I mean, if we have some sum of 2 numbers (or 1) that have a bit bigger than the S's MSB set, it is bigger than S.On the other hand, checking until X's MSB doesn't guarantee correctness.
•  » » » » » 6 years ago, # ^ |   0 Same approach Me too failed systests :( idk y
•  » » » 6 years ago, # ^ |   0 Awesome approach. I couldn't solve it during the contest but your approach made things pretty clear. Since sum & xor is in the range of 10^12. We can continue till 40 bits approx.Attaching my link to the above approach implementation http://codeforces.com/contest/635/submission/16423712
•  » » 6 years ago, # ^ |   +9 There's also an O(sqrt(N)) meet in the middle solution in which you split the number into 2 groups of ~20 bits each.
•  » » » 6 years ago, # ^ |   0 This was the approach I tried during the contest. I missed the restriction about positive integers and I submitted it before the end of the contest so I did not have time to fix it.Dynamic programming solution is much elegant and saves a lot of time and memory resources.
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 Make use of the fact that each integer has a unique binary representation,so this means we don't have to use DP , simply check if the binary representation of s' is a subset of ~ x, where s'=(s-(sum of 1<
 » 6 years ago, # |   +7 I hope the System Test won't take forever to start.
•  » » 6 years ago, # ^ |   +3 UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 "Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest."Your hopes have been denied.
•  » » » 6 years ago, # ^ |   +1 FML.
•  » » » » 6 years ago, # ^ |   0 Well, congratulations on the spectacular performance :)
•  » » » » » 6 years ago, # ^ |   +8 Thanks, I really didn't expect to do this well (not after yesterday's debug output fuckup).
 » 6 years ago, # |   +11 Problem 627C - Package Delivery is quite similar with 241A - Old Peykan. You increased limits but solution idea is the same.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 It's just a tedious well-known problem in my opinion. I think I've even seen it on USACO although I can't find where it is..
•  » » » 6 years ago, # ^ |   +13
 » 6 years ago, # |   +4 O(N^2) somehow passes pretests for Div2B.
•  » » 6 years ago, # ^ |   0 Link to the code?
•  » » » 6 years ago, # ^ |   0 You can't see solutions while system testing is pending.
•  » » 6 years ago, # ^ |   0 Pretests are weak. My recursion also passes div1B:ll count(ll s,ll x){ if(s%2!=x%2) return 0; if(s==0) return 1; if(s
•  » » 6 years ago, # ^ |   0 If O(N^2), then not for long we will see, how it will fair with system test
 » 6 years ago, # |   0 What is WA5 in D (DFS)?
 » 6 years ago, # |   +9 The difficulty of problems was very appropriate: in all 3 contests, someone solved the second-last problem but no one solved the last problem.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I would say implementation of div2 F was way easier than div2 E or my approach is wrong (might be, cause it's pretty simple and obvious).
 » 6 years ago, # |   +36 D on div 1 is quite similar to this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=283The only difference is that that one is slightly harder: B is not necessarily equal to D
 » 6 years ago, # |   +34 When .o. forgets to do unsuccessful hacks......
•  » » 6 years ago, # ^ |   -9 No it's time to rise and shine! :P
•  » » » 6 years ago, # ^ |   +1 I want to know how much points he will get :)
•  » » 6 years ago, # ^ |   +26 .o. height rating increasing. I think historical in codeforces record +548
 » 6 years ago, # |   +40 I opened B's statement and thought "Ok, let's look for something shorter", then went to E which reminded me of this topic — http://codeforces.com/blog/entry/23613, which led me to this problem — http://codeforces.com/contest/364/problem/E and I spent the whole competition (well, after submitting A) trying to change some of the solutions of that problem in order to make them pass without understanding how those solutions worked :D So, yeah, I got what I deserved :D
 » 6 years ago, # |   0 Can Div1 D be solved using stack? Or something more tricky?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 You can use deque to maintain remained gas to get a O(m) solution instead of priority queue. but sorting is still needed.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +109 I've solved this task many times (include the first time I come up with this task by myself..)So the idea is: you can buy some gas, and at some point you can sell them at the price you bought it. When you are spending gas, spend the cheapest one When you arrive at a station, if there are gas more expensive than the one at this station, sell them all. And then buy as much as you can. When you arrive destination, sell all. You can use an array with 2 pointers (left, right) to keep a sorted list of gas with different price and amount.
•  » » » 6 years ago, # ^ |   0 Another view:Each cell has its travel cost (initially INF). When you visit gas station, you need to update the consequent N cells with cellcosti = min(cellcosti, stationcost). Let the starting point have 0 fuel cost.Of course you don't store the whole cellcost array, you store only events (add possible cost/remove cost) and sweep from left to right, taking the minimum cost on each segment. So you need a sliding window minimum (using deque). And I also used deque for events instead of 2 pointers.
•  » » » 6 years ago, # ^ |   +5 @cgy4ever: How can we maintain a sorted array in log(n)? Wouldn't insertion (new gas station) take O(n)?I was thinking a max-heap (for new station), and a min-heap (for traveling), and another simple array just to store the values. When we extract from either heap, we check from the array if value has been changed by the other heap, and update accordingly, before proceeding.
•  » » » » 6 years ago, # ^ |   +5 "if there are gas more expensive than the one at this station, sell them all." — it means when you want to insert x, you will remove all elements larger than x first, so after that you just need append x to the back.
•  » » » » » 6 years ago, # ^ |   0 Nice.
•  » » 6 years ago, # ^ |   0 not sure if correctsort all gas stations by costuse set of gas for gas station and for each gas station insert values and update answer
•  » » 6 years ago, # ^ |   0 div1D can also be solved with divide and conquer. solve(l , r) denotes min cost to reach rth point from lth point if we leave with full fuel at l. find the point with minimum fuel cost in range l + 1 to r — 1 , and buy all fuel here or as much as we need to reach rth point and now add solve(l , index) + solve(index , r) to it. Code
 » 6 years ago, # |   +10 At first glance, the problem 627E - Orchestra is very similar to 364E - Empty Rectangles.
•  » » 6 years ago, # ^ |   +31 I copied code of 364E of someone and modified it and pass pretest finally after some TLE >_< Hope I can get AC...
•  » » 6 years ago, # ^ |   +10 The problem 627C - Package Delivery is much easier version of 581E - Kojiro and Furrari.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +10 Hadn't I solved the problem 364E, I wouldn't have been spending long time thinking about the method of divide and conquer :( It seems the expected solution is way different from that of 364E.
 » 6 years ago, # | ← Rev. 2 →   +17 Duh, "Orchestra" was almost the same as http://codeforces.com/contest/364/problem/E I copy pasted more or less randomly chosen solution (I chose -XraY-'s one) and adjusted it to this problem, but got TLE. After that I compared those two problems more carefully and found out that the fastest out of >80 ACs to "Empty rectangles" runs 2,5s for n<=2500 and k<=6, and here we have 2s, n<=3000, k<=10, so there's no chance that those problems follow exactly the same idea >_>. Only difference in statements is that number of forbidden cells is not larger than 3000 in Orchestra while there is no such constraint in Empty Ractangles and in Empty Rectangles there needed to be exactly k forbidden cells and here less than k (but second difference is not making Orchestra easier).
•  » » 6 years ago, # ^ | ← Rev. 4 →   +43 My solution highly exploits the fact that n ≤ 3000. The main idea: Suppose the top side of the rectangle is in row i and the bottom side is in the row j > i. First iterate over all i in any order, for a fixed i iterate over j from r - 1 to i. When we have fixed i and j, we have a horizontal strip of cells, write down for each column how many 1s there are in this column in our strip into an array A. Having this array, it's easy to find how many good rectangles there are in this strip: for each non-zero item j in A we only need to know closest non-zero item to the left prev[j] of it and the first positon from[j] such that on the segment [j, from[j]] the sum of values in A is greater or equal to k.Now let's understand what changes when we decrease j by 1. Some values in A decrease by 1 (that's O(n) totally over all j), my idea is that there will be no more than k values of from we need to fix for each changed position j (actually, those positions are no more than k non-zero items to the left of j). I use this fact for a careful recalculation of array from. The main difficulty here is how to find a closest non-zero item to the left or to the right in A. I do that by using path compression technique that provides a very fast log factor. So, overall complexity after careful amortized is for all path compression and O(rnk) for all changes in arrays A and from. Overall complexity is . It has pretty easy implementation, though I spent about an hour on optimizing this solution to make it fit into TL, and still, it runs for about 1.7 sec on pretests :( UPD: formulas above had a mistake, I've lost the r factor in an analysis. Now it's fixed.UPD: 1918 msec on final tests. Damn I feel lucky :)
 » 6 years ago, # |   +24 3500 signed up for Div. 2, but only 1000 solved A? Where did the other 2500 go?
•  » » 6 years ago, # ^ |   +1 So that's part of why the rating change prediction plugin thing shows so much loss for me :D I did screw up royally, but -82 does seem like worse than my previous royal screwups.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Hah, royal screwups :)I hope you haven't trademarked the idiom, cause I'll have to use it a lot in the future :)
•  » » » » 6 years ago, # ^ |   0 This is a real English idiom, not one I made up :D (Though I admit I did hesitate after posting it if it actually existed, but Google says yes :D )
•  » » 6 years ago, # ^ |   0 3500 signed up but I only see 1300 in the standings. Still trying to figure out where the rest went...
•  » » » 6 years ago, # ^ |   +3 I felt like Div2A was less easy than usual. Maybe some got discouraged.
•  » » » » 6 years ago, # ^ |   0 Got the same feeling. Still, can you leave a competition after it starts?
•  » » » » » 6 years ago, # ^ |   0 Il you don't make any submission, your ranking doesn't change. But after one submission or more, it's too late...
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 You can sumbit and not be rated if your points are <= 0Why do you think some people spam bad hacks and get into a negative score?
•  » » » » » » » 6 years ago, # ^ |   +1 In today's contest, Hedgehogy got less than -2000 points and lost 74 points. There is something that I don't get.
•  » » » » » » » » 6 years ago, # ^ |   +1 Yeah, you're right. But I definitely saw it in some other contests. When people got negative points they got * above their name, which means they were out of the contest. Shrugs
•  » » » » » 6 years ago, # ^ |   0 Sadly yes, if you don't submit at all you're not counted — no rating change for you, no difference for other participants. This is a good thing for people who realize after registering that they cannot come, but I don't think that's a typical problem, so I'm not sure why it's so... Maybe they don't want to discourage anyone by such a loss or something?
•  » » » » » » 6 years ago, # ^ |   +1 Wow.. you can totally bail out if you realise the problems are harder than usual.Whilst it's only fair to let people leave the competition if they can't make it, it shouldn't really be allowed after the competitions started or after you've read the problems.
•  » » » » » » » 6 years ago, # ^ |   +4 What's the point? They'll keep sucking if they keep bailing out. Bail as many as you want. Nobody's loss except yours.
•  » » » » » » » » 6 years ago, # ^ |   0 Fair enough; you've got a point there:)
•  » » » » 6 years ago, # ^ |   0 Yeah, basically the brute force solution required a few more control structures than usual. :D (6 nested loops for the very brutest one)
 » 6 years ago, # |   0 Any hints to solve Div 2 B- Island Puzzle
•  » » 6 years ago, # ^ |   0 move 0 in both arrays in place 1 then check numbers in places 2 to n to each other
•  » » 6 years ago, # ^ |   +39 Ignore zero in both arrays and then check whether they are cyclic permutation.
•  » » 6 years ago, # ^ |   +9 Read the two lists of numbers. Remove the number 0 from both of them (can be done while reading) Rotate the second lists until it starts with the same number as the first list. Compare if every number in the same position of both lists are the same, if they are --> YES, else NO
•  » » » 6 years ago, # ^ |   -8 Same Idea as mine. But how is it possible that we all came up with the same solution. Is there a proof of its correctness somewhere?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +1 If we have the numbers 0 1 2 3 4 5, we can get all the possible positions of 0 when swapped with its neighbours:0 1 2 3 4 51 0 2 3 4 51 2 0 3 4 51 2 3 0 4 51 2 3 4 0 51 2 3 4 5 0Here we can see that moving the 0 doesn't affect to the relative order of the other numbers and we can move the 0 to whatever position we like. Then the 0 is not a necessary data we need to keep, we can throw it away.We know that we can't change the relative order of the other numbers, then we only can verify that the elements are in the same order.I don't know any other proof of correctness.Hope this helps you :)
•  » » » » 6 years ago, # ^ |   0 if 0 is in i index, then if you move statue in i-1 index to i then now i+1 index lost its access to 0. Similarly, if you move statue in i+1 index to i then now i-1 index lost its access to 0. So, only indices adjacent to i can make a move. This means no jumping over indices, only sliding. Imagine 0 is like a tiny bubble in a bottle of liquid, tilted 90 degree.
•  » » 6 years ago, # ^ |   0 ignore 0, and check if they are rotation of each other
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Edit. My idea fails.
•  » » 6 years ago, # ^ |   0 Proof for the method is welcomed.Thanks in advance.
•  » » » 6 years ago, # ^ |   +9 if you move 0 to left n times.. 0 will be in same position but remaining array will be rotated once. so you can generate all the rotated arrays. As you cannot place any non zero number between 2 numbers. So, any other array other than rotations cant be generated. Hope thats correct and helps :)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 Ignoring the zero in the arrays, the first array can be transformed into the second one only by some finite number of cyclic shifts, (i.e. 2nd array is a rotation of the 1st). That ordering does not change. If 1 is followed by 2 counterclockwise (or clockwise) in the first array, it has to be the same in the second array too.
 » 6 years ago, # |   +31 we are waiting for...
 » 6 years ago, # |   +29 Please post photos from the onsite contest. :D
 » 6 years ago, # |   +15 I'm looking at my code for Preorder Test (Div1 edition task E) for like an hour already and can't understand why it gets TLE#8.Can any of you guys help me find the bug? I don't think 8 million dfs calls can cause TLE in C++ when TL is 7 seconds.http://ideone.com/d46vuQ
•  » » 6 years ago, # ^ |   +41 Your algorithm becomes quadratic if you have a case where one vertex is connected directly to all of the remaining ones.
•  » » » 6 years ago, # ^ |   +13 Thank you so much, that's it!
 » 6 years ago, # |   +64 Pending System Testing is the most annoying sentence I've read in a while.
•  » » 6 years ago, # ^ |   +5 Notice this: " UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest. " So you don't lose time if you have to do something :)
•  » » » 6 years ago, # ^ |   +22 If I had something else to do I wouldn't be so on edge :D
•  » » » 6 years ago, # ^ |   +16 Hum, I think it's been more than an hour already...
•  » » 6 years ago, # ^ |   +8 I've always wondered: What is the purpose of this phase?
 » 6 years ago, # |   +5 Can anyone explain me, why the first one got WA4 but the second one got AC. Its not Long Long problems for sure, because max value in this task is about 1e9.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Typically, it can produce up to a thimbles a day. However, some of the machinery is defective, so it can currently only produce b thimbles each day.
•  » » » 6 years ago, # ^ |   0 so? in my first code it is clear. Only i had changed is first query. Fromupdate(1, 0, n - 1, d - 1, get(1, 0, n - 1, d - 1, d - 1) + min(a, q));to update(1, 0, n - 1, d - 1, min(TTT[d - 1], a * 1LL));`Where TTT is a previous values.
•  » » » » 6 years ago, # ^ |   +3 get(1, 0, n — 1, d — 1, d — 1) + min(a, q) can exceed a.
•  » » » » » 6 years ago, # ^ |   0 wow, really. Thank you, I was so dumb, lost 20 minutes, trying to fix it :c
 » 6 years ago, # |   0 the contest ended seconds before I got to send my code for problem Div2 E :( If it was submitted and passed system test I might have ended up in top 20 for the first time :3 anyway, If this code gets accepted later I'm not gonna forgive my slow internet connection >:(
•  » » 6 years ago, # ^ |   +51 system test finished and I still can't send my code :D this is feeling like forever :(
•  » » 6 years ago, # ^ |   +3 The same situation with Div2 C. I am waiting for check the last solution. Will it able only after changing of ratings?
•  » » 6 years ago, # ^ |   +16 Well :D, for anyone following this: I just sent my code for E and I got WA on test 10...It's both a relief and a pain in the butt :3 ... I really don't know how to feel about this contest anymore :\
•  » » » 6 years ago, # ^ |   +4 Be happy you learned stuff.
•  » » » » 6 years ago, # ^ |   0 Yes! I did learn to always open submit code page before reading the problem :D .. It was a nice contest anyway :) I'm happy I participated
•  » » » 6 years ago, # ^ |   +3 be happy for you had an idea ... i aspire to the day i read a problem like problem E and think of something ... i guess this requires time and hard work :)
 » 6 years ago, # |   +9 It seems like we have to wait all night again.
•  » » 6 years ago, # ^ |   0 System testing has started.
 » 6 years ago, # |   0 is an editorial going to be published ?and could anybody kindly give a hint on C div2 ?
•  » » 6 years ago, # ^ |   0 For C, focus on each bit of the numbers.
•  » » » 6 years ago, # ^ |   0 i got the bits part ... but does a backtracking solution pass?
•  » » » » 6 years ago, # ^ |   0 No, you would have something like 2^45
 » 6 years ago, # |   -17 Oh no!! If I registered, I'd be under 300 rank and I'd be blue right now ;_;
 » 6 years ago, # | ← Rev. 6 →   +46 DIV2 C can be easily solved using identity a+b=a^b +((a&b)<<1)from above identity,value of a&b=(a+b-(a^b))/2now using a^b and a&b,we can count ordered pair easily...for each bit in a^b and a&b,we have 4 possibilities(a^b) : (a&b)1 : 1 (not possible)1 : 0 (2 cases--> (ai=0,bi=1) or (ai=1,bi=0))0 : 1 (1 case--> (ai=1,bi=1))0 : 0 (1 case--> (ai=0,bi=0))code: 16412578complexity: O(log(x))
•  » » 6 years ago, # ^ |   +8 You probably meant a+b=a^b +((a&b)<<1)
•  » » 6 years ago, # ^ |   0 Really nice solution. Can u just give a prove of the identity you mentioned above?
•  » » » 6 years ago, # ^ |   +2
 » 6 years ago, # |   0 I'm in trouble when submitting problem Div2C. In my computer it gives the right answer for the first testcase, but when I submit it, it gives 0 as result, what is wrong. I've tried with Ideone an it gives the same as in my computer. Is anyone having the same problem as me? It's due to any particularity of the CF compiler that I'm not taking care in my code?https://ideone.com/csKtVPhttp://codeforces.com/contest/635/submission/16418542
•  » » 6 years ago, # ^ |   0 You access an element of the vx vector that does not exist, because it can have size less than nbits.When different compilers give different results, it's usually the programmer's fault for doing something that is not allowed.
•  » » » 6 years ago, # ^ |   0 Solved, Many thanks!!! :D
 » 6 years ago, # | ← Rev. 2 →   -17 Could div2 C be solved with the following logic? Now there is no point in finishing my question, if the comment is hidden :)
 » 6 years ago, # |   0 Can someone please tell why my solution fails? 16414129 I wrote y = Xor sum xor x Then replaced in the sum equation and then tried dp. Similar solution passes but mine fails. I cant get the bug!:(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 You are terminating your loop too early, so you fail when sum < xor. Just let i run till 60. Also your dp array is too small.
•  » » » 6 years ago, # ^ |   +1 Thank you I deserved that WA :(. Although i was happy to solve a good question
 » 6 years ago, # |   0 Could someone help me find an error in my submission for Div 1 C -http://codeforces.com/contest/634/submission/16414568My logic is that I store the values of the elements in two subtrees, only if they are smaller than a and b respectively. I also keep a count of all active elements (<=a/b) in the subtree as well. I can split the query into two halves and query the correct tree (b one before repairs and a one after repairs.) Could someone please tell me what is my logic/implementation error?
 » 6 years ago, # |   +39 When will editorial be published?
 » 6 years ago, # |   +7 When editorials will be published ?? Waiting....
 » 6 years ago, # |   +1 If anyone wants to know the solution to div 2 C or finals A please have a look at my blogspot.http://iamayushanand.blogspot.in
•  » » 6 years ago, # ^ |   0 why when !temp 1<
•  » » » 6 years ago, # ^ |   0 if temp==0 then there is a possibility that we will be counting 0 sum and sum 0 in our final answer
 » 6 years ago, # |   0 As the editorials haven't been published yet, here is my greedy approach for problem E from Div 2(635E — Package Delivery)Let us see for all i from 0 to m if it possible to reach some location such that X[i] ≤ location. Now, to travel the distance between the previous location and the new location, we will have to choose one of the P[i] such that they lie in range [location - n, location]. So let us keep a set of all those locations from which we can start prioritising by lower P[i] and greater X[i](this would also manage duplicates). Keep track of the starting pointer at each i, and for the next i, just iterate it until you reach the lower_bound on that X[i]-n. This is O(nlgn) because each element may be inserted in the set at most once.Now, this is slightly tricky and I'm not formally sure why it works(intuition rules :P ) but while we are removing these elements, we simply need to check if the element being removed is the best element, and if so, try to jump to X[j]+nth location(where j is that element). This works because for the X[j]+nth location the current set should correspond to the entire range that we would need to check otherwise as well. Now if we don't reach the X[i]th location after all this work, it means that we need to use some other value in the set to jump to the X[i]th location. Implementation of this is not so tough, just checking a few boundary cases is slightly tedious. This is my accepted submission: 16432717
 » 6 years ago, # |   +59 8VC has sent me some photos from the Final. I'm glad to see familiar faces. Share them with you: