Hi everybody.
The IndiaHacks finals will take place tomorrow (on Saturday). The contest is being organized by HackerEarth. Just after the official finals, the CF round will start (check-your-time) with almost the same problems. You can treat it as a standard CF round — there will be 5 problems in each of 2 divisions, and 2 hours to solve them. Two divisions will compete together on the problem set with 7 problems, with 2 hours to solve them.
I want to especially thank I_love_Tanya_Romanova for testing the problems, GlebsHP for help with making the CF round possible, and MikeMirzayanov for his awesome attitude and for the Polygon system. Setters: Lewin, k790alex, Sokolov, Errichto. Testers: I_love_Tanya_Romanova, Errichto. Small help: belowthebelt, raviojha2105, johnasselta, Radewoosh. And my big thanks to HackerEarth for inviting me to Bangalore, it's truly a vibrant city.
Some info only for 40 official finalists — Remember not to discuss anything until the CF round ends (so, at least 2 hours after the official contest ends). You will find all important information at link-to-the-contest. You can ask me questions by PM on CF or on HE, and I will put answers in the "Challenge Details" at the link provided. Do not use comments here because it can only confuse others. You can use some old blog about the IndiaHacks semifinals if you want to discuss something.
I wish you great fun and no frustrating bugs. Enjoy the contest.
Scoring: 500-1000-1500-2000-2500-3500-3500.
WINNERS
- jqdai0815, the only one to solve all 7 problems!
- JoeyWheeler
- jcvb
- andrew.volchek
- ikatanic
In the official finals there were technical issues with the stack size (it was again only 8MB) and constraints in E weren't correct at the beginning. We want to fix it as much as possible, without any guessing though — we can't say how much time did you waste because of something. If you were affected then write to me PM with the description of the situation. Your time penalties will be canceled (and maybe some earlier submission will be accepted, if only the stack size didn't allow you to get AC).
Editorial is being created here.
So the official finalists lose a rated contest? Or is there a way to add ppl to the standings afterwards and let them be rated?
Yes, they do lose a rated contest. It's impossible to add them to the leaderboard, too many differences in the problem set.
most of them will probably lose two rated contests if they are competing on-site
The top 19 or so won't be competing onsite. World level vs country level...
We always expect some photographs in these onsite contests :)
You'll get all the photo updates tomorrow during the live contest. :)
Where is the blog?
A rated div2 contest after a long time.
Welcome to India Errichto! :)
Idk why, but March is so adored by different cups and competitions. It's hard to take a part in all of them, especially (speaking about me) because there is some All-ukrainian competition in this time too (I'm talking about Math and Informatics). So, can someone explain me why March is so adorable?
Note changes in the blog — the contest will be combined for two divisions. Make sure to register again.
And the contest will last for 2 hours.
It's goodbye 1394(in Iran)
Happy new year(1395) :)))
Happy New Year !!!
I think these 2 contests (CROC & IndiaHacks) are closer time-wise in history of codeforces.
It's probably the technical issue that caused the divisions to be combined :P http://mirror.codeforces.com/blog/entry/43838
Thanks for Announcement .
The name of this contest is "IndiaHacks" and none of the writers or the testers of this contest are Indian. Not that I am saying it's a problem but it feels a little weird.
Still decreasing in Div 1 after 6 months :(
finally positive rating changes :))))
"The duration is 2 hours. I will try to inform you about the duration in a few hours."
Just in case the duration will change again.
Will the format be ACM or standard CF?
It's never written about ACM, so I think it will be standart CF
I submit a hack but get Unexpected verdict.I want to know what happened.
Oh god, not again.
I feel many submissions will fail in B. Will generating all strings give time out? And can it result in int overflow?
PS
My submission was running too slow for this test case
6 26
aa a
ab a
ac a
.. .. till az a
PPS — I was wrong. I forgot that we can only use a,b,c,d,e and f.
6*6*6*6*6 = 7776 won't time out and neither will 6^6 = 46656
You mean: 6^6 or 6^5?
Considering that the length must be between 2 and 6 inclusive, I really don't think that generating all the possible strings will be a problem
46656 total strings possible in worst case and O(n) operation per string. Why should it tle? And no chance of overflow as total possible strings are 46656
You can only use 'a', 'b', 'c', 'd', 'e' and'f', the test case you provided is invalid
I forgot that. My bad.
I think the test case is fine. You just have to put a check and skip the ones with 'g' and all. A possible hack case?
"It's guaranteed that... all ai and bi consist of only first six lowercase English letters."
Such a difference between B and C. I think in B condition "a.i!=a.i for all i!=j" makes the problem much more easy
Anyone can share his idea about D/E?
D. Max-flow with some tricks: Binary search on the answer. For answer being tested edge capacity equals maximum number of bears that can go through it. Calculate max flow. If it's more or equal than number of bears — such answer is achievable.
E. Let's consider graph with all non-forbidden edges (G). G' = G with vertex 1 removed. Proposal: Answer is possible if and only if following conditions are met:
Degree of vertex 1 in G more or equal than k.
Number of connected components in G' is less or equal k.
Each connected component in G' is connected to vertex 1 in G.
for E, I deduced this much, but how do we check the condition that number of connected components in G' <=k ?
Basically we do dfs. We need to do in some "trickier" way to fit in time. You can take a look on my solution: https://github.com/aeremin/Codeforces/blob/master/alexey/Solvers/6xx/653/Solver653E.cpp
You can check problem E from cf120 and it's tutorial
In D, I did the following:
1). I used binary search on the answer.
2). How can we check if we can use this weight?
I used the same approach but I am getting WA on test 44. Its because of precision issue, but I do not know how to handle this. LINK Correct answer: 1.000000 Output: 0.99991126
You should change condition in binary search. Now you EPS = 10^(-9) * x Correct condition is (Math.abs(r — l)*x / (Math.max(r,1)) > E)
Very old bump, but can someone explain the WA44 here? I don't get why my solution also only outputs 1 to 4 or so not 6 decimal places
D: Binary search on doubles the check with maxflow if you can travel to the end with each bear's weight equal to the current middle in the binary search.
There is a strange bug(?) happening during contests. Whenever I'm seeing someone's solution, and this solution is hacked or resubmitted, a message pops up and I automatically log out.
This happened in yesterday's contest too.
When will start system tests?
soon
How we can solve C simply?
I checked 7 possible states!!! :(
Iterate through the array if you found a bad index i then you must swap i or i + 1. So try swapping i and i + 1 with the rest of the array and check if each swap will fix all the bad indices.
OH MY GOD , thanks!!! My brain stopped in the contest. How stupid am I !!!
How to solve C? :)
I think that you can find all "invalid" positions (d[i] <= d[i+1] or >=, whatever), and brute force to "fix" it with swapping with any other position. It's not hard to see that invalid positions cannot be too many (i set limit = 9, but should be <= 6 or smth), and you need a O(1) checking then.
Ohh sh*t, that is actually too easy, thanks!
I timed-out when trying all swap combinations, I never thought to only check bad indexes! :(
How did you deduce that the number of invalid positions would be less than 6?
We touch only two numbers. Let indices be i and j. Proposal: swapping them can fix only positions {i — 1, i, i + 1, j — 1, j, j + 1}. So if we have more than 6 "bad" positions, some of them will still be unfixed.
Hello can you suggest similar problems! I fail on such easy to "see" problems.
I knew that 4th was binary search with max flows but I don't know much about any algorithm of Max Flow so couldn't solve it! I was solving C yesterday using ternary search( I didn't knew much theory about it ) and couldn't debug (although I had that sliding window in my mind) I switched to D but was unable to deduce the fact! So Probably I am having very bad contests these days! I think I should take a break :/
CantGetAnyACWhyAmISoWeak
I feel very stupid for not solving C.
CantGetAnyACWhyAmISoWeak
You just need more practice to improve your intuition! :)
BONUS: Thank you guys for C explanation!! I managed to code it :) I needed only to add a set to avoid counting two times swaps. Is there a way to avoid it?
16822666
Yes, see TooDifficuIt's code: http://mirror.codeforces.com/contest/653/submission/16814329
Considering positions i and i+1 as invalid if sequence[i] >= sequence[i+1], for odd i, or if sequence[i] <= sequence[i+1], for even i.
You must notice that if there are more than 6 invalid positions then a single swap won't fix it, so you output 0.
When there are 6 or less invalid positions just test all possible changes with them.
The complexity is O(6*N) if you check if one change makes the sequence nice in O(1).
A really nice implementation of the above idea by jqdai0815 : http://mirror.codeforces.com/contest/653/submission/16814329
Looks like problems in the Codeforces round are significantly easier than those in the HackerEarth round.
is it bad?
Well, this round was initially announced as an online mirror of IndiaHacks Algorithm Finals, but now it looks more like a different contest. Also, because the problems are different, it is not possible to easily compare results of this round with those of the official participants, and discussing problems is also more difficult because some problems are different, and all the problems are in a different order.
Not to mention that I spent some time solving problem E with a wrong constraint.
The period of waiting for systest to begin, is painful. They lock problemset and all. Maybe next time I'll contribute too so they can get more servers and keep them open for generic solving >.>
What is the idea for problem D ?, I tried to solve using binary search the maximum amount of weight one bear can deliver and check if it's possible using fordFulkerson. But I am getting WA in pretest 6. Am I missing anything ?
Did you copy-pasted Ford-Fulkerson from some site? I got WA when used some apparently broken max-flow algorithm from e-maxx.
Yes, I copied it from geeks for geeks.
I have copy-pasted one from https://web.stanford.edu/~liszt90/acm/notebook.html#file3 (called PushRelabel) and got AC. You can try to use it instead and check if it will got you AC.
Yeah I will try, thank you.
Damn it, integer overflow in D!!!. T^T
Feel the same...
I think you're lying, because you get ACs.
CantGetManiACWhyAmISoWeak?
standings
Thank you. I myself would not have found.
How to solve D. I figured out that if I obtain residual graph and after that find flow from each edge which is leaving source node than I have to distribute 'x' bears over them. But how to do it? Or I started wrong?
http://mirror.codeforces.com/blog/entry/43860?#comment-285024
Summary of HackerEarth problems:
How to solve F from this problem set?
If I'm not mistaken, if you already have a valid flow for x0, then the answer for x0 + 1 depends on the least amount of wood each bear needs to lose to create a new augmenting path from source to sink. If you compute, for each edge in the residual graph, how much wood each bear would need to lose to be able to send one extra bear through that edge (it can be 0 if the capacity is not full), then this is equivalent to finding a path from source to sink with the minimum maximum weight, which can be solved in O(E log V) by Prim or Kruskal.
It seems to be true. Thank you!
Yeah, that's how I solved this problem. The algorithm looks more like Dijkstra though, with the sum replaced with maximum. I tried to find the initial flow in the same way, but it didn't pass TL, so I had to add binary search.
my solution for B( codeforces) and E ( hackerearth) has a complexity n*26*q .code
Your program doesn't solve E from hackerearth.
Is there any way to access the problemset from onsite ? I tried looking at hackerEarth recent contest but couldn't find anything.
I think it will become available in a couple of days, maybe tomorrow.
Human stupidity at its finest: taking 50 minutes to notice a compilation error -.-'
(I'm so happy I did it before the contest ended, though :P)
I know that feel bro, same sh_t with MLE, so now I catched -27 to my rating
Wow so you just submit and don't wait to see whether you passed the pretests?
#justgrandmasterthings
I usually think so:
"I`m not going to waste my time on waiting, see later"
trying to solve next problem
forgot about previous
"OH WAIT WTF"
I had a similar issue.
I've noticed that I actually got TL for C only after successful submission for D. I'm pretty sure that I've seen "Pretests passed" for C and I think that it is the issue of twitchy status line that can change from "Running on pretest 7" to "Running on pretest 3" and back several times before showing an actual verdict. That's pretty sad :(
Why didn't my submission fail?
This line is wrong according to me
z.pb(a[k]+c[j][i-3]);It should be
z.pb(a[k]+c[j][0]);A total rating gain of 1 in last 24 hours
A total rating change of 0 in last 24 hours :P
Same here because I didn't participate in any of the contests :D
12 Legendary grandmasters! :D
Lol
Hashes with modulo = 264 passed :)
16814596
Time limit for this problem was intended to be 1 second or 2 seconds for slow languages like Java to avoid these kind of solutions.
jqdai0815 rating looks like typical track in Gravity Defied now
I have got WA 2 for Problem C.
But locally with gcc 4.9 and on ideone.com with C++ 14 this code on this test was executed correctly.
http://mirror.codeforces.com/contest/653/submission/16816483
What's wrong with this code?
Same thing with problem B.
http://mirror.codeforces.com/contest/653/submission/16817781
Somehow, tests for D allow to search only for blocking flow, not for maximum. Compare this accepted solutions: 16816698, 16816675 on next test:
(outputs are about 3 and 4, second one is correct).
There is a overflowing bug in my code of problem D.
My code will fail on the following case:
And some other participants also passed the system test using int to store the capacity of edges.
I think such test should be added and then to rejudge all submissions. And calculate rating afterwards.
Also a test like the one Kaban-5 mentioned should be added.
Like me... :)
What are results of onsite(?) round?
Если я не ошибаюсь, то задача F была один в один на Петрозаводском контесте пару лет назад. Вроде это был контест от tourist.
Всё же не один в один, но идеи очень похожи. link
HackerEarth scoreboard.
Remember, HackerEarth has different problems.
Can you guess or prove why does it work?
Problem E solution. 16820873
I suppose the testset in E is pretty weak. My original solution was too slow... so I just done some hacks in order to pass pretests: 16814798. I was super surprised when it was accepted on the main tests, because I'm almost 100% sure it's wrong.
Have you tried to find some tests?
I tried but has not found.
Yes, for my solution I can came up with simple test on ~50 vertices (constant that I use in the code) that will fail. Essentially, there will be one bridge that connects one separate vertex to the fully connected component, and all the edges except one from this component to this vertex will be prohibited. Then this edge won't be discovered and the vertices will be considered disconnected.
Another suspicious North Korean code!
http://mirror.codeforces.com/contest/653/submission/16815024
http://mirror.codeforces.com/contest/653/submission/16811842
I think those codes are really identical — simply some names are the difference (ex, 'doit' <-> 'foo', 'xvalue' <-> 'dat')
I actually didn't really care about those stuffs before, but my 2599 rating makes me bit sensitive. MikeMirzayanov, can you investigate these deeper?
Says the South Korean...
Regardless of nationality, The fact remains :)
(And the desire for IGM also remains..)
Is it possible that this is some sort of template or part of an official solution to an earlier (North Korean) problem?
Also, it's interesting that those nearly identical submissions still make a difference of 15 ms.
It's not possible that this is some sort of template — problem E from this round wasn't that typical. Considering the huge simillarities between those two submission (they only replaced some name) maybe they were a part of an official solution, but then there is no way to punish cheaters (since the same logic belong to any cheated code). So this should be decided upon other reasoning like previous decisions.
Also, "completely identical" submissions can easily make a difference of 15ms, so IMO it's not that interesting..
Will be tutorial?
Editorial Please!!!
wrong answer 1st numbers differ - expected: '1.0000000', found: '0.9999918', error = '0.0000082'What a sad story :((
What's the meaning of dsu? I can see it in Problem tags sometimes.
disjoint-set union. aka union find tree
Why has the round been made unrated ?
My rating is as low as it used to be. Nothing's unrated.
It was made unrated for a while because they were recalculating the ratings to remove cheating cases etc. I think.
Errichto And India
Thanks for coming to India. I hope you had a great time.
Image1
Image2
Image3
Image4
Image5