tomasf's blog

By tomasf, history, 7 years ago, In English

A — Bath Temperature

Problem author: teochaban

Solution

B — Nicoleta's Cleaning

Problem author: tomasf

Solution

C — Leading the Scoreboard

Problem author: tomasf

Solution

D — Joaozao, The Digit Maker

Problem author: danft

Solution

E — Double Fence

Problem author: tomasf

Solution

F — No Link, Cut Tree!

Problem author: teochaban

Solution

G — Hungry Canadian

Problem author: teochaban

Solution

H — Eating Pie

Problem author: bssanches

Solution

I — Matrix Sum

Problem author: bssanches

Solution

J — Beautiful Triangles

Problem author: bimaoe

Solution

K — Counting Good Teams

Problem author: tomasf

Solution
Tutorial of 2017 USP-ICMC
  • Vote: I like it
  • +62
  • Vote: I do not like it

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

Here is another solution idea for solving problem F No Link, Cut Tree!.

My solution idea for this problem is at first make the given tree a full binary tree. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. On the other hand A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. So we can convert a complete binary tree to a full binary tree by adding some dummy node whose cost is 0 so that they don’t contribute anything in the solution as well as they will help us to form our solution. Now classify the nodes according to their level and make their cumulative sum or insert them in segment tree or in a binary indexed tree. We need this data structure for every level. Now map the nodes by the inorder traversal of the tree and position of the level array like 1,2,3….

Now here comes an important observation in a full binary tree at any level, if I want to delete a subtree starting at node u the will need to delete 1 node from level[u], 2 node from level[u]+1, 4 node from level[u]+2…2^i node form level[u]+i.

Now form the data structure (here I have used Binary Indexed Tree(BIT)) just query the contribution of the deleted node subtract them form the total contribution of that level and take the maximum. We need to do this from level[u] to last level and we need to consider the whole level from level 1 to level[u]-1.