The registrations before 00:00 have been deleted, because the form didn't support teams. Please, register again if your registration has been affected.
VK Cup 2015 Final Round has ended two days ago. It's very likely that you've seen our previous posts. The last event to happen is online mirror of the final round. It will be held on Thursday, July 30th, at 19:00 Moscow time. Individual contestants as well as teams consisting of two people may participate in this round. Round duration is three hours, problems will be shuffled in comparison with to the original order. Both division participants may take part, but we want to warn 2nd division contestants that problemset may be hard for them. This round is a rated Codeforces round.
Finally, we want to thank all people that made this Championship. Following VK developers, Codeforces team members and the other people suggested their help to us while creating and preparing problems: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Kurpilyansky, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. We want to thank the people that helped us very much by testing our rounds and giving great advices: winger и AlexFetisov. Also we want to say thank you to all VK members that helped us to run the onsite Finals: burunduk3, Burunduk2, KOTEHOK and many others. Thank to all of them!
Good luck and have fun on our Online Mirror!
UPD: Note that during the round the team is allowed to use only one computer. This means that you may code/use console/succeed in solving problems in any other manner by using only one computer at time. The only thing that is allowed from two computers is reading the statements.
UPD2: Since this is a team contest, specially for your convenience we publish the encryped zip-archive with pdf-statements of problems: vkcup2015-mirror-statements.zip. When round starts, we'll publish a password for it.
UPD3: The round will use the dynamic scoring with 250 points step.
UPD4: Due to technical reasons the round starts at 19:20 Moscow time.
UPD5: Password for statements archive: vkcup4ever. Good luck!
UPD6: Online mirror has ended! Congratulations to winners:
- rng_58
- Zenith: I_love_Hoang_Yen, ngfam_kongu
- OrOrZZZ!: zld3794955, KFDong
- Petr team: Petr, ilyakor
- jcvb_matthew99: matthew99, jcvb
Also, my personal respects for a team "Petr team: Petr, ilyakor" for only solution for a problem Е in this mirror, user rng_58 and a team "Excited: YuukaKazami, jqdai0815" for two correct solutions for problem С.
Congratulations to a user rng_58 that showed that a single contestant can compete with teams consisting of two people!
Rating will be updated shortly.
UPD7: Editorial!
How it's going to be rated for teams?
Like this one I guess.
What is the rule for teamed participants?
UPD:Mike's comment on this topic
Why I can't register team?
Registration of teams will be available in 3-4 hours.
Thank you.
I'd really like to take part in this contest but I'm afraid of this problems. Is my fear justified shuld I pass this one?
don't think too much about rating . Pleasure of participating with high rated coder is much higher than fear of losing rating :)
So not to cast stones or anything, but I was wondering why you guys consider rating team members individually a good idea. It feels like they're completely different skill sets. I remember TopCoder had a special SRM that lasted 4 hours and had super hard problems and they didn't rate it. I don't think they ever rated something else than a SRM-style contest. Codeforces ratings were already suffering from the fact that you can choose not to participate after reading the problems. This way it's easy for some people to only choose favorable problem sets. I know that it's their problem and all that, but it still undeniably affects rating relevance.
To me it feels that this move wouldn't do any favors to rating relevance. Again, you guys know better than me what you're doing and what you want the rating to reflect. I just wanted to know what your official reasoning is :).
Well, rating doesn't have any real relevance to begin with. Long-term, it's a good measure of one's skill, but that's it.
The thing with not being rated if you don't submit doesn't bother me much. If you don't try, your loss. But I'm thinking of skipping out on this round due to teams and individuals being rated together. A team simply has a huge advantage in time that the combined rating doesn't reflect properly. In a round for teams only/primarily, this isn't a problem, but I can't help but feel I'm at a big disadvantage to some people. I suppose I'll decide based on how teamy the registrants' list gets.
As far as I see, we didn't have big rated rounds with both teams and individual registrants. So, your words about:
aren't confirmed with any previous experience. For us this round is a good possibility to see how rating works in such combined conditions.
We do have a way to compete individually against teams, I've done so in many Gym trainings. It may not be the same thing, but it's something I can base my view on.
The type of problemset is also important. When the problems require more thinking, the difference between teams and individuals are bigger.
Xellos wrote his first comment when there was nothing about 1 PC per team rule. During VK Cup online rounds participants were allowed to use 2 PC, and in my opinion (and from my experience) it actually gives huge advantage. In this case "more coding" problemset is even worse comparing to "more thinking" one.
you said that problems will be hard can you compare the level, I mean for example the easiest problem will be harder that E div 2 ?
also it will be as usual if I didn't submit any problem score will not change ?
Yes, if you not submit any problem, score won't change.
The easiest problem here is like Div2 D, others are much harder.
Just curious, what is "much" harder? Is it Div1 D and harder?
Participate and you'll see ;)
Anyway, the final standings on the on-site are available for you, so you can make an estimation regarding the difficulty level of problemset.
MaximShipko Did anyone see this black man before ?
I've saw him before, cause I've worked with him in Codeforces for about 2 years :-)
Never
racist
I would like to joking with it, but i won't hurt someone ;)
stingray, codeforces
How many problems will be ? How about scoring ?
http://codeforces.me/spectator/contest/562/standings
Maybe my question is stupid, but I cannot find the rules for teams anywhere: is it allowed to use more that one computer (i.e. write code in parallel)? I don't see it forbidden anywhere, but looking at the photos from onsite, there was only one computer per team...
Can you see any relevant way to control coding on more-than-one computer during online competition ? I think in this case it's free to be free :)
There are no relevant ways to prevent cheating in general, like 10 people participating from single account (some people do it, e.g. kutengine and black_horse2014), using multiple accounts, OCR'ing solutions for hacking, etc. Still, decent participants follow rules.
So, if organizers say that one team should use one computer (reasonable assumption, because these were the rules during the onsite), I will comply this rule.
Teams should use one computer. It will be a broadcast about it.
That's an extremely important information, which should be very well emphasized before start, broadcast at the beginning is definitely not sufficient. I bet vast majority of teams registered think that it will be possible to participate using 2 computers (being in completely different places, e.g. their own houses) and what do you think all those teams should do when they will see such a broadcast? They can't simply just use one computer if members are not in the same place.
Considering this and the fact that the onsite isn't at the same time as the online, I get the feeling that this contest is just begging people to cheat. I think I'll skip this one.
What does the fact you mentioned imply? I do believe that none of the finalists have spoiled problems to somebody participating in the mirror today because we explicitly asked them not to do that (and because I personally know more than a half of finalists, I really believe them). I don't see any other way how to use the fact that onsite isn't at the same time with the mirror.
Nonetheless, it's up to you whether to participate or not.
Come on, it's not like people who get to onsite rounds tend to help others cheat. I'm not exactly happy about teams+individuals (see my comment above), but screw it, I'm going to take it as a challenge.
Eh, sure, I like that logic. The only thing I have to lose is rating.
What's wrong with participating being in completely different places? They can still use Hangouts/Skype and coordinate who works with computer at any moment. Our OpenCup team (www.opencup.ru, it is mostly-russian ACM-like competition without age restrictions) does this all the time, and we never had any problems with coordinating, even with 3 people; with 2-people teams, it should be even easier.
(but yes, I agree that this should be announced more prominently; e.g. add it to this "You can register on the coming round individually or in 2-members team. It will be rated for all individuals and teams" green message displayed on top of the page)
to take part,or not to take part?!!that is the question...
I love that my presence in this contest but my rating :((
goodbye div1 and expert and Specialist and Pupil and Hello newbie for along time :((
Why am I not able to register? :/
This one has got to have the most bad-ass problemset this year!!! Am I crazy for participating?
Interesting, from registered list I can see that a lot of people preferred to participate individually
Some of us don't have a choice, because.
I don't have choice because of the same because :D
Auto comment: topic has been updated by Zlobober (previous revision, new revision, compare).
Can I be reading my code trying to find bugs(as if it was printed) while my teammate is coding a different problem?
No, you can't.
Why? If he print his code by once computer, why not?
No, you can't!!!
I missed the registration because codeforces was temporarily unavailable :/
It is available ~1.5 minutes more. Hurry up!
I did now, Thank you
Very very nice problems. Big congrats ! Looking forward for the editorial.
Isn't the complexity of F n log n?
Yes, it is.
Then why did I get TLE :(
http://ideone.com/VTzU2z can anyone take a look and tell me why TLE?
Your method for taking input is too slow. Use scanf instead
Oh no!!! not this problem.....anything but this :(
Just make it a rule that whenever input size is around 106 use faster input
This is O(n*sqrt(n))
IDTS ...... for each a[i] you run the loop log(a[i]) times, at most
Very difficult contest (even the easiest one is already at Div1-A level, and the second easiest is at Div1-C level), but nice problemset nevertheless.
Anyway, how to solve problem A and G?
you can solve A with suffix array
first of all prove that this greedy approach is correct: select the two strings which have most lcp and match them
i think every matching that isnt max can be made into a max matching with 2-switches which the value of the matching increases everytime i cant really explain it really good just prove this i think it can be proved
anyway after that we know that maximum lcp is between adjacent elements in suffix array so just get a set and a linked list and do stuff :D
it can also be solved using trie, insert all strings(of both kinds) into the trie
then do dfs to trie when you are in a node and you already have visited all its children then if you find at least one string from each kind inside subtree of that node then match them
Well... now im depressed because i implemented my first suffix array and didn't think about the easier way :((
A — make trie of all strings from input. Then dfs and matching strings from the subtrees of vertices before leaving vertex.#em8kM5
I just saw this lmao
Can someone tell me what is the original problems order in the official contest?
I'll post it with an editorial in a few minutes, but you may try to figure it out by yourself =)
I think C — F — E — D — G — A — B.
I guess that G from mirror is E from onsite
Last hour I was thinking of B, had a very very simple greedy solution but cannot prove it's correct and not writing a byte for it (as so few ppl solving it, I was thinking well the solution should be very complicated), and in last 10 minutes, I thought that the time was running out and I just write it (in 2 or 3 minutes) and it passes systest lolz
Most solutions for G failed as expected (including my own)
Now me and jerry can say we solved a problem that YuukaKazami, jqdai0815 and scott_wu didn't solve. We're at the IOI right now and since we're obviously not good enough to beat them here, this is pretty much the closest thing to an IOI victory as we could have hoped for :D (and also nomnomnom delicious, delicious rating points)
Test cases were too weak for the last question!!
Be more specific, what wrong solution passes them?
EDIT: If you mean the pretests, that's working as intended.
OMG we are #2, I can not believe that I am not dreaming.. Now my life is complete. Thank you so much ngfam_kongu for coming up with solutions for most problems (I am just a coding monkey).
This "Convex Hull" passed the first 20 test cases :)
It is in my solution to G.
I failed G, because of I used int in cross product. I'm bored this stuff :(
How to deal with the range merging in D ?
For operation 1 and 3 let's use a standard dsu data structure. In order to handle unions in range operations, let's keep a data structure that stores intervals. When one interval [L,R] is added, remove all intervals that intersects it, i.e intervals [L1,R1],[L2,R2],...,[Lx,Rx] such that L<=Ri and R>=Li. This intervals are going to be merged into one, so in the dsu data structure, we have to join the vertices that are in those interval: join(L1,L2),...,join(Lx-1,Lx). Each interval is added and removed once, so the number of join operations in linear;
You have thanked Errichto for his help in preparing the problemset . So shouldn't he have been restricted from participating in the contest ?
He gave us a great help while preparing an on-line round 2, not the Final round. So, there was nothing preventing him from participation in this round.