Sorry for my poor English, this blog will be corrected soon.
Solution for this problem — just go through the possible pairs of numbers and check them for correctness. We can do that in any way.
Nuber is divisible by 2,3,5 only if sum of the digits is divisible by 3 and last digit is 0, so if we havent 0 in our set answer is -1, otherwise solution exists(we can return 0 as solution). A further solution — analysis of the cases.
Lets sort all didgits in nonincreasing order. If sum of all digits is divisible by 3 — answer is our set of digits(without spaces ofcourse :) ). If modulo equals 1 — we must delete minimum digit from out set with modulo after division by 3 equals 1, if we haven't such we must delete 2 minimal digits with modulo after division by 3 equals 2. If we have modulo equals 2 — we have identical case.
Also we must remember that we cannot use leading zeros. In case when we have more then one 0 and no another digit we must print only one zero.
Solution — Greedy.
Lets our computers settled on circle, and moves (1->2, 2->3, 3->1) will be steps "forward", and moves (1->3,3->2,2->1) will steps "back".
Note that "back" moves is not optimal, as we can make two moves "forward" that is identical in time. We will look over all starts. Further, we will go by circle while we not complited all game. For every level we will remember number ne[i] — count of another level that "direct" need for it. We will complited levels with ne[i]=0 and update all ne[i] that we must. It can be implemented with O(n^3) time.
Solution — dynamic programming.
Look over for length of the number that we will build. Further, we will use DP f(len,i) — how many numbers with length len we can make with digits i..9.
Recount:
- f(len,0) = sum(f(len-i,1)*C(len-1,i), i=a[0]..len);
- f(len,j) = sum(f(len-i,j+1)*C(len,i), i=a[j]..len), 0<j<9;
- f(len,9) = 1, если len>=a[9], 0 если len<a[9].
C(n,k) — binomial coefficient.
Solution — dynamic programming.
Note, that we can make 2 pathes form cell (1,1) to cell (n,n).
Note, that after each move our cells will be located on the same diagonal.
We will solve the problem with DP f(d,i1,i2), d — diagonal number, i1 — 1st coordinate 1st path, i2 — 1st coordinate 2nd path. It is clear that we can calculate 2nd coordinate when we know number of the diagonal and 1st coordinate. Recount — obvious, we make all 4 transition, and if pathes are intersected in temporary point, we add value of the cell only one, otherwise we add both values of the cells. We can imlement this solution with O(n^2) memory if we will rewrite array of DP after increasing of diagonal number. Also we must remember that answer can be lower then 0.
I present solution as few pictures:
https://get.google.com/albumarchive/pwa/115317317397602031319/Solutions131
Implementation.
We have only one difficult moment — how to count coordinates? We can calculate them from regular pentagon, all that you need, you can read there.
For given two permutation we will make two another by next transformation: New_A[A[i]] = i, where New_A — news permutation, A — given permutation. Lets we get two permutation A and B. Now our problem is next: how many sub-arrays of length n are equals to firs permutation. Two arrays will be equal if after swaping every element with its number in sorted array obtained arrays will be element-wise equal.
Further solution hashes, but we will use not only modulo 2^64, we will use some big modulos, but they must be smaller then 2^32-1.
Lets step[i] = 1000003^i.
Lets F(A) = num[1]*step[1] + num[2]*step[2] + ... + num[n]*step[n], where num[i] — number of the element A[i] in sorted array.
If we will compare arrays, we can use this function. But it can be very big, so we will count it by modulos.
So now our problem is to calculate F function to every subarray. Lets look what will change after adding/deleting some elent from set: some element from num array willnot change, and some will become grater after adding, and become lower after deleting. So we must use some interval-tree to recount our F function. We need to know sum of step[i] on some interval of added numbers and count of elements on some interval. Uses this information we can simply recount out function. Also we must remember that after adding element with coeficinet step[i], where i>n and deleting some previos element our function will become grater that we need. So we will multiple hash of first array by 1000003 to avoid this issue.