mahmoud_arafa's blog

SPOJ — FP "Finding password"
By mahmoud_arafa, 10 years ago, In English

Hi,

I got WA for this problem. I hope that you can help me.

Problem Link: http://www.spoj.com/problems/FP/

My idea is sorting the numbers in non-increasing order, then applying (0/1) logic, either I take the element, or I leave it.

My code: http://ideone.com/wJaQoR

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are trying to generate a number then try to check what ever its divisible by 9 or not . limit of number 10^6 and there can be k == 100 . adding two number by (solve(i + 1, curK + 1, val * 10 + arr[i] is totally wrong . think about it if we have two numbers 200 and 88 then by this ( 200 * 10 + 88 ) i am generating 2088 but it is exactly 20088 right ? . As limit is too high to concat all numbers here its not wise to do so also. if you think a little bit i don't even need to know the number also , we just need to know sum of all of its digit is divisible by 9 or not ( a number is divisible by 9 if sum of its digit also divisible by 9 here is the link ) it can easily done by per number check . you just need to know the sequence ( as T <= 30 a global array should work ) which are taken after descending order sorting .

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Hi,

    Thank you for correcting my understanding for the problem.

    If I took K numbers, how can I maximize the answer? I mean k can be equal 100, and each number can be equal 10^6. This is too big. Using "sum % 9 == 0" is not enough, you need the number itself to be returned I think. Can you provide a pseudocode to the approach?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      thats why you should keep track the numbers which you are currently using by a global array . something like that 


      string ans = "" ;  // it will store the final result 
bool vis[105] ; // it will keep track which numbers are i am using right now
int mod[105] ; // where i am store all numbers mod % 9 
void DP(int rem,int pos , int taken)
{      if( pos >= n ) return ;
       if( taken == k )
        {
              if( !rem ) // we need to check what is generating now 

              {
                     string tmp = "" ;
                     for i ->0 to n-1 
                     if( vis[i] ) // i am using this number 
                     tmp += num[i] ; 

                    if( tmp.size() > ans.size() || ( tmp.size() == ans.size() && tmp > ans) 

                     ans = tmp ;
              }
            }
             vis[pos] = 1 ; // currently taken this number 

          DP( (rem + mod[pos] ) % 9 , pos + 1 , taken + 1) ;

          vis[pos] = 0 ; // not taken 

          DP ( rem , pos + 1 , taken ) ;

         return ;
         }

        

}

      code will look something like that , i think you should get it now how to code . good luck :)

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

        Here is my new one, still WA.

        http://ideone.com/77o0JH

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          sorry my friend i don't know the solution but i can tell you why this process isn't working . look if we have this case 

          3 3

544

5
54

          after sorting ( 544 , 54 , 5 ) and takeing all numbers we are generating 544545 but we can do better of that by taking 5 , 54 thrn 544 which means 554544 . that is greater then 544545 . idea of sorting isn't quite right here taking always big number first . As we can what ever we take , we are taking k numbers right ? so what ever the taking the biggest number 1st or last exactly doesn't matter . i haven't solve this problem , if you solve it or anyone please let me know .

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

marat.snowbear, can you help me with a tutorial for this problem please?

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

Can someone give hints to solve this problem?

→ Reply