OJ Board

Now, the leaderboard is up! Join us.

ACM SIGMOD 2013 PROGRAMMING CONTEST
http://sigmod.kaust.edu.sa

Student teams from degree granting institutions (both undergraduate and graduate) are invited to compete in the annual SIGMOD programming contest. The winning team will be awarded a prize of USD $5,000. Teams with the top-performing ...

I would like to know the speed difference between running a solution on the old a new systems.
In the past, I liked to make a code that runs in less than 2 seconds (as this was the real time limit intended by the most of the problem authors). In the new system, what should be equivalent to 2 seconds ...

I cannot submit it, because I use an array:
char D[50][101][3000];
But how can I avoid it, and get the path (the actual string number) at end?

I wonder, where are the problems of the last 'hard' contest? And where is the forums related to it? I like to try submitting the problem 'Bigger is Better'.
I have made a very fast code. I made a dynamic programming approach using C++ code, that is very fast on my machine. (but got TLE)
I will be ...

These two questions are not related:
1) I would like to know how to make it using integers.
2) I will make a lot benefit from sweeping if there is a math formula to get number of grid squares inside a trapezoid with two edges parallel to x-axis.

See page 7 of the following:
http://ai.stanford.edu/~serafim/CS262_2 ... ture16.ppt

Thank you very much Mr. sclo for your time and effort.
I will try to think in it again using your valuable clues.

I am tired of thinking.
Can you give me an example of how to put an equation in this system?
Or please, direct me to a similar problem having discussions on it.
Thank you

I am not good at designing test cases, but this may help:
If you did not make these:
1) Ignore horizontal edges.
2) At each y, Compute edge intersection with the line Y=y, Y=y+1. Let the x cords xl, xr (where xl min of them, xr max). Edges are sorted by xl, and in tie by xr. xl, xr are double ...

Can you help me further?
I used something like these (in most computations) and got AC:
hm2 [j]=((hm2[i-1][j]+MOD-(hm1[i-x][j]*po[x-1])%MOD)*AS+hm1 [j])%MOD;
where MOD = 65521
How can I convert it using this trick of unsigned int? I have tried removing %MOD, and +MOD, and making all numbers in ...

Also, I have used a small number (MOD=65529), so as to ensure that no overflow (using int) will occur (its square should fit in int). Is there a way to overcome this? I do not like to switch to long long computations as they are slow.

I need a hint to solve this problem.

For Mr. tobby, if you have time, please describe the greedy approach.

Thank you very much Mr. Emilio. I followed your advice and got AC.

For Mr. Misof:
I do not know how to use the trick of using unsigned int, and not using %. For example, consider this line:
hm2 [j]=((hm2[i-1][j]+MOD-(hm1[i-x][j]*po[x-1])%MOD)*AS+hm1 [j])%MOD;
How can I convert it using this trick ...