Getting wrong answer

#1

Hello…
I am trying this question from codeforces…
https://codeforces.com/problemset/problem/1285/C
I am solving is from past 2 hour…
The final solution on which i have arrived is this…
https://codeforces.com/contest/1285/submission/97438109
But this is wrong answer…
Please see my code… where i am doing wrong.
Thanks

#2

hello @ashishnnnnn
what approach u r trying to implement?

#3

This is my final code…


Here first i am generating all the different factor of number…
and then i am iterating over the factors and sepating the n into two part one part is some selected factor and other part is number/selected factor.
then checking if lcm of both part is is equal to number … then updating the value of a,b if max(a,b)<max(first_part,second_part)

#4

The issue is in ur distribution.
Distribute factors by generating subset .
Also u don’t have to calculate lcm,becuase we are distributing factors of x only

#5

Means you are saying something like…
first create map … then for each prime factor …increment it’s count and then do the unique factor calculation.

#6

No , factorisation part is correct.

after factorisation , we need to distribute them into two parts right.

to distribute these factor we will use subset generation technique.
number genrated by all those factors that are in a subset we will call it a
and number generated by those factors that are not in subset we will call it b.
and compute its maximum.
for examples if factors are { 2, 3} then how many subsets are there
2^2 -> 4
i.e
{} -> it means no factor in a , all factors in b
{2} -> it means 2 in a , and 3 in b
{3} -> it means 3 in a , and 2 in b
{2,3} -> it meand 2 ,3 in a and nothing in b

we have considered all the possibilities . whichever will give minimum value of maximum we will pick that.

in code form->
image

#7

I got that i am not generating all the subset…
Sorry… if this sound wierd… But is this code is of all subset generation…
This code of subset generation… Beacuse… I am not able to get what we are doing in 2nd loop… first loop i am able to understnad that 2^n types of subsets.

#8

Okay… i will learn it from net…

#9

its a very common technique of subset genration.

suppose this is the set
{ 1 2 3 ... N }
Now you can consider creating all its subset
For each element there is 2 possibilities either keep it or leave it
This way there are 2^N possible cases.
For each of this case you can consider the binary representation of the number
if(j th bit is set include it)
else
 leave it.

That’s how I understood it. Take a small example

   {1 2 3}
   {1 2 3}   1 1 1
   {1 2  }   1 1 0
   {1   3}   1 0 1
   {1    }   1 0 0
   {  2 3}   0 1 1
   {  2  }   0 1 0
   {    3}   0 0 1
   {     }   0 0 0--->empty set

if still it is not clear then pls read this->link

#10

Yaa… I got this… I have read this in the course video… :slight_smile:
Thanks for this… thank you very much :slight_smile: