You are not logged in. Please login at www.codechef.com to post your questions!

×

Solution for solving the Practice Contest

What is solution idea for the Solving the Practise Contest ? Is it related to finding recurrence and solving in O(log n) using exponentation or can it be solved using combinatorics ?

asked 02 Nov '14, 13:03

kshitij_jain's gravatar image

3★kshitij_jain
663
accept rate: 0%

edited 01 Dec '14, 19:59

admin's gravatar image

0★admin ♦♦
19.8k350498541


Yes, the problem can be solved by finding a recurrence relation and then using matrix exponentiation. The DP state is:

DP[i][x][y][z] represents the number of ways of distributing i problems such that

  1. x is the number of problems done by first mod k. (0 <= x < k)
  2. y=0 means second has not done the current problem and y=1 means the current problem is given to second. (0 <= y < 2)
  3. z=0 means third has done 0 problems till now and z=1 means that third has done at least one problems till now. (0 <= z < 2)

We made a matrix of 40x40 (10 * 2 * 2) for the matrix exponentiation.

link

answered 02 Nov '14, 20:12

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,112
×33

question asked: 02 Nov '14, 13:03

question was seen: 1,173 times

last updated: 01 Dec '14, 19:59