mango_lassi's blog

By mango_lassi, history, 2 weeks ago, In English,
  1. Is there any way to view top rated users (with inactive users included)? (The "Rating (All)" tab would logically be this, but the list is just the same as "Rating". Further, it seems you need to login to even see the "Rating (All)" tab. What even is it?)
  2. Is there a list of users sorted by their max. rating?
  3. Is there some convenient way to show only European contestants or do any filtering other than by country, city or organisation?

I've tried to google for these but haven't found anything. If any of these lists are hidden somewhere on the site, or any external sites have these lists, please inform me.

Read more »

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

By mango_lassi, history, 4 weeks ago, In English,

The 2019 NWERC (Northwestern European regional contest) is tomorrow. You should see the scoreboard here once the contest starts.

There will be an online mirror here.

Let's discuss the problems after the contest!

Read more »

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

By mango_lassi, history, 7 months ago, In English,

This problem

I have a solution I think is correct but can't get it to pass, and apparently even my n^2 code (standard game theory iterating through all states solution) that should obviously work gets WA. They both give the same answers for random small inputs.

I can't find editorials or test data for the contest, so seeing so many teams have +1 or more in this problem, is there some tricky corner case I might have missed?

My code if it is of any interest:

code
n^2 code

Submissions: 54559534 54559186

Read more »

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

By mango_lassi, history, 7 months ago, In English,

I wrote this pretty short implementation of Heavy-Light Decomposition today:

code

It uses no recursion, which is nice, and takes data in the index-of-parent format, which can be a small plus or a large minus (I needed HLD over Aho-Corasick automata, so that input format is useful there). The intervals returned by get are in decreasing order, not in the order they are in the path, so something like adding an arithmetic sequence to a path is not possible.

The par-array just stores the parent of every node, ind gives the index of the node in the array HLD maps the nodes to, and pp gives the highest ancestor of the node that is mapped to the same continuous segment.

get returns a vector of at most $$$O(log(n))$$$ intervals, such that hld-index of every node on the path between $$$a$$$ and $$$b$$$ is in exactly one of the returned intervals. Specifically it returns all intersections of heavy paths with the path between $$$a$$$ and $$$b$$$ that are nonempty, in decreasing order (first interval has highest startpoint and endpoint). Clearly there are at most $O(log(n))$ such intervals, since every path contains at most $O(log(n))$ light edges, so at most $O(log(n))$ heavy intervals.

Get works since the path from $$$b$$$ to $$$pp[b]$$$ corresponds to the continuous interval $$$ind[pp[b]], ind[b]$$$ in the array HLD maps the nodes to, and therefore if $$$ind[pp[b]] \leq ind[a] \leq ind[b]$$$, $$$a$$$ is on the path between $$$pp[b]$$$ and $$$b$$$, and if $$$ind[a] < ind[pp[b]]$$$, then no node we go over is an ancestor of $$$a$$$, since the HLD-index of a node's ancestor is always less than the ind of the node.

Since get also finds the LCA, this also gives a nice LCA implementation:

code

Here's Caves and Tunnels solved with this HLD-implementation. Changing the tree format is pretty nasty, so the code isn't that clean :/

code

Read more »

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