Hi everyone !!!
We at Indian Institute of Information Technology, Allahabad proudly share with you today The Humblefool Cup, the annual coding event of our Techfest Aparoksha’19, in memory of Harsha Suryanarayana (humblefool). It is being hosted and sponsored by none other than TopCoder, with the prizes worth 550 USD.
Humblefool was one of the first Indian red coders on Topcoder. He had been a member of Topcoder since 2005, and he was a proud graduate of Indian Institute of Information Technology, Allahabad. He was a fantastic competitor, participating in challenges across multiple tracks. More than that, he was a great community member and gave back to the community in countless ways. humblefool personally trained and motivated many other members to participate in SRMs and Marathon Matches.
Details
There will be 2 rounds :
- Qualifying Round – 15th March 2019 9:30 PM IST
- To participate in the Humblefool Cup you have to enter the Humblefool Cup Round.
- The top 30 students located in India will be invited to compete onsite at Indian Institute of Information Technology, Allahabad.
- The best ranked student in the qualifying round (not located in India) will be awarded $100 prize money.
- Onsite Round
- The top 30 best students from the qualifying round will compete onsite to win the Humblefool Cup Trophy and $450 in cash and goodies. The finalists will also receive Topcoder Humblefool Cup T-shirts.
For additional details please visit Topcoder Humblefool 2019
Make sure to get yourself registered at The College Fever and fill this google form (link) to be eligible for prizes.
See you in the arena!
EDIT : It will be a RATED FOR ALL contest.
EDIT 2: After an amazing contest between 550+ contestants , here is the final result :D
Thanks to everyone for an overwhelming response. Hope you guys had fun :D
Top 5 Contestants Overall :
Top 5 Contestants from India :
Congratulations guys!
Top 30 Indian contestants will be contacted soon! :D
Also Editorials are now available here!
The Editorial to 3rd question will be added soon! :)
EDIT 3: All the editorials have been published here.
The invitations to top 30 Indian participants have been sent. Please check your Email ID!
Auto comment: topic has been updated by mridul1809 (previous revision, new revision, compare).
looking forward to the contest..
The google form link is showing "You need permission. This form can only be viewed by users in the owner's organization." Please fix it.
Fixed!
It clashes with Reply Code Challenge. Can it be shifted?
Very sorry, it can't be shifted.
Is it unrated? It didn't mention anywhere.
Hey. It will be a rated contest. :)
Who all are eligible for the onsite rounds? What i interpreted is who have filled this google forms + top scorer in the online round + Indian ? Am i right?
Yes you are right!
filling of the google form is not mentioned on topcoder site. Some of the deserving people may not be eligible then as they might not have booked their tickets on college fever site
Hey. We will be floating that form again. Don't worry everything will be taken care of. We assure you that no deserving candidate will be left out. :)
Do you provide travel reimbursement to the onsite participants ?
Unfortunately we cannot provide with the travel reimbursements for onsite participants. Arrangements for stay will be made on a chargeable basis of Rs. 200/day including food.
hello i frankly don’t care about this so don’t include me in this without my consent because that is illegal.
Noice Display Image XD
See you in the arena :P
i don't get it, what arena
How to solve the last question?
The answer is almost always "yes".
On your machine, use the Sieve of Erathostenes to generate all primes up to 10^8 and run BFS to find the connected components of the graph. For small numbers of digits you'll find that the entire graph is connected, for larger numbers of digits there will be a few isolated vertices, a single component of size 2, and the entire rest of the graph is connected. Once you know this, the easiest way to get accepted is to hardwire the few exceptions into your solution. The entire solution you submit will then just check for the exceptions and answer "yes" otherwise.
The really top contestants should see that this approach will work before implementing anything. Here's how: Primes are not random, but in most aspects they behave as if they were. Thus, what we have here is essentially a large random graph with rather large vertex degrees (see below), and it is known that dense random graphs behave this way.
There are roughly n/ln(n) primes up to n. Among the 45,000,000 odd numbers with 8 digits, around 5,000,000 are prime. If you pick a prime number, there are 66 other odd numbers that differ from it in a single digit. On average, about seven or eight of those should be prime. (This is indeed true. For 8 digits the graph has over 20,000,000 edges, putting the average degree a little over 8.) If this was a truly random graph, the edge probability would put us significantly beyond the threshold probability from which essentially all graphs are connected. As it's not a truly random graph, we may expect some artifacts, but as it turns out, not too many.
Will there be Editorials for prelims ?
What is the idea of the div1's 600?
There is no strategy involved. Just greedily pick a single edge as a path, extend it as much as you can, remove it. Repeat until all edges are gone. I did this by choosing to start at a leaf each time.
Won't the answer be for all cost c, ans+=(number of odd degree node/2)*c. Odd degree in the graph with only edges of cost c?
No idea why this is downvoted at the moment, it's correct.
Consider only the edges with some specific weight c. If you have exactly 2k nodes with an odd degree, you need at least k paths (1), and it can always be done using k paths (2), so the contribution to the solution is k*c.
(1) Each path will change the parity of only two nodes: the one where it starts and the one where it ends.
(2) If you connect some k-1 pairs of odd vertices by new edges in a way that makes the graph connected, it will have an Euler tour. Remove those edges again to split the tour into k paths.
(Technical details: on a tree, a tour = a path, and you cannot have components in which all nodes have a positive even degree.)
Exactly my point. I proved this in contest in a different way, though got WA due to a simple bug in my code. Thanks for the neat proof.
I think i got it. Ty
one other approach is as follows:
iterate over all weights (1-100) and for each weight x add the edges in the graph that have weight x. now run a dfs and count number of components of graph and number of leaf nodes.
so for some weight x , count= sum of ceil(number of leaf nodes/2) over all components in current graph
for each x : ans +=(x * count of each x)
The answer to this image would be 3. But i think your approach gives 2. Am i wrong?
It will be number of nodes with odd degree, not the number of leaves!
The editorials will be published soon. Please keep an eye out for the link! :)
how does one check rating on topcoder? this was my first contest there and topcoder contest was very different. The rating changes in applet are reflected but doesnot show on profile. let me know if I am mising something
The Applet updates sooner than web. Please wait for sometime it will soon be reflected on the web as well.
When is the onsite round?
It will be between 29th and 31st March. Final dates are yet to be confirmed. We will contact you soon with the details. :)
Gawd questions mridul1809 Hope to see you set questions for Div1 F
Any updates on the editorial and final India ranklist?
Hey. The editorials will be published by tonight. The participants in ranklist will be contacted by tonight as well. Keep an eye out for invitations on email ID and Topcoder. :)