smjleo's blog

Invitation to UWCOI 2021 on CodeChef — Rated for All
By smjleo, 4 years ago, In English

Hey all!

We would like to invite you all to an online replay contest for UWCOI 2021. UWCOI 2021 is an OI-style contest hosted by the Computing Society of UWCSEA Dover which will be used to select members for the UWCSEA Dover team for the Singapore National Olympiad in Informatics for this year. It is also participated-in by several other schools in Singapore. The online replay contest will be held as a round rated for both divisions on CodeChef.

We have also held UWCOI 2020 around a year ago -- you can check out the problems here if you wish and get a feel for the contest.

Here are some details:

  • Time: Saturday, 19 December, 2020, 21:00 hrs IST (Indian Standard Time). Please check your local timezone here.
  • Contest Format: 7 OI-style tasks (tasks have subtasks) in 3 hours.
  • There is no time penalty for non-accepted verdicts; however, time will be used as the tiebreak.
  • The contest is rated for both divisions (all ratings).
  • There may or may not be interactive questions.
  • The writers are smjleo, astoria and kimbj0709.
  • The contest is hosted on CodeChef here.

We hope you enjoy the contest!

Update: We would like to thank our testers from CodeChef: Akash Whiplash99 Bhalotia, Aryan Aggu_01000101 Agarwala, Daanish 7dan Mahajan, Jatin jtnydv25 Yadav and Smit l_returns Mandavia for helping us out with polishing statements and testdata, as well as giving us valuable feedback.

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

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

We hope that the contest will be entertaining :) The contest should be able to cater to a wide range of skill levels — problems range from grey to red difficulty (hence, it is rated for all).

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

    Well, now that the contest is over and there are zero AKs, I feel slightly vindicated...

    Edit: Sorry for the confusing comment; I think it was really badly written. I just meant that after seeing the contest results, I think the analysis in parent comment of difficulty ranging from grey to red is accurate.

    We hope that all enjoyed the contest. I'd also like to apologise to those who didn't enjoy the contest, as some have told me they didn't enjoy it.

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

Is this the exact format of the official Team Selection Test? Because Singapore NOI is a 5-hour, 5-problem competition.

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

    Yes. Our goal wasn't necessarily to adhere to the difficulty/format of the actual NOI as we wanted a gradient more suited to our school.

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

What's full form of UWCOI ?

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

    United World College Olympiad in Informatics.

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

Hey,

I just did the onsite version of this contest (it was used to select the UWC school team to NOI), and I really enjoyed it! I think there's a good amount of variety and the contest caters well to many different skill levels. I believe many participants will enjoy the online version too!

Good luck to all!

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

Reminder — Contest starts in 20 minutes!

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

How to solve City Mapping 2?

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

    https://discuss.codechef.com/t/uwcoi21e-city-mapping-2-editorial/82429
    In case you missed it

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

    I have a deterministic solution for City Mapping 2.

    The idea is to use HLD to add nodes incrementally. We use $$$N$$$ queries at the start to find the root of the tree.

    Now when adding a node, call it $$$x$$$, we try to find which subtree the node should go into. Let's say that currently we know the node is contained in the subtree of $$$root_c$$$, where $$$root_c=root$$$ initially. Let the node at the end of the heavy path from $$$root_c$$$ be $$$node_h$$$. There are a few cases:

    • $$$lca(node_h,x)=node_h$$$. Add $$$x$$$ as a child of $$$node_h$$$.
    • $$$lca(node_h,x)=x$$$. $$$x$$$ is somewhere on the path from $$$root_c$$$ to $$$node_h$$$. We can use binary lifting to find the highest parent of $$$node_h$$$ that is a descendant of $$$x$$$ (that is $$$lca(node,x)=x$$$). Then we add $$$x$$$ there.
    • $$$lca(node_h,x)=w$$$ and $$$w$$$ has been found before. We set $$$root_c$$$ to the immediate child of $$$w$$$ that is a ancestor of $$$x$$$ and recurse as such. However, there is also a case where we need to make a new child of $$$node_h$$$ as $$$x$$$, so be careful of that.
    • $$$lca(node_h,x)=w$$$ and $$$w$$$ has never been found before. Similar to case $$$2$$$ we use binary lifting to find the highest parent of $$$node_h$$$ that is a descendant of $$$w$$$. Then we add both $$$w$$$ and $$$x$$$ there.

    Now, this part of the algorithm uses at most $$$N \log N$$$ queries on the worst case. Since $$$node_h$$$ is on the heavy child, every time we change $$$root_c$$$, the size of the search space we have to consider for $$$x$$$ at least halves. Then when we are adding $$$x$$$, we may have to do some $$$lca$$$ queries. Each $$$lca$$$ query also halves the search space.

    Thus, the algorithm uses $$$N+N \log N$$$ queries total.

    Code: https://www.codechef.com/viewsolution/40551263

    → Reply