hukei5's blog

NOT FAIR!
By hukei5, history, 2 months ago, In English

Why always Alice moves or plays first:)

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

»
2 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

Because her name begin in "A" (the first alphabet)

Also:
→ Reply
»
2 months ago, hide # |
← Rev. 3  
Vote: I like it +44 Vote: I do not like it

Bob is angry that Alice always go first, so he decides to break into her house.

The neighborhood is modeled as N houses (N <= 200k) numbered with integers 1 to N. Houses are connected by N-1 two-way roads, such that each house can reach every other house through some sequence of roads.

Bob lives at house 1, but he does not know where Alice lives. He wants to visit every house, starting at his own house. It takes him 1 minute to travel between two houses connected by a road, and 1 minute to check if Alice is inside a house (he does not need to check his own house).

Please tell Bob how much time it will take him to visit every house.

Input format: N, then N-1 pairs of integers u, v denoting that u, v are connected by a road.

Output format: Output the answer.

Sample:

3

1 2

3 1

Answer: 5. Bob starts at house 1. He can travel to house 2, check house 2, travel to house 1, travel to house 3, and check house 3 in 5 minutes. It can be proven that no faster route exists.

(for the record I thought of this in like 5 minutes I think I have an idea but am not sure if it is fully rigorous)

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    I think this one is well known to be 3n — 3 — maxdepth.

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +11 Vote: I do not like it

      Yeah I think that looks about right.

      Bob now possesses a bomb. Don't ask why he has one. With it, he can destroy exactly one road.

      The IOI venue is located at house K (1 <= K <= N). If Bob can prevent Alice from reaching house K, then he can win the game by forfeit.

      Bob would like to know where he should explode the bomb. You are given Q = N-1 queries. Each of them specifies a road. For each query, if Bob destroys that road, please output (1) whether this prevents Bob from reaching the IOI venue, and (2) the chance that Alice will be cut off from the IOI venue, assuming that Alice lives at a random house that is NOT Bob's house or the IOI venue (as a float, which will be correct if absolute error is less than 0.000 001).

      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        I think we can root the tree at 1, and construct a tree in parent form Then from K, since k does not change throughout queries we can recursively go through parents until the root is reached putting these edges we pass in a set, if and only if these edges are broken answer 1 is yes, else its no.

        for part 2 we will need to use child subtree count dp, lets assume we had yes for answer 1, look at the child node of the broken edge and query the dp[child node of broken edge] — 1, since only one edge is broken, we would divide this by n-2, otherwise we had no for answer 1, meaning ((n-2)-dp[child node of broken edge])/(n-2)

        Of course this is assuming bob is starting from 1 like in the previous problem.

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, hide # ^ |
           
          Vote: I like it +6 Vote: I do not like it

          I think that works. The idea I had in mind was to root at K, and then the number of nodes we block is equal to the size of the subtree. (Can do this with DP or Euler tour), and then checking if 1 is in the subtree can be done with range query or just O(N) walking upward from node 1.

          → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it -7 Vote: I do not like it

    And the harder version of this problem:

    If bob moves optimally, what is the minimum expected time that bob know which house the alice live?

    Sample:

    3
1 2
3 1

    Output:

    2

    Explanation:

    Bob can choose to the house 2 or house 3 (in 1 second) and check if Alice is inside (in 1 second), so the expected time is 2 second because even if Alice is not found at the current house, there are only one house remaining and bob didn't have to check it because he already know 100% where the Alice is.

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      oh no i am not good with expected value problems

      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
         
        Vote: I like it -6 Vote: I do not like it

        Expected value is basically the average of how long bob will know where Alice is over all possible Alice places in $$$(house_2,house_3,...,house_{n-1},house_n)$$$ this problem is solvable with DP :)

        → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Pause. He...broke into her house because she goes first?!

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

Because Ladies First

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

Because Bob wasn't really paying attention when the rules of the game were explained and needed to see a turn being played before asking about half the rules again abd then suddenly playing optimally for the rest of the game.

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This deserves so many more upvotes.

    Opinion
    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Thank you

      Counteropinion
      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        That's completely not my point or how many upvotes you've had previously.

        Explanation
        → Reply
»
2 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Because Alice -from the time being in the wonderlands- learnt to hypnotize people and always hypnotizes Bob to start first. Life isn't fair anyways.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It's sexism against men :(

→ Reply