z-95 round #4

When competition will be judge ?...

In the next 24 hrs.

tanks..=)...

The results are up.

It took me some time to check if the tests for the 3rd problems were okay. And they ARE okay. Even though everyone got 0 :(

hm, very strange. Is it possible to see one test and right answer for it?

Can somebody give some test cases that don't work for those who got 20 points on z-rectangle?

if you have a rectangle 6X5. tell me what is your optimal answer. So, i can give you the right one.

Ok, thanks, I just found the problem :D

can someone tell me whats the problem with my code, I can't see the mistake

#include <stdio.h>

int x,y,br=0;

int main()
{
  scanf("%d %d",&x,&y);
  while(x>0 && y>0)
  {
     if(x>y)x-=y;
     else if(x<y)y-=x;
     else
    {
        br++;
        break;
     }
     br++;
  }
  printf("%d",br);
  getchar();
  getchar();
  return 0;
}

as soon as possible

because you solution is wrong
for example 5 6
your answer - 6
right answer - 5

_ _ _ _ _
| | |
|_ _| |
| |_ _ _|
|_ _| |
| | |
|_ _|_ _ _|

lol, is it clear :D ?

May anyone who got 100 in rectangles tell me how can i optimize to to get 100 ?
i am getting 70 coz of 3 TLE.

that is my dp function:

int solve(int r,int c)
{
    if(r==c)return best[r][c]=1;
    int ret=1<<30,i;
    if(best[r][c]!=-1)return best[r][c];
    for(i=1;i<=r/2;i++)
        ret=min(ret,solve(i,c)+solve(r-i,c));
    for(i=1;i<=c/2;i++)
        ret=min(ret,solve(r,i)+solve(r,c-i));
    return best[r][c]=ret;
}

try change your recursion dp to tabular dp

does it differ in time ?

Oh, it really differs, Thank you :)

complexity of two solutions are equal, but in recursion you need to call function which more slowly then simple access to array

ah, i see. :)

@Ravent
@AhmedKamel

Thanks

You are welcome :)

In spaghetti:

If the line segment (spaghetti) is on the cutting line(collinear). how will it be cut ?

There is no such a case. But if there was, you would cut it in half

Oh, i see. Thanks alot.

Damn, the tests WERE ALL okay, but the grader program was NOT.

I've fixed it and the competition is being regraded. Sorry for that guys, it took me a while to find the bug :)

Grader for that task in training section is OK now?

yes, it is okay now

Are you sure grader is working properly for z-spaghetti in training section? I'm getting a 0/10 for it...