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

×

PAYU Hiring Challenge 2nd Question

It is 2nd Question from Yesterday's PayU Hiring Challenge on Hackerearth

PROBLEM

Given an array with size n and maximum value l compute

$(\sum_{i=0}^{l} t_i * 31^l)$ % mod

where mod=10e9+7

$t_i$=size of maximum subset whose xor is i

If there is no subset whose xor is i then $t_i$=0

Constraints

$n<=10^4$

$a[i]<=10^3$

Sample Example

4

1 2 3 4

Output

3755653

Explanation

l=4

For i=0 $31^0 * 3$ Subset is (1,2,3)

For i=1 $31^1 * 2$ Subset is (2,3)

For i=2 $31^2 * 2$ Subset is (1,3)

For i=3 $31^3 * 2$ Subset is (1,2)

For i=4 $31^4 * 4$ Subset is (1,2,3,4)


I used DP to solve this problem but got WA

Here is link to my Solution

It would be grateful if someone can point out my mistake :-)

asked 07 Aug '17, 12:20

anushi's gravatar image

4★anushi
24617
accept rate: 15%

edited 07 Aug '17, 12:23

Do you remember problem name?? I can look up in my submissions and check.. I solved that question successfully and remember that there was some edge condition in dp.. I can help easily then.. :)

(07 Aug '17, 13:42) kauts_kanu5★

for i in range(1,n):
    for j in range(0,1001):
        dp[i][j]=dp[i-1][j]
    for j in range(0,1001):    
        dp[i][a[i]^j]=max(dp[i-1][j]+1,dp[i-1][a[i]^j])

why range here is 1001 and not 1024 because xor can vary till 1024. Although a[i] <=1000 but a[i]^j can be above 1000 till 1024.. no?? and this will affect when you are calculating max using dp.. because you have not updated cells of j>1000..

link

answered 07 Aug '17, 13:56

kauts_kanu's gravatar image

5★kauts_kanu
1.1k110
accept rate: 19%

edited 07 Aug '17, 13:58

Thanks a lot :-)

(07 Aug '17, 20:33) anushi4★
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:

×2,212
×858
×398
×5

question asked: 07 Aug '17, 12:20

question was seen: 492 times

last updated: 07 Aug '17, 20:33