mridul1809's blog

Invitation to Topcoder Humblefool Cup 2019
By mridul1809, history, 6 years ago, In English

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 :

  1. Stonefeang
  2. Voover
  3. ei1333
  4. Kriii
  5. Egor

Top 5 Contestants from India :

  1. rahuldugarrd
  2. praran26
  3. jeel_vaishnav
  4. vishal4556
  5. teja349

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!

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mridul1809 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

looking forward to the contest..

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It clashes with Reply Code Challenge. Can it be shifted?

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Is it unrated? It didn't mention anywhere.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes you are right!

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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. :)

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you provide travel reimbursement to the onsite participants ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

hello i frankly don’t care about this so don’t include me in this without my consent because that is illegal.

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve the last question?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +27 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will there be Editorials for prelims ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea of the div1's 600?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +22 Vote: I do not like it

        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.)

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think i got it. Ty

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The answer to this image would be 3. But i think your approach gives 2. Am i wrong?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        It will be number of nodes with odd degree, not the number of leaves!

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorials will be published soon. Please keep an eye out for the link! :)

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The Applet updates sooner than web. Please wait for sometime it will soon be reflected on the web as well.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When is the onsite round?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will be between 29th and 31st March. Final dates are yet to be confirmed. We will contact you soon with the details. :)

    → Reply
»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Gawd questions mridul1809 Hope to see you set questions for Div1 F

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any updates on the editorial and final India ranklist?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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. :)

    → Reply