All Tracks Algorithms Dynamic Programming Problem

Competition
Tag(s):

Dynamic Programming, Medium, Probability

Problem
Editorial
Analytics

Hasan is organizing a chess competition, there 2N participants, they are standing in a row and numbered from 1 to 2N from left to right.

There are N rounds, in the each round player number 1 in current row play against player number 2 in current row and player number 3 in current row play against player number 4 in current row and so on, the winner of each game advances to the next round, so the number of participants in round i (1-based) is 2N-i+1. all winners stand in a row in the next round in the same relative order as the current round.

the winner of last round is declared to be the winner of the competition.

Hasan has estimated the skills of the participants and now he know that if players i and j played against each other, then the probability that participant i win the game is Ai,j / 1000, of course Aj,i = 1000 - Ai,j, (for all i,j (i!=j) between 1 and 2N), the result of any game will never be draw.

Now Hasan wants to know the chances of each participant to be the winner, Help Hasan to compute the probability that participant i will be the winner for each i between 1 and 2N.

Let Pi be probability that i-th participant win, then find Pi * 10002N mod 109+7 for all i between 1 and 2N , it can be proven that Pi * 10002N is always integer.

Input:

First line contains integer N the next 2N lines each contains 2N integer numbers, the matrix A

Output:

print 2N space-separated integers in a single line, the i-th integer is Pi * 10002N mod 109+7

Constraints:

  • 1 <= N <= 10
  • 0 <= Ai,j <= 1000
  • Ai,i = 0
SAMPLE INPUT
2
0 422 756 855
578 0 396 161
244 604 0 844
145 839 156 0
SAMPLE OUTPUT
549365725 698518551 555517333 196591405
Explanation

.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

International Women's Hackathon

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications