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

November Easy '16 on HackerEarth
Автор belowthebelt, история, 9 лет назад, По-английски

Hello Codeforces community,

November Easy '16 will start in a while (check your time zone). The duration of the contest is 3 hours.

You will be given 6 algorithmic problems of various difficulty. All problems will have partial scoring that is, points for each test case passed. Thus, everybody should find something for themselves. Getting full points on all 6 problems should be fun for everyone. Don't hesitate in scoring partial points in order to score as many points as possible if you want to get to the top.

Problems were prepared by niyaznigmatul. Errichto is the tester and an editorialist for this contest. So you don't have to worry about the quality of the problem set. The problems are interesting.

Importantly, we want to thank lightning, iilnar, FireZi, dusja.ds, and disa who helped in preparation of the contest and making the contest in a good shape. I also want to thank r3gz3n for being around to help in handling the issues with the contest and the system.

There are prizes — t-shirts and Amazon gift cards. And the eternal glory of winning a contest, of course.

Enjoy the contest. Good luck!

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

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

Auto comment: topic has been updated by belowthebelt (previous revision, new revision, compare).

→ Ответить
»
9 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

I can't find Amazon gift cards among the prizes.

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

Errichto Sir till when will the editorials be uploaded ?

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

As there is no editorial for "Trustworthy network" so can someone please explain how to solve it

→ Ответить
  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    The main idea is that the whole path from S to E and back can be splitted into loops, for example:

    • S (edge) X1 (shortest path back) S
    • X1 (edge) X2 (shortest path back) X1
    • etc.

    So the algorithm is:

    1. Compute shortest paths for all ordered pairs of nodes (e.g. using Dijkstra from each node)
    2. Run another Dijkstra algorithm from S and instead of normal cost of moving from some X to Y use the original cost plus cost of shortest path from Y to X.
    3. The answer is the "distance" from S to E returned.
    → Ответить
    • »
      »
      »
      9 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      hellman_ I did something similar

      1) First applied floyd-warshall to find all pair shortest paths in d[n][n] .

      2) then made a new graph with edges equal to d[i][j] + d[j][i]

      3) applied djkstra to find shortest path from s to e

      But i am getting wrong answer. This is the snippet of the main part. Link to the complete code

         for( int i =  0 ; i <  n ; i ++ )
             d[i][i] =  0 ;

    for( int k = 0 ; k < n ; k ++ )
      for( int i = 0 ; i < n ; i ++ )
     	 for( int j = 0 ; j < n ; j ++ )
            {
                       if(  d[i][k] + d[k][j] <  d[i][j] )
                 	      d[i][j] = d[i][k] + d[k][j] ;

            }


     FOR( i , n )
      FOR( j , n )
       {
            if(  d[i][j] < inf && d[j][i] < inf )
            	 {  g[i].pb( mp( j , d[i][j] + d[j][i] ) ) ;
            	    g[j].pb( mp( i , d[i][j] + d[j][i] ) ) ;
                 }


       }


     cout << djkstra ( s , e  ) ;
      → Ответить
      • »
        »
        »
        »
        9 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Why in your new graph you put edges in both directions? They are still directed. Also you need to use (**original edge cost** + shortest path back), NOT shortest paths in both directions.

        → Ответить