Troll As it seems someone got my cf account and trolled me :D

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 166 |

4 | antontrygubO_o | 166 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 156 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

Troll As it seems someone got my cf account and trolled me :D

example input:

8 (N)

13 51 35 43

output:

5 (13,51),(51,35),(35,43),(51,35),(35,43)

The problem can be solved easily with a complexity of (2^10)*(2^10)(there are at most 10 different digits in a number). We have an array of size 2^10. We find the digits that a number contains for every number. Then we put the numbers, who contain the same set of digits in the same bucket. If a number contains digit 0 it is put in the bucket whose least significant bit is set, for digit 1, the buckets second least significant bit should be etc. After this, you can loop over the buckets like this:

for(int i=0;i<1<<N;i++)

for(int j=0;j<1<<N;j++)

if(i&j) //we should actually add a special case when i equals to j but anyway.

ans+=bucket[i]*bucket[j];

But my question is that could we do this in a better complexity?

I got an idea but I cant compute the bucket version it uses faster than 2^20. Here it is: If we could convert the array we computed above into this:

If a number contains digit 1, it should be put in every bucket whose bit for digit 1 is set. The same thing also applies to the other digits. Then we could compute the number of pairs with the inclusion&exclusion principle. We would just have a 2^N loop and if it has an odd number of set bits, we add it to the answer, if it doesnt, we subtract it from the answer. Actually I got an idea to compute the new array but it doesnt quite work. Some numbers get counted more than once. To fix it I have to use inclusion exclusion principle again. But then the complexity increases to 2^20 again. The wrong version follows:

for(int i=(1<<N)-1;i;i--)

for(int j=i;j;j&=j-1)

bucket[(j&-j)^i]+=bucket[i];

Could you please find a better way to solve this problem?

Thanks in advance.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 20:46:54 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|