You are not logged in. Please login at www.codechef.com to post your questions!

×

ICL1804 - Editorial

0
2

Problem Link

Practice

Contest

Author: Divesh and Bhuvnesh Jain

Testers: Bhuvnesh Jain, Praveen Dhinhwa

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

System of Equations, Greatest common divisor.

Problem

You have an initial energy of $P$ units. You are required to reach from $(0, 0)$ to $(n, m)$ in any possible way with the only condition that your final energy should be zero. The energy lost in traveling in all $4$ directions is given the problem.

In case, you are able to reach $(n, m)$ with zero energy, then report the length of the shortest path possible else print $-1$.

Explanation

Since we can move in any possible way we want, let us assume after reaching our destination, $(n, m)$, the numbers of steps taken in north, south, east, west direction are $N, S, E, W$ respectively. Also, the corresponding energy lost while traveling in each of these directions be $a, b, c, d$. Thus we have the following constraints for any valid path:

  1. $N - S = m$, as traveling north increase y-coordinate by 1 while traveling south decreases y-coordinate by 1.

  2. $E - W = n$, as traveling east increase x-coordinate by 1 while traveling west decreases x-coordinate by 1.

  3. $Na + Sb + Ec + Wd = P$, constraint that total energy lost should be equal to the inital energy.

  4. N, S, E, W are integers and $N >= m$, $S >= 0$, $E >= n$, $W >= 0$.

Using the first 2 equations, we can modify the 3rd equation as

$N(a + b) + E(c + d) = P + mb + nd$.

Since, all variables are integers, by Euclid algorithm solution exists only when gcd(a + b, c + d) divides $(P + mb + nd)$. But existence by Euclid algorithm just tells us that solution with integers exists, not that these integers satisfy the additional constraints mentioned in $4$.

To check this, just iterate over the possible values of $N$ and find the corresponding value of $E$ from last equation and of $S, W$ from equation $1$ and $2$. In case, all these integers satisfy the constraints mentioned in $4$, then we can update the answer with the value of the length of path i.e. $(N + S + E + W)$.

For details, refer to the setter's solution below.

Bonus Problem

To solve this problem with harder constraints, i.e. in complexity of $O(\log{P})$, you can refer to ideas in this thread

Time Complexity

$O(P)$, per test case.

Space Complexity

$O(1)$ per test case.

Solution Links

Setter's solution

asked 03 Mar '18, 19:10

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 03 Mar '18, 22:08

admin's gravatar image

0★admin ♦♦
19.8k350498541


@likecs simple explanation and easy solution :p

But didn't get the idea of implementing the solution in O(log p) time complexity . Can someone help ?

link

answered 14 Mar '18, 11:35

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

edited 14 Mar '18, 12:17

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×1,672
×593
×319
×29
×17
×2

question asked: 03 Mar '18, 19:10

question was seen: 374 times

last updated: 14 Mar '18, 12:17