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, sivukhin, 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:
That's funny, my dad and Joe Lonsdale are really close friends, I get to meet Joe all the time. :)
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!
Joe Lonsdale company make codeforces rounds, your dad's company don't, perhaps that's why they split up :V
They used to be in an investing company together. They were like best friends. They were the founders of the company, they worked together.
fair division!
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 ;)
Div 2 edition will be rated? UPD1: It is rated, it was unofficial at first thats why I asked.
Yes, it will.
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.
I agree, I'd like to do the same lol. :)
Snowden offended Barack Obama as well. He's got big balls.
I see the option to register for the Final Round, but I didn't place top 200 in the elimination round. Is it normal?
yap!
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.
Could you give me examples? We have some exclusions because of local finalists.
I'm a local finalist but I still get the "you can't register" message.
Please try again. Anyway no reason to worry, for sure you'll be registered correctly.
kyleliu is an example. His rank in the elim round was 852
I'm also a local finalist
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
I am here at Addepar.
When I clicked on register button , it's showed me that I am not eligible. So that's not a problem at all.
Rating will Dowa?
Hope another exciting contest, interesting problem set :)
Contest postponed by 10 minutes?
Sorry, it is because of onsite event.
damn everyone wants upvote!!
No, some people just want to stay informed on what's happening with the contest
Ah yes, imaginary internet points. They truly are what make the world go round.
Delayed !!
Why delay?
Damn, contest delayed by 10 minutes.
Please ignore this comment.
tourist GK hope u will 1st today , best of luck . zscoder u are just awesome zi song
hoping is for us. he is first normaly
R.I.P. English
am i the only one failing to understand problem c statement ?
I've read it multiple times and I still don't understand what the questions wants :(
the only way is to submit wrong and wrong til it gets pretest passed !
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.
Will you upload English statements?
Unable to understand Div 2 C. Never cooked barbecue. :/
Awful contest, problem B in russian was not full, so i couldn't solve it. Hope it will not repeat.
I think it wasn't too difficult to understand the statement. Also samples can help.
Same shit
Awesome contest, hope that i will pass system tests.
What was your logic for C?
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.
My bad I visualized it in terms of components.
Why is the number of 1's should be even? Why is this bad b[4] = {0, 1, 0, 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.
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).
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
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 -> .... -> x
So, 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.
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.
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.
Your approach will fail for the following case.
Correct answer is 1, not 0.
Oh no, tl on 80 test.
Will Div 1 and Final Round results be combined for the rating calculations or are those calculated separately?
This won't. There would be a combined contest for div1 and div2 if that was the case.
The Contest was good, spend a lot of time on B but still unable to come up with a solution...
Binary Search on answer.
what was the right limit? (the left limit was 1, sure)
I used M i.e number of pillows given as right limit.
code I used Binary search. but it didn't succeed.. Can you please see my code (what is wrong)
Paste it somewhere else i can't see from here
here
Your check function logic is not right. Here is link to my accepted code : here
Thank you :)
Can you explain your logic for div 2b ?
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)].
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.
I did it the same way. Any idea what the complexity would be?
Roughly O(sqrt(M))
good contest
Me when I read div2C
I need some SAT Reading skills to understand this problem :))))
How to solve D div1?
Hint* Dynamic programming + binary search
I guess I need some extra hints :)
Also are you sure you aren't talking about Div1 B?
So sorry, missread
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.
Div 1
is there anyone who passed div1 D with 26*n^2 solution instead of n^2 ? because if there is then #%#%@#$@#@
Yes, it runs in 1300ms. Use int instead of long long and do
if (dp[i][ii]==0) continue;
Strangely, this gave TLE with C++11 and passed in 1263ms with C++14. Never knew C++14 had so much better optimizations.
C++11
C++14
Never would have thought there is such a big difference in speed between int and long long.
Mine failed
I did, 1900ms.
edit: And yeah, I also spent 30 minutes optimizing it..
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 >_>...
Did almost everyone else do O(σ N2)? I just wouldn't imagine this passing along with modulo operations. I did waste some time figuring out how to reduce to O(N2). I did like D as a problem though.
You can do the dp in O(N2) by using a prefix sum table.
I did, with no optimizations at all. It passes in 1840ms.
Got it passed in 1.5 seconds.
The code running O(n2) times was the following (3.5 seconds locally on a random test):
First, branching gets in the way of instruction-level parallelism. So, get rid of branching by switching
f
toint64
(it wasint32
) and taking the remainder in an O(n2) outer loop (down to 3.05 seconds):This was still not enough: my compiler is
dmd
which sometimes produces suboptimal code. Locally, this is already fast withgdc
orldc
, but they are not present on Codeforces.So, the next thing was to streamline accesses to the transition table (1.55 seconds):
This looked fast already. But I added manual loop unrolling, just to be sure it happens (1.3 seconds):
Overall, the optimization effort took 5.5 minutes between the two submissions (one, two). Actually solving the problem took way longer for me.
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?
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)
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.Um, I'm confused, Why do you need lazy propagation for this?
kraskevich We commented at the same time :P
To update a range in O(log n).
..... I came up with this idea and then forbade it.... that's too stupid
struggled to debug div1 B for 40 min because of misreading 1440 as 1140 T T
Same here. I had WA 6 and was looking for a bug, but only looked at the 1440 place after your comment :(
Problem F: wow, such idea, very insight.
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.
It is good when people complain only about problem F
At least problems A, B, C and D weren't bad which is not the case for many other contests
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.
I solved F without using any bignums.
I think W4yneb0t's comment is sarcastic.
Sorry, I do not understand your previous comment context correctly.
(Want to get my -100 comment)
I'm the author. What is the problem? Swistakk is also welcomed.
Really? It is a problem about bignums?
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.
Wow. I was thinking about 2 hours on how to avoid O(n2) for case 1 - 10n. 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.
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.
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.
F: Then maybe the part about the intervals would make a good problem D or E.
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.
"(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?
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.
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 - 10n 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.
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?
if the bitwise xor of all bi is 0 then you should add 1 to the answer
I did that but got WA.http://codeforces.net/contest/760/submission/24051551
I am not allowed to see your submission, upload it somewhere else
http://pastebin.com/YhbCFETN
I got my mistake. In line 43, it should be i<=n.
too sad...
Parity
If my idea is correct, you need to have an odd number of 1's in the second array
If the sum of b[i]'s is even, 1 more operation is needed.
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.
How to solve Div1 D?
Similar to counting number of different subsequences
Here you need subsequences with distinct adjacent symbols and for each k you should count how many such subsequence you can have with length k
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.
Understanding A-B div 1 took me the whole contest a even now i can't even understand the samples.
Nice taskset, but could anyone explain how to solve Div2E?
Can anyone explain, how to solve Div2_C?
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.
How does that works for this test :
7
2 3 4 7 6 1 6
0 1 0 0 0 0 0
The case would be invalid since array p needs to be a permutation.
Holy Shit I didn't saw that fucking permutation thing :(
I feel you lmao, reading is hard sometimes.
didn't see*
Your pi values don't include 5, so this isn't a valid input.
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
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.
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?
Imagine the skewer that starts at position 1. If pi 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.
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!
Does anyone have any hack cases for Div. 2 A?
I used m=2 and d=2 to hack one solution.There was off by one error in his code
try these tests:
input:
7 6
correct output:
6
input:
3 6
correct output:
6
input:
1 5
correct output:
5
input:
4 1
correct output:
5
The problems' statements weren't easy. I can't understand div2 D till now.
I agree Div2 E was really hard to understand
I still don't understand Div2 E till now. Anyone care to explain?
And Div 2 C
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 !?! ;_;.
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.
red is solution that you read last.
green are all other solutions you read.
A moment of silence for those very few people who failed the system test :D
really sad when we use correct logic but just a silly = sign ruins it all up :|
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.
do you mind sharing your approach for D? (div 2)
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 ti, we would like to calculate the minimum cost ci. There are three options:
Total time is because of the binary search at each step.
Another way is to do exactly what statement says.
No DP, no binary search. 144kk operations worst case = 500 ms.
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.thanks both of you, I understood the question now. I was trying greedy so couldn't get sample case 2 correct.
Well formally this is DP. But, come on,
sum[i - 1] - sum[j]
would be real DP :)That is definitely DP, and instead of binary search, you just do linear search, so wouldn't work for slightly tighter constraints :)
Now it will send you into space :)
Nice time limit in E.
My solution works about 350 ms. Have you ever heard about numbers in base 109?
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...
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
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.
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 ofvector & 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.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).
1 second isn't an unusually small TL for me.
Codeforces exceeded time limit when going through all the zeroes in hardcoded constants in your code.
Upsolving!!!
waiting for problems to added in practise.
Is there a time limit after which you can see other's solutions ?
Can anyone suggest how to solve Div2 B?
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.
try to use BinarySearch :)
Will these problems be added to archive, and when?
So I was trying to access the problem for practice and suddenly this happened. Some kind of bug or hidden feature? o.O
This happend with me too, wtf
You went to my account? o.O
Div-2 D is written so badly . I am still not able to understand it. Can any one help?
discussed here! already
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 :(
Yeah, I thought this was a little misleading.
I understood the question as:
If only the problem could say these words, I would have been better rated today :P
Waiting for rating update...
Only few people have their ratings updated till now like tourist. Does the process of updating take too much time??
Rating of Final Round participants is updated, not other two.
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.
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.
When will be editorial?
The editorial is here.
Thank you, C++, for being so tolerant to typos...
Why the hell codeforces hides comments with too many negative votes? They are more interesting for me :D
Exactly like the problems, the interesting ones are harder to get.
Congratulations to winners!
The onsite participants only standings page is available by the link http://codeforces.net/contest/756/standings?list=2c7ac9b338b4906db6d101641a3b06b4.
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.
Still waiting for rate changes
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 :)
I want t-shirts but I forgot participating in elimination round lol
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?
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)
Who are the local winners?
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 :'v
And I also sometimes wonder how it feels to be tourist . :)
very good contest