I am in real trouble...

Anyone would help me???

I can't solve the 618 problem...so if any kind person sends me the code....i'll b greatful for all my life

## 618 - Doing Windows

**Moderator:** Board moderators

### 618 Any good algorithm beside cases checking?

I solved 618 by using many case analysis, but there are so many cases to consider and my code is 10k long!!

Does anyone have some fantastic algorithm to solve the problem with short code?? Thanks~

Does anyone have some fantastic algorithm to solve the problem with short code?? Thanks~

My signature:

- Please make discussion about the algorithm BRFORE posting source code.

We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.

### 618 - Doing Windows WA

I'm trying to solve this problem by placing the windows in 4! positions. In each position I solve four linear equations like:
If these equations give reasonable values for a,b,c,d ( which are the expantion factors) then it is possible. This algo looks right to me. But I am getting WA. Can anyone help please ?

Regards

Sanny

Code: Select all

```
w[1] * a + w[2] * b = ws
w[3] * c + w[4] *d = ws
h[1] * a + h[4] * d = hs
h[2] * b + h[3] * c = hs
```

Regards

Sanny

I used backtracking, my code is only 30 lines.

Here is roughly the algorithm:

In the main function, just call:

if rec(0, Rs, Cs) then Yes else No

Here is roughly the algorithm:

Code: Select all

```
// Rs, Cs is row and column of the screen
// R[i], C[i] represents window[i] : (R[i],C[i])
int Rs, Cs, R[4], C[4];
// is it possible to fill the screen(r,c)?
bool rec(int used, int r, int c){
if the dimension(r,c) is negative, forget it
if one of the dimension(r,c) is 0,
check the used mask, return true if all are used
for all window i that has not been used yet:
resize window[i] to fit the column c if possible,
then try to fill the rest, return true if success
resize window[i] to fit the row r if possible,
then try to fill the rest, return true if success
if used mask is empty
resize the first window[0] to it's minimum dimension(rr,cc) using gcd
for i = 1 until (rr*i > Rs || cc*i > Cs) :
resize window[0] is resized to window[0] * i
for window j : 1..3 do
place window[j] to the right of window[0] if possible,
then try to fill the rest, return true if success
place window[j] to the bottom of window[0] if possible,
then try to fill the rest, return true if success
return false;
}
```

In the main function, just call:

if rec(0, Rs, Cs) then Yes else No

Visit my script to hunt UVA problem here:

http://felix-halim.net/uva/hunting/

-----------------------

Felix Halim

http://felix-halim.net/uva/hunting/

-----------------------

Felix Halim