UVa OJ Board

I got accepted and my outputs are:

sclo wrote:did you handle cases like these properly?

1+1+1-1-1+1-1-1-1+1+1+1-1-1

Which operations could be done last?

If A=S=M=D=1 my program outputs 5. Is it correct?

I tried solving this one with dynamic programming but I keep getting WA. Does anybode have some tricky test cases?

How do you solve this without getting TLE? I tried an O((H-L)*lgK) approach but it did not fit the timelimit.

I don't get it, I do it exactly like you explained. Here is my code: #include <stdio.h> #include <math.h> #include <algorithm> using namespace std; #define MAX_N 105 #define EPS 1e-9 #define FOR(i, a, b) for (i = (a); i < (b); i++) #define MAX(a, b) ((a) > (b) ? (a) : (b)) #define pb push_back #defi...

I would really appreciate some test cases. I can't figure out why I keep getting WA.

I have also used plane sweep , but i get WA. Does the polygon self-intersect? Could someone provide some testcases please?

Can anyone give some hints as to how to obtain O(N*2^N) solution? I had an O(N^2*2^N) solution , that got ACC in about 0.7s after some heavy optimizations, but i doubt that is the official solution.

Just maintain two 2D arrays the one should contain the minimal amount of matrix ( i don't know the plural :) ) and the other the minimal cost of multiplying the last few matrix in a given interval. Rostislav P.S. read the statment carefully i.e. you cannot use the proccesor like this : A*(...)*B......

The same idea also works for more complicated test cases: if you want to evaluate a sequence of matrices ((A1, A2, ..., Ak), (B1, B2, ..., Bm)), check whether it's possible to evaluate it as (A1, A2, ..., Ak, (B1, B2, ..., Bm)). Can you give more details please? I have tried a similar algorithm, wi...

Isn't this just a pigeon-hole principle application?
Is your array is A[1]... A[n] just compute S = A[1] + A[2] + .. + A
if any S % N == 0 then you have a solution (A[1] A[2] .. A), otherwise there will be an S equal to S[j] (i < j) and the solution is A[i+1] A[i+2]...A[j].

As far as I understand : let's say you do this res1 = calc_N_from_PHI_N(J) ; res2 = calc_N_from_PHI_N(num/J); 1) If res1 and res2 have no common divisor than we have no problem. In this case we generate res1*res2 and we put it in the list of our candidates for N ( whose phi(N)==num ) . 2) If they h...

Oh, and by the way, how are people solving this in under 0.1s? I have 0.5s runtime after hashing the results with a STL map. Could someone share some hints? (i see Adrian Kuegel for example has a really fast solution)

Well, it seems you figured it out that tests like 20 and 2000 weren't working because you didn't treat the case when the phi_n = p^k*(p-1) (p prime) and the minimal n could have been p^(k+1) (it's not always p^(k+1) as you realised that for 32 it was 51). So, my test case is like this: N = 33817088 ...

The output for that case is 33817088 , check it out because it is worth it. My algorithm is very similar to yours (actually i started solving this task after reading your posts) and i finally got accepted after fixing my program to work for this case (although it was pure luck, i don't know how to p...