618 - Doing Windows

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am

618 - Doing Windows

Post by razibcse » Wed Aug 28, 2002 8:44 pm

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

A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

618 Any good algorithm beside cases checking?

Post by .. » Sun Jun 20, 2004 7:56 pm

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~
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.

Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET

618 - Doing Windows WA

Post by Sanny » Mon May 30, 2005 9:30 pm

I'm trying to solve this problem by placing the windows in 4! positions. In each position I solve four linear equations like:

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
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 ?


User avatar
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta

Post by fh » Tue Oct 24, 2006 1:58 pm

I used backtracking, my code is only 30 lines.
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:
Felix Halim

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada

Post by sclo » Thu Aug 30, 2007 4:15 pm

There are only 2 main cases.

Post Reply

Return to “Volume 6 (600-699)”