AtCoder Beginner Contest 167 Problem D approach

help
, ,
1

Problem link: D - Teleporter

2

Simulate the teleportation until you find repetition. Then go and find the first occurrence of the repeated value. The answer will be to travel to the first occurrence and then going in a loop from the first occurrence to last occurrence, for which the answer can be calculated using modulo.

1 Like
3

You just need to iterate till you find the cycle. Since its easier to understand with an example I’ll do that.

Say you have a array that that causes a teleporting sequence like 1->2->5->3->6->4->5->3->6->4->5…
Notice that the cycle is (5,3,6,4) .

So the algorithm goes like this:

  1. Find the cycle and store it in an array a.
  2. Subtract number of elements before the start of the cycle from k. In the above example the elements before start of cycle are 1 and 2 so k-=2.
  3. Our final answer will be a[k%a.size()] since these 4 numbers will be repeated continuously and we only care about the remainder.

My code : Submission #13055489 - AtCoder Beginner Contest 167

1 Like
4

Try finding the path You can reach from 1 And You will observe You will either end up visiting every Node Once In all of your K moves , or you will also observe while doing these K teleportations You will be in a loop(cycle) ( will be revisiting some node once again before ending up with your K moves so Try finding the loop and Independent path By finding this loop You will easily observe a simiple Modulo operation will suffice to come to an ans in cases of loop(cycle) !! Happy Coding Dude

1 Like
5

Thanks buddy

1 Like
6

Hints and solutions for AtCoder Beginner Contests 167 [A-D problems]: https://sahilbansal17.github.io/Competitive_Coding/2020/05/10/atcoder-167.html

2 Likes