A note on CF1809F (EDU145F) Traveling in Berland

Revision en5, by GrandLisboa, 2023-03-24 20:17:28

Submission: Link $O(n)$, 92ms!

Part1: Hint

By looking at the $4$ test cases, we find that answers for $b[i] = 1$ are the same.

Part2: The greedy strategy (for each index $i$)

First, we define some macros for convenience:

The previous index of $x$: #define pr(x) ((x) == 1 ? n : (x) - 1)

The next index of $x$: #define ne(x) ((x) == n ? 1 : (x) + 1)

If $b[x]==1$, rt(x) denotes the place of the next $1$ in the loop: rt(x). For example, let $b$ be an $1$-indexed array $[2, 1, 2, 1]$, then $rt(2)==4$ and $rt(4)==2$. Note that $rt(i)==i$ could happen, for example, $b==[2, 1, 2]$, then $rt(2)==2$. rt could be pre-calculated using a stack.

get(i, j): The gas need to go from $i$ to $j$, both inclusive and $1$-indexed. For example, if $a=[1, 2, 3, 4]$, then $get(1, 2)==1+2==3$ and $get(4, 2)==4+1+2==7$. The $get$ function could be pre-calculated using the prefix sum.

//The Initialpoint
int i = initialpoint;
while(true){
(1) If you are at the destination, which is the same as the initialpoint, break out of this while loop.

(2) When you stay at i where b[i]==2, just pay 2a[i] for a[i] gas that enables you to move from i to ne(i). let i = ne(i);

(3) When you stay at i where b[i]==1, set initialized2 = true and curi = i, and do the following inner while loop:
while(initialized2 || curi != rt(i)){ //rt(i): The next i in this trip with b[i]==1

curi = ne(curi);
}
}
outer loop:


#### History

Revisions

Rev. Lang. By When Δ Comment
en25 GrandLisboa 2023-03-24 21:36:45 71
en24 GrandLisboa 2023-03-24 21:17:21 2 Tiny change: '$get(i, j) liters of' -> '$get(i, j)$liters of' en23 GrandLisboa 2023-03-24 21:16:32 8 en22 GrandLisboa 2023-03-24 21:16:05 6 Tiny change: '$O(n)$, 92ms!\n\n**P' -> '$O(n)\$, 93ms!\n\n**P'
en21 GrandLisboa 2023-03-24 21:11:47 8
en20 GrandLisboa 2023-03-24 21:10:54 0 (published)
en19 GrandLisboa 2023-03-24 21:10:42 31
en18 GrandLisboa 2023-03-24 21:09:50 398
en17 GrandLisboa 2023-03-24 21:06:58 98
en16 GrandLisboa 2023-03-24 21:05:42 158
en15 GrandLisboa 2023-03-24 20:56:25 333
en14 GrandLisboa 2023-03-24 20:53:59 159
en13 GrandLisboa 2023-03-24 20:52:42 442
en12 GrandLisboa 2023-03-24 20:46:55 381
en11 GrandLisboa 2023-03-24 20:43:09 473
en10 GrandLisboa 2023-03-24 20:36:26 518
en9 GrandLisboa 2023-03-24 20:30:55 321
en8 GrandLisboa 2023-03-24 20:27:55 27
en7 GrandLisboa 2023-03-24 20:27:23 369
en6 GrandLisboa 2023-03-24 20:23:25 541
en5 GrandLisboa 2023-03-24 20:17:28 573
en4 GrandLisboa 2023-03-24 20:11:33 120
en3 GrandLisboa 2023-03-24 20:08:49 310
en2 GrandLisboa 2023-03-24 20:05:22 573
en1 GrandLisboa 2023-03-24 19:56:21 194 Initial revision (saved to drafts)