Xbalanque's blog

Problem E1 discussion : Game on a Tree (Easy version)
By Xbalanque, history, 35 hours ago, In English

I read yesterday's 2062E1 - The Game (Easy Version) because i like playing games and specially on a tree. I read the problem and tried so hard on coming up with a strategy that i would pick to win. Since it's only rated 2000 in difficulty i thought i might be able to solve it if i give enough time to it.

I want your help in knowing that is the problem solved only using advanced solving/data structural technique or is it just about finding the strategy and implementation is not so hard. I want to know if i can solve it by myself without looking at editorial.

Thanks!

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

»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

PS: Don't downvote just because im a newbie, i genuinely want to solve it,

Here is my thought process so far...
→ Reply
  • »
    »
    34 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice pfp.

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

    I was also trying to understand it . This could be wrong as i have not been able to solve it in contest , maybe someone could verify this?

    These were my observations in the contest :

    1. We cant select the root or the highest weighted node as we insta lose.

    2. If we are able to delete any node with the second most maximum weight and the remaining tree's maximum remains the same we would win as then the next player has to choose the maximum.

    3. If selecting the second last maximum results in a loss we can go for the third maximum , if after removing this node the max of the remaing tree is greater than the third max then we win since we have already proved that choosing the second last max results in an insta defeat and so on.

    So i tried to somehow find and store the max of the remaining tree if that node along with its subtree were deleted but could not implement it .

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

      That's the general idea of the solution and there are many ways to implement it. Also if you know binary lifting, try to think about a solution that uses it since it's one of the most straightforward ones.

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

        I dont know about binary lifting , I will start learning it , you got any nice material for it by chance?

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

          You can find explanations on usaco guide and cp-algorithms. The general idea for the algorithm is a bit like binary search :if you want to find the 22nd ancestor of a node, you find the 16th ancestor, then the 4th, then the 2nd, and then using it you can calculate LCA in O(log n) instead of O(n)

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

    you can do something like

    const int N=3e5;
int tin[N],tout[N],T;
void dfs(int i=1,int d=1){
    tin[i]=T++;
    for(int j:adj[i]){
        if(j==d)continue;
        dfs(j,i);
    }
    tout[i]=T++;
}

    then we can notice something if node $$$i$$$ is son of node $$$d$$$

    thentin[i]>=tin[d] andtout[i]<=tout[d]

    knowing these facts we can sort nodes by their values

    and start from the largest values

    when considering node i

    if there is a node j such tha w[j]>w[i] and j is not son of i then directly i is the answer

    actually first i we find is the answer you can check if some node is not son of i by getting their min_tin , max_tout and checking if one of them does not satisfy the condition upove.

    → Reply
  • »
    »
    25 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    e
    → Reply
  • »
    »
    23 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As I can see everyone shared their thoughts on the implementation. I would like to share my approach as well. I solved it using — Small to Large. The idea is to count the number of nodes greater than the current node in the subtree of the current node. I used PBDS for counting as mentioned here

    → Reply
»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

i used lca

→ Reply