Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Ghassane's blog

AtCoder Beginner Contest 294
By Ghassane, history, 6 days ago, In English

I could not find the usual discussion post about the most recent atcoder contest, so I'm posting here. How to solve problem G?

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

»
6 days ago, # |
  Vote: I like it +20 Vote: I do not like it

G: use ETT + Segment Tree (Fenwick Tree usable also). Make sure to use LCA with time complexity $$$O(\log n)$$$ or lower.

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

    Ok thanks! I knew about ETT but not how to use it for path sum queries. Actually this exact task is explained by SecondThread in his tree basics video (in case someone is interested), i wish I knew it earlier.

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

this blog may help https://codeforces.com/blog/entry/78564

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

https://cp-algorithms.com/graph/tree_painting.html

You can also refer this blog, small modifications in given code will also work.

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

How to solve problem D. I am confused about the statements.

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

    For problem D you can maintain 2 sets(Let's say A & B), A consists of the first N natural numbers(IDS) and B can store the smallest ID that were called out by the banker. Now to process Queries:

    Query1: The Banker calls for the smallest ID that has not yet been called. In this case you can just insert the first element of the set A into B( This is because set store the element in sorted order so the first element will be the smallest ID, to access it you can just use (*A.begin()) and then erase the smallest ID from set A as it has been called out At-most once now.

    Query2: As it says person whose name has already been called out at-most once comes to the banker. This just means the ID which the banker calls out gets erase from the set which stores the IDS that have been called out at-most once (i.e set B).

    Query3: The teller calls out the smallest ID that has been called at-most once but hasn't left. That is just the first element(i. e. smallest) ID of set B.

    Now you can just simulate the process depending on each query and whenever query 3 is called output the answer.

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

It is bad, that this problem is quite implementation heavy and is very common, and I had the solution for almost this problem on one archive.

There are two ways to do it.

$$$A$$$. Let's precompute sum on pathes from $$$v$$$ to $$$root$$$. Then answer for $$$v$$$ and $$$u$$$ is $$$sum[v] + sum[u] - 2 \cdot sum[lca(v, u)]$$$, where $$$lca(v, u)$$$ is the least common ansestor of $$$v$$$ and $$$u$$$, which can be calculated using binary lifting. How to answer queries? Well, the query here means "add $$$x$$$ to $$$sum$$$ of all vertices in subtree of vertice $$$v$$$". How we can add value on subtree quickly? There is a technique, which uses some properties of $$$dfs$$$. Let's simply run dfs and every time we visit a vertice or return to it from child, append it to some global array $$$dfsarr$$$. Look at some vertice $$$v$$$: it appears in array several times, and the segment from $$$leftmost[v]$$$ to $$$rightmost[v]$$$ contains all vertices in subtree of this vertice (just draw it, and you will see). Now, instead of working with original array of numbers on vertices, we use that $$$dfsarr$$$. All remaining is range sum: we can use fenwick tree of segment tree.

$$$B$$$. Way for not smart but strong coders. You can use heavy-light decomposition. It is not easy structure and a bit overkill, but I submitted this, because I already had it prewritten.

→ Reply