OJ Board

Now it is back to normal.

Hello,

I have solved 961 problems as of yesterday. However, when I logged in today, I found out that my number of problems solved became 2 and number of total submissions became 2. What happened to my account??!

PS My user number is 8764.

Thank for the hint. Managed to solved it after so long.

A hint from me is that the order you search matters too. I just changed the order and my code which probably takes hours to run manage to solve the largest test case in a short time.

There's an O(n) solution. Almost similar in idea to 11237

Think nim/nim sum.

You are using the wrong method. It does not give you the smallest lexicographical palindrome.

Inserting into a map takes O(lg n) and hence you got TLE.

Using O(n^2) algorithm to generate all the edges result in my code taking 0.7+s. I think using kd-tree will result in faster runtime.

I'm encountering the same problem too...

use %lld

There is no need to compute factorials. Just find the kth smallest number that is not used (k starts from 0...so-on).

People have suggested using interval/segment trees to solve this problem. I've used fenwick trees to solve it. It is possible to find the kth smallest number using binary search.

I finally realised that there is a linear solution to the problem - solving longest path on a DAG.

You are moving towards the right direction.

If you really want a hint take a look at Steven Halim's website (a solution by Minh Duc): http://www.comp.nus.edu.sg/~stevenha/pr ... al_Polygon

Well let me drop one hint.

In this problem we have to find the suffix of the string that is the longest palindrome. This problem can be solved using a slightly modified KMP with the search string the reverse of the original string.

Therefore, this problem can be solved in linear time.

You didn't comment out your freopen. I think your code might TLE.

phi(N!) = number of numbers between 1 and N! which has no common factors with (1...N) ie number of numbers between 1 and N! with prime factors > N.