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

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

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
  • Проголосовать: не нравится

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

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

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

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    They aren't sending T-shirts to all countries. Maybe he's referring to that case. In my case I got an 10$ for amazon instead (it was a different contest at hackerrank).

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

Errichto Sir till when will the editorials be uploaded ?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

    Football and Beatles are uploaded. I'm creating an editorial for Fibonacci right now so it should be ready in 30-80 minutes. I will explain easier problems tomorrow.

    EDIT after 46 minutes: Fibonacci is ready and uploaded.

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

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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.
    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← 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  ) ;
      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 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.

        → Ответить