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.
ABOUT 8 | PARTNERS
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!
Will problem set be same for both division and top 200 contestants ?
Базара нет.
হালা বাংলায় লেখ
what about difficulty of problems ?
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 :((
regular codeforces round means Div2 and Div1 combined rounds or Div1 rounds ?
Will the Div.2 version be easier?
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)"?
Please, do not register on Div.1/Div.2 Editions. I'll register you on "Final Round" manually.
Where is Delinur then?
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?
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.
"problemset for div. 2 will be a bit easier than the problemset for div. 2."
Not really sure how that's possible...
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."
div 1, div 2, div 3
better — div0, div1, div2
29.02.2016 00:10UTC+6 -- это же жесть
Программист — жаворонок? Не верю своим глазам :)
Please let me register in div1 edition, I don't want to lose my ratings
I am sure you will do great...
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?
Since problem set is not same for all 3 variants it can't be combined
ow, you caught me there... oh no :')
(thanks anyway!)
My internet speed is fluctuating today, so I want to participate unoffiaclly (without registration). Is it possible?
Try virtual participation after the round maybe? I think that is the only way.
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.
You can wait 2 hours and then participate virtually
Wow, official finals are harder than Div1 set and only the top 200 are participating, hello rating loss.
I'm also afraid of it.
Who isn't? Good news is at least some of us will have a positive rating change :p
The violet participants most likely will.
Good!
Bad :/
it seems you were not accurate, reds have the biggest rating change
?
why contest will be started too late? Now it is mid-night.so...............
You might find it hard to believe, but the world has different time zones. I believe it's morning for the contest creators.
if contest will be started codeforces usual time,i think most of them will be helpful.bcoz participant will be high .
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!
Oh God, how I like to be high while at contest.
After an hour of making div.0 E fit into TL I actually feel high.
Don't do drugs, kids!
Lol You mean number of participants will be high haha
One has to wonder about the meaning of the term "High Elves".
Впервые пишу контест в свой день рождения :) и могу точно сказать, что как минимум за четыре следующих года такого не повторится :)
You can see onsite finalists only by link: http://mirror.codeforces.com/contest/627/standings?list=b0ba514e26c9f1c73337415d0f8927e6
Em, I think you have a bug there. I'm on the list, but I'm not an onsite finalist.
It seems it shows finalists + current user. It will be fixed, but you can easily compare your result and onsiters!
It's not a bug, it's a feature!
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.
Please remove me from that list. It seems somewhere I clicked the button that I don't supposed to click :-)
Please modify the problem statement of DIV2 Problem B, it's confusing and difficult to understand :(
Раз 10 перечитал Д, но так и не смог полностью понять что требуется.
Not sure what to feel about the problemset
Problems were extremely derivative. Not original.
Does anyone know what pretest 5 for Div2 C was? (task with XOR, sum given)
Probably a high integer value > 10^9 I got WA at it just because I was making sums till 30 bits only!
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!
Ya you need to use __builtin_popcountll(). (Just figured this out yesterday)
Same thing happened to me. :( I spent some 45 minutes debugging it, when it struck me. FML.
Something like 10^12 10^12. My error was because of integer overflow.
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.
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 is2 ^ i - 2), and it passed the pretests.If after removing the 1s in xor from s, we get 0, then we subtract 2, otherwise, answer=2^no. of 1s in x
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.try 4 4 answer is 0
Somehow someone failed Div 2 C with the test : 7 5
correct answer 0?
Ya the guy in my room returned 4
Yes
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.
Thanks for your quick mini-editorial! :D
Please, 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?
Read the problem statement.
"Two positive integers a and b have a sum.."
That 'positive' means greater than 0? I thougs 0 was positive too :(
You learned something from math-English, then.
Yes. Thanks for your help! :)
Congrats... they all passed :D
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).
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.
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
Production can be used only on the day it was produced, so no leftover.
Whaaaat????
I misinterpreted it as
I committed exactly the same mistake. How did you solve the mis-interpreted question with 5 Fenwick Trees?
Я бы смог решить задачу С с помощью ДП, если бы в качестве одного из двух неизвестных чисел подходил ноль. Не успел придумать, как от него избавиться.
Так в этой ситуации достаточно отнять 2 от результата :-)
Ключевые слова — "не успел" :(
10s too slow to submit F :(
Solution for Div 2 C?
dynamic programming on the bits. Let
f(i, carry)be the solution considering the firstibits and if we have a carry (from the previous bits(0 , i - 1)).Now depending on the value of the
ithbit of the sum and theithbit of the xor we call the appropriate recursive calls.for example (assume
carryis 0) if the value of theithbit of the xor is 0, then we can put either(0, 0)or(1, 1). now if theithbit of the sum is 0, then the first choice(0, 0)will have the solutionf(i + 1, 0)and the second choice(1, 1)will have the solutionf(i + 1, 1). and the rest of the cases are similar.Hope it helped.
And till how many bits do you call f? max(number of bits in S, number of bits in X) or some constant?
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.
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.
Same approach Me too failed systests :( idk y
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://mirror.codeforces.com/contest/635/submission/16423712
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.
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.
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<<position of bits set in x))/2, if s is divisible by 2. In other cases(s' is odd, or s' is not a subset of ~ x) output is 0.
как Б(про сумму и ксор) решать нормально? Сам писал что-то типа meet-in-the-middle. Для каждой половины битов писал ДП dp[i][sum] = колво пар чисел длиной i бит с суммой sum. переходы понятны.
Нужно переписать уравнение n^(s - n) = x в виде n^x + n = s. Дальше просто динамика по битам.
Что за динамика по битам? Можно подробнее? :)
Динамика на каком бите стоим (начиная с младшего) и перенеслась единице к нам или нет. Перебираем текущий бит и делаем переход.
Верно ли, что ответ в этой задаче всегда либо степень двойки, либо степень двойки минус два?
P.S. Либо "невозможно".
0 = 21 - 2 :)
Точно :)
s - x = удвоенная сумма битов, которая стоит у обоих чисел
С учётом этого, если данное число вообще может быть правдой (
), то число пар это 2__builtin_popcountll(x). С учётом того, что считаем положительные пары, придется ещё вычесть 2 если s = x.
I hope the System Test won't take forever to start.
UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest.
"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.
FML.
Well, congratulations on the spectacular performance :)
Thanks, I really didn't expect to do this well (not after yesterday's debug output fuckup).
Problem 627C - Package Delivery is quite similar with 241A - Old Peykan. You increased limits but solution idea is the same.
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..
Here it is! http://usaco.org/index.php?page=viewproblem2&cpid=283
O(N^2) somehow passes pretests for Div2B.
Link to the code?
You can't see solutions while system testing is pending.
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<x) return 0; if(s%2==1){ return 2*count(s/2,x/2); } else{ return count((s-2)/2,x/2) + count(s/2,x/2); } }
But it is O(s+x) in worst case.
What is WA5 in D (DFS)?
The difficulty of problems was very appropriate: in all 3 contests, someone solved the second-last problem but no one solved the last problem.
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).
D on div 1 is quite similar to this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=283
The only difference is that that one is slightly harder: B is not necessarily equal to D
When .o. forgets to do unsuccessful hacks......
No it's time to rise and shine! :P
I want to know how much points he will get :)
.o. height rating increasing. I think historical in codeforces record +548
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://mirror.codeforces.com/blog/entry/23613, which led me to this problem — http://mirror.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
Can Div1 D be solved using stack? Or something more tricky?
You can use deque to maintain remained gas to get a O(m) solution instead of priority queue. but sorting is still needed.
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.
You can use an array with 2 pointers (left, right) to keep a sorted list of gas with different price and amount.
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.
@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.
"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.
Nice.
not sure if correct
sort all gas stations by cost
use set<start, end> of gas for gas station and for each gas station insert values and update answer
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
At first glance, the problem 627E - Orchestra is very similar to 364E - Empty Rectangles.
I copied code of 364E of someone and modified it and pass pretest finally after some TLE >_< Hope I can get AC...
The problem 627C - Package Delivery is much easier version of 581E - Kojiro and Furrari.
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.
За 16 минут до конца: наконец-то, с 6 попытки сдаю B и решаю пойти ломать решения.
За 13 минут до конца: думаю всё-таки прочитать С, но решать — вряд ли.
За 10 минут до конца: осознаю какой я идиот, что раньше не прочитал С.
За 2 минуты до конца: ВА на втором сэмпле. Быстро разбираю этот сэмпл для поиска ошибки в решении.
За 30 секунд до конца: понял в чем ошибка, исправляю.
За 10 секунд до конца: засылаю.
За 1 секунду до конца: осознаю, что неправильно исправил ошибку.
Duh, "Orchestra" was almost the same as http://mirror.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).
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 :)
3500 signed up for Div. 2, but only 1000 solved A? Where did the other 2500 go?
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.
Hah, royal screwups :)
I hope you haven't trademarked the idiom, cause I'll have to use it a lot in the future :)
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 )
3500 signed up but I only see 1300 in the standings. Still trying to figure out where the rest went...
I felt like Div2A was less easy than usual. Maybe some got discouraged.
Got the same feeling. Still, can you leave a competition after it starts?
Il you don't make any submission, your ranking doesn't change. But after one submission or more, it's too late...
You can sumbit and not be rated if your points are <= 0
Why do you think some people spam bad hacks and get into a negative score?
In today's contest, Hedgehogy got less than -2000 points and lost 74 points. There is something that I don't get.
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
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?
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.
What's the point? They'll keep sucking if they keep bailing out. Bail as many as you want. Nobody's loss except yours.
Yeah, basically the brute force solution required a few more control structures than usual. :D (6 nested loops for the very brutest one)
Any hints to solve Div 2 B- Island Puzzle
move 0 in both arrays in place 1 then check numbers in places 2 to n to each other
Ignore zero in both arrays and then check whether they are cyclic permutation.
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?
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 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0
Here 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 :)
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.
ignore 0, and check if they are rotation of each other
Proof for the method is welcomed.
Thanks in advance.
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 :)
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.
we are waiting for...
Please post photos from the onsite contest. :D
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
Your algorithm becomes quadratic if you have a case where one vertex is connected directly to all of the remaining ones.
Thank you so much, that's it!
Pending System Testing is the most annoying sentence I've read in a while.
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 :)
If I had something else to do I wouldn't be so on edge :D
Hum, I think it's been more than an hour already...
I've always wondered: What is the purpose of this phase?
http://pastebin.com/dqJRLfCU http://pastebin.com/pfxyMvFQ Task D Div2.
Can anyone explain me, why the first one got WA4 but the second one got AC. It`s not Long Long problems for sure, because max value in this task is about 1e9.
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.
so? in my first code it is clear. Only i had changed is first query.
From
update(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.
get(1, 0, n — 1, d — 1, d — 1) + min(a, q) can exceed a.
wow, really. Thank you, I was so dumb, lost 20 minutes, trying to fix it :c
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 >:(
system test finished and I still can't send my code :D
this is feeling like forever :(
The same situation with Div2 C. I am waiting for check the last solution. Will it able only after changing of ratings?
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 :\
Be happy you learned stuff.
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
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 :)
It seems like we have to wait all night again.
System testing has started.
is an editorial going to be published ?
and could anybody kindly give a hint on C div2 ?
For C, focus on each bit of the numbers.
i got the bits part ... but does a backtracking solution pass?
No, you would have something like 2^45
Oh no!! If I registered, I'd be under 300 rank and I'd be blue right now ;_;
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))/2
now 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: 16412578
complexity: O(log(x))
You probably meant a+b=a^b +((a&b)<<1)
Really nice solution. Can u just give a prove of the identity you mentioned above?
Add two numbers without using arithmetic operators
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/csKtVP
http://mirror.codeforces.com/contest/635/submission/16418542
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.
Solved, Many thanks!!! :D
Could div2 C be solved with the following logic?
Now there is no point in finishing my question, if the comment is hidden :)
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!:(
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.
Thank you I deserved that WA :(. Although i was happy to solve a good question
Could someone help me find an error in my submission for Div 1 C -http://mirror.codeforces.com/contest/634/submission/16414568
My 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?
When will editorial be published?
When editorials will be published ?? Waiting....
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
why when !temp 1<<count — 2 ?
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
8VC has sent me some photos from the Final. I'm glad to see familiar faces. Share them with you:
https://get.google.com/albumarchive/pwa/114907919772955385569/20168VCVentureCupFinal?authuser=0&authkey=Gv1sRgCIfk3s78m9T6sgE&feat=directlink