Блог пользователя onlyone

Автор onlyone, 14 лет назад, По-английски
Problem A:
Check whether exist a pair i and j,they satisfy xi+di = xj && xj+dj = xi;

Problem B:
Pay attention to Just Right or Red. use Div and Mod can solve it easily;

Problem C:
As we know, there are only two path -- forward and reverse, so we can do DFS from the one-degree nodes (only two nodes).
As their index may be very larger, so I used map<int,int> to do hash.

void dfs(int i)
{
     int sz = mat[i].size()-1, j;
     UF(j,0,sz)
     if (!vis[mat[i][j]])
     {
        vis[mat[i][j]] = 1;
        printf(" %d",val[mat[i][j]]);
        dfs(mat[i][j]);
     }
}

Problem D:
Floyd.
First, Floyd pretreat the path from I to J, and save the path.
Then get the answer.
The order is a1,a2...ak, K is the number of the leaves, we can assume a0 = ak+1 = 1, the root.
then, answer push_back the path[ai][ai+1].

if the ans.size() > 2*N-1 , cout -1;
else cout the answer.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can you please describe your approach about problem D in more details. I didn't understand your approach.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    first, i use floyd save all the path[i][j], vector<int> path[][];
    path[i][j], from i to j;

    then, just push all the path, from 1 to next leaf, and come back 1.
    • 4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      full solution using lca, better complexity

      • 4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Same complexity without LCA. For each leaf y let leaf_pos[y] be the position of the leaf in the desired visit order. For each node x let dp[x] be min value of any leaf_pos for all leaves rooted in the subtree of x. Then do a dfs visiting nodes in order of increasing value of dp. 92775116

        • 4 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          wow, thats smart, very clean code. i think its important to solve problems, using different approaches. learned something new, thanks

      • 3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        if (sum != 2 * n — 2) { fine = 0; }

        what is the meaning of this line in your code?plz explain

        • 3 года назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          there are n — 1 edges in a tree, in the problem you are asked to find path from root to root such that you go through each edge only two times, thus total walked distance is 2 * (n — 1) = 2 * n — 2.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

About problem D.

Since the route between two nodes in a tree can be split into two parts by their least common ancestor, I think maybe a better solution would using directly walk between two adjacent nodes by passing their lca and connect the edges.

Although, since n is small enough, Floyd is just good for it. :-)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone post the idea for 29E

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's a shortest path problem. The state is u, v, t, which means person 0 is at vertex u, person 1 is at vertex v, and person t must move now. For t = 1, you have to check that the vertex you move to is different from u. You can solve it with BFS.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why should we use map ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Assuming the question is for C, the range of numbers is from 1 to 10^9 which means to store graph you will use an array of size 10^9 which is beyond the memory limit of your hardware.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

fuckoff @onlyone is this editorial or a Treasure hunting letter??.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem C, it's simply finding the diameter of a tree. You can use two DFSs to do so.