alpenglow's blog

Ad-hoc problem — Triangular grid
By alpenglow, history, 2 weeks ago, In English

How to solve 10022 — Delta-wave from UVa?

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

Comments Comments (6)
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A good practice would be to mention your progress so far and where exactly you're stuck. It makes it easier for others to help you.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not stuck at any valid approach. All the approaches I tried were wrong eventually.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

up

→ Reply
»
13 days ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Code

First of all, find row and column coordinates.

row = ceil(sqrt(num))
col = num - (row - 1) * (row - 1)

Then, look at the photo and consider these intersections, there are at most 3 unique (yellow) intersections, you should find those and go through it, meaning from the starting point go to that intersection and then go to the end. Take the minimum out of these three (or two or one) paths. When three unique intersection exists then the answer is just travelling between the levels. Otherwise you should go south-west and then east or south-east and then west if the are not in the same level, if they are, then the answer is the difference between column coordinates.

→ Reply