CCC '26 S1 - Baby Hop, Giant Hop - Olympiads Online Judge

CCC '26 S1 - Baby Hop, Giant Hop

Points: 5 (partial)

Time limit: 3.0s

Memory limit: 1G

Authors:

Problem type

Canadian Computing Competition: 2026 Stage 1, Senior #1

Samantha the Frog is hopping between lily pads arranged in a straight line, evenly spaced. There are an infinite number of lily pads. The lily pads are numbered, in order, using integers. For every integer, there is also a lily pad. Samantha starts on a lily pad numbered $A$ ~A~ and would like to hop onto a lily pad numbered $B$ ~B~. She can take a giant hop of length $K$ ~K~, or a baby hop of length $1$ ~1~. Each hop can be either forwards or backwards.

Samantha would like to know the fewest number of hops needed to get from $A$ ~A~ to $B$ ~B~. But sometimes, she would like to know the second fewest number of hops needed.

Input Specification

The first line of input contains a single integer, $A$ ~A~, the starting lily pad ( $-10^{18} \leq A \leq 10^{18}$ ~-10^{18} \leq A \leq 10^{18}~).

The second line of input contains a single integer, $B$ ~B~, the ending lily pad ( $-10^{18} \leq B \leq 10^{18}$ ~-10^{18} \leq B \leq 10^{18}~).

The third line of input contains a single integer, $K$ ~K~, the distance of a giant hop ( $2 \leq K \leq 10^{18}$ ~2 \leq K \leq 10^{18}~).

The fourth line of input contains the integer, $T$ ~T~, which is either $1$ ~1~ or $2$ ~2~, indicating if the fewest (when $T=1$ ~T=1~) or second fewest (when $T=2$ ~T=2~) number of steps should be found.

The following table shows how the 15 available marks are distributed:

Marks Awarded	Bounds on $A,B$ ~A,B~	Bounds on $K$ ~K~	Bounds on $T$ ~T~	Additional Restrictions
5 marks	$0 \le A, B \le 10$ ~0 \le A, B \le 10~	$K=2$ ~K=2~	$T=1$ ~T=1~	Only hops in the positive direction needed
6 marks	$-10^{18} \leq A, B \leq 10^{18}$ ~-10^{18} \leq A, B \leq 10^{18}~	$2 \leq K \leq 10^{18}$ ~2 \leq K \leq 10^{18}~	$T=1$ ~T=1~	None
2 marks	$0 \le A, B \le 100$ ~0 \le A, B \le 100~	$2 \le K\leq 4$ ~2 \le K\leq 4~	$T=1$ ~T=1~ or $T=2$ ~T=2~	None
2 marks	$-10^{18} \leq A, B \leq 10^{18}$ ~-10^{18} \leq A, B \leq 10^{18}~	$2 \leq K \leq 10^{18}$ ~2 \leq K \leq 10^{18}~	$T=1$ ~T=1~ or $T=2$ ~T=2~	None

Note that for full marks, solutions will need to handle 64-bit integers. For example:

in C/C++, the type long long should be used;
in Java, the type long should be used.

Output Specification

On a single line, output:

the fewest number of hops, if $T=1$ ~T=1~
the second fewest number of hops, if $T=2$ ~T=2~

required to move from lily pad $A$ ~A~ to lily pad $B$ ~B~.

Sample Input 1

Output for Sample Input 1

Explanation for Sample Output 1

Samantha hops to lily pads labeled 3, 6, and 9, with three giant hops, and then hops to the lily pad labeled 10 with one baby hop.

Sample Input 2

Sample Output 2

Explanation for Sample Output 2

Samantha hops to lily pads labeled 4, 8, and 12, with three giant hops, and then hops to the lily pad labeled 11 with one (backwards) baby hop.

Sample Input 3

Sample Output 3

Explanation for Sample Output 3

The fewest number of hops needed (4) was found in Sample 2. In this input, the second fewest number of steps is to be found, since $T=2$ ~T=2~. Samantha hops to lily pads labeled 4 and 8 with two giant hops, and then hops to the lily pad labeled 11 with three baby hops.

Sample Input 4

Sample Output 4

Comments

15

Sucram314 commented on March 19, 2026, 3:56 a.m. ← edited →

Dear Kirito,

I am writing to you today to express my heartfelt thanks for creating the last two subtasks of this delightful problem for CCC 2026. After countless hours of hard work and dedication, two years of CCO to my name, and solving every single 3 to 7 pointer on this wonderful website, I felt overqualified to take on whatever was ahead of me this year.

On the fateful day of February 18th, 2026, I was proven wrong.

With four hours of sleep, a developing fever, and at least two missing school assignments, I walked into the proctored exam room ready to push all of my other concerns aside and impart my undivded attention to my laptop for the next three hours.

As soon as the clock struck 1:00, I breezed through the registration survey and opened the problem statement for "Baby Hop, Giant Hop". At first glance, it appeared a little annoying, but nothing too much. I calmly wrote up a solution and submitted it, moving on to S2 while the submission was still grading. S2 seemed simple enough, so I wrote up a solution for it and submitted that as well. It passed without any issues. Only now did I look back at my submission for S1.

Wrong Answer.

Alright, nothing to panic about. Competitive programming is not about solving things on the first try. I can always fix my mistakes. I noticed that I forgot to account for being able to move back and forth to add two additional hops to any given solution, and also that I did not consider taking the unique second minimum. Okay, that has to be all that was wrong, right? I submitted it and moved onto S3.

S3 seemed like a strange question for CCC, and I was at a loss for a good 10 minutes. But after reading more carefully and realizing that Alice and Bob did not have to take all of the cards, the main observation came quickly and I wrote up a solution once again. It passed on my first try without any issues. Only now did I look back at my second submission for S1.

Wrong Answer.

Okay, so it turns out something is still wrong with my code. Perhaps it didn't want the unique second minimum? I made another submission but was met with another fail. I decided I couldn't waste any more time and moved onto S4.

S4 was a more traditional question, and I approached it with the usual methods. Unfortunately, I wasn't able to achieve full points on it, despite pretty much having the solution idea written down in my brainstorming comments. I have come to accept my failure on S4 as a reflection of my indecision and lack of confidence. It was a good question though, perhaps my favourite of this year.

I briefly looked at S5, and it looked interesting, but my heart was being pulled back by my 11/15 on S1. I would go on to spend the next hour periodically swapping between attempting to implement my idea for S4 and thinking of all the possible ways that my code could be wrong for S1. I investigated small values of $K$ ~K~ to look for an edge case, but $K = 2$ ~K = 2~ somehow managed to elude me for the entirety of the contest.

In the end, I finished with a 48/75, my head in my hands, and my world turned upside-down.

Today marks the one month anniversary of this incident, and the day where CCO 2026 invitations were released. I would like to congratulate all the qualifiers, including but not limited to hxian, NK, dxke02, GraceY2, and TheRZ123. Your hard work has paid off greatly and I wish you all the best in CCO 2026.

As for myself, I have done much reflection on my performance in CCC 2026, particularly in respect to this problem.

You got me, Kirito. You really got me good.

This problem has taught me that no amount of preparation can save you from every possible situation, and sometimes life just throws you the (second) shortest end of the stick. I will continue to work on my debugging, speed, and persistence, but I will also move forward with the understanding that I don't need to take every defeat to heart.

Perhaps my indecision for implementing my idea for S4 was a result of the demotivation that S1 built up. If I learn anything from this experience, it is that I must not let a single setback cost my performance in the rest of any challenge I take on in my life. CCC 2026 as a whole might have been a setback in my highschool competitive programming career, but I won't let that stop me from continuing down a path towards my full potential.

If you can't find the shortest path, there's always a second shortest one as well.

Anyway, Kirito, I hope you know that this person:

is me.

I am determined to find you next year at CCO 2027 and give you a hug (with your consent, of course). You have taught me so much more than what I can express in this letter.

Sincerely,
Sucram314

0

do_ur_homwork commented on March 19, 2026, 2:43 p.m.

Orz Sucram314

6

Kirito commented on March 10, 2026, 4:44 p.m.

Problem has been buffed to 5 points by feedback.

1

stephengzy___PYTHON commented on March 8, 2026, 7:16 a.m.

can the second fewest ever be equal to the fewest (because batch 3 case 11 of 82 40 2 2 should be 23, how can it be 22?)

0

do_ur_homwork commented on March 8, 2026, 3:45 p.m.

No. This should be clarified.

5

JamesJiao commented on Feb. 26, 2026, 11:35 p.m.

I've never been so happy to solve a 3p before

34

Ryan_Sharma commented on Feb. 26, 2026, 5:20 a.m.

I hope this problem dies

5

do_ur_homwork commented on Feb. 26, 2026, 8:45 p.m. ← edit 2 →

why 3p???

Edit: i understand now. I hate this problem more than p3 now lol (its not the psetter's fault tho)

Edit: Ty kirito! its 5p now.

1

Kirito commented on Feb. 26, 2026, 10:41 p.m.

One point for each if statement you need in the solution.

2

do_ur_homwork commented on Feb. 27, 2026, 3:31 a.m.

Also, erm actually, you only have 2 if statements in ur code(or did i forget how to count)

3

Olly_Onion99 commented on Feb. 27, 2026, 4:32 a.m.

So many edge cases!

2

do_ur_homwork commented on Feb. 27, 2026, 8:39 p.m.

If there are so many edge cases, you are probably doing it wrong :/

See: https://dmoj.ca/src/7682611 (Kirito's solution)

0

Olly_Onion99 commented on Feb. 28, 2026, 3:54 a.m.

Yeah Im not that good at coding 😔

3

Olly_Onion99 commented on Feb. 27, 2026, 4:45 a.m. ← edited →

also batch 3 case 11 is: 82 40 2 2 and case 19 is 65 45 3 2 (I failed on those)