belowthebelt's blog

November Easy '16 on HackerEarth
By belowthebelt, history, 7 years ago, In English

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!

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

Comments Comments (10)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

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

    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).

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Errichto Sir till when will the editorials be uploaded ?

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

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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  ) ;
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply