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

×

spoj ONEZERO

getting wrong answer on spoj problem link:http://www.spoj.com/problems/ONEZERO/ my solution:https://ideone.com/AAS5v4 i came to know that the problem is due to overflow can any one please tell me the efficient solution thanks in advance:)

asked 17 Mar '15, 00:08

pallesai's gravatar image

4★pallesai
176830
accept rate: 17%


this problem can be solved using bfs using states. So the naive state approach is that we start from 1 and then we have two options either append 0 or 1 to the current number. 1 -> (10,11)->(100,101,110,111)->...... every time when we encounter any number we can check off that module with n gives 0, but this solution will give us overflow or a TLE. so we can optimize it, as we can go from one state to another state by just appending the 0 or 1, now let's say we have already found a string (X) of 0 and 1 whose modulus with n giving me some value p. Now during my traversal to all possible outcome if I encounter another string (Y) which is greater than X and giving the same modulus p. I can ignore it as if both of them giving the same modulus result, as I assume If I append Z both of them going me the same result. In this way, I'm only considering n states, this solves our TLE problem.
eg: n = 15 X: 1010 Y: 1100
X%n = 5 Y%n = 5
so if we encounter initially to 1010, we will ignore 1100 as both of them will finally give the same result. To solve overflow problem, we don't have to store the whole number, we can store parent of every number and store the value i.e 1 or 0 is used to get from parent to current.

Kindly find my ideone solution. https://ideone.com/JDnBN5

link

answered 01 Feb '17, 08:50

aeon_stark's gravatar image

3★aeon_stark
11114
accept rate: 0%

You can also refer the Lalit kundu explanation which are more precised and catchy way! Quora

link

answered 01 Feb '17, 15:21

bansal1232's gravatar image

5★bansal1232
2.8k1418
accept rate: 16%

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:

×18

question asked: 17 Mar '15, 00:08

question was seen: 2,984 times

last updated: 01 Feb '17, 15:21