algorithm/ideas needed

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

algorithm/ideas needed

Post by abishek » Sun Jun 12, 2005 7:51 pm

http://acmicpc-live-archive.uva.es/nuev ... php?p=2339

I am completely stumped by this problem :(
any body has any ideas how to proceed? may be very advanced math?

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Thu Jun 23, 2005 2:50 pm

i have no theorem to back me up, but here's a guess:

if lh is the hexagon's side length, ah it's area, lt1..ltn the triangle sides and atn their areas, then if u can write lh as a sum of lt1..ltn and ah as a sum of at1..atn then i belive the hexagon can be splited.

at = lt*lt*sqrt(3)/4;
ah = lh*lh*sqrt(3)*3/8; (there are 6 lh/2 side length triangles in a hexagon)

just an idea... (it works for the test cases)

what i'm sure of though is u only have to consider triangle sides that are prime: if u have both 2 and 4, u can use just 2 since a 4 side triangle is 4 2 side triangles

PS: i used backtracking to see if the splits are possible and it takes quite some while
Understanding a problem in a natural way will lead to a natural solution

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Thu Jun 23, 2005 2:54 pm

sorry, ah = lh*lh*sqrt(3)*3/2
Understanding a problem in a natural way will lead to a natural solution

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Fri Jun 24, 2005 4:11 am

it may not be enuf to test primes as 2 and 6 may well produce different results than just 2.

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Fri Jun 24, 2005 10:04 am

actually, a 6 side triangle can be broken into 9 2-side triangles that cover the exact same area.

So, whatever u can cover with a 6 sider, u can also cover with 2 side triangle.

/\ /\
/ \ /\ /\
/____\ / \/ \/\

something like that, with 5,3 and 1 2 side triangles on the rows.
Understanding a problem in a natural way will lead to a natural solution

Post Reply

Return to “Algorithms”