Editorial of COPC Marathon Contest 1A

Author: Md. Rohan

Problem A2 ( Marathon Course B )

Editorial

This problem asks us to find the distance from the current position (N) to the
nearest water station, as well as the distance of that station from the starting
point. The positions of all water stations are given as distances from the
start.

Key Idea

First, we take all the inputs. Then, we calculate the distance from the current
position to each water station and keep track of the minimum distance.

Note

If multiple stations have the same minimum distance, we choose the one
that is farther from the starting point.
#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

double a,c; // Here a = total length of marathon, c = current point of runner

int b; // b = number of stations
cin>>a>>b>>c;
double arr[b];

for(int i=0;i<b;i++){
cin>>arr[i]; // stores the distance of water stations from starting point

}
double mi=abs(c-arr[0]); // assuming minimum distance as from 1st water station to the
current point
int id=0; // assuming the 1st index as the nearest one

for(int i=1;i<b;i++){
double m=abs(c-arr[i]);
if(mi>m){
id=i;
mi=m;
}
else if(m==mi && arr[i]>arr[id]){
id=i;
}
}
cout<<fixed<<setprecision(6)<<mi<<" "<<fixed<<setprecision(6)<<arr[id]<<endl;

return 0;
}

Explanation

First, we take all the inputs from the problem. We store the distances of the
water stations in an array ‘ arr[b] ’, where ‘ b ’ is the number of water
stations.

We then use a variable ‘ mi ’to store the minimum distance from the runner’s
current position. Initially, we assume that the closest station is the first one,
so we set mi = abs(c - arr[0]). We also used another variable id to store the
index of this station.

Next, we iterate through all the stations using a loop. For each station, we
calculate the distance from the current position, denoted as m = abs(c -
arr[i]).

 If m < mi, we update mi to m and set id = i.

 If m == mi, we choose the station that is farther from the starting

point. Since the array is sorted, this means selecting the station with
the larger value, so we update id if arr[i] > arr[id].

Finally, we print the minimum distance (mi) and the distance of the selected
station from the starting point (arr[id]) with proper precision.
Problem A3 ( The Final Marathon )

Editorial

This problem asks us to find the distance from the current position ((N_x,
N_y)) to the nearest water station, as well as the distance of that station
from the starting point ((0,0)). The positions of all water stations are given as
2D coordinates.

Key Idea

First, we will take all the inputs. Then, we will calculate the Euclidean
distance from the current position to each water station using the formula:

√ 2 2
d= ( x i−N x ) + ( y i−N y )

We will compare these distances and keep track of the minimum distance.

Note

If multiple stations have the same minimum distance, we choose the one
that is farther from the starting point. If there is still a tie, we choose the
station that appears earlier in the input.
int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

double a,c,d;int b;// here a = maximum distance , b = number of water stations , c,d =
current position
cin>>a>>b>>c>>d;
double dis=1e18; // assuming distance as a big number
double org=-1; // assuming origin distance as -1
double ansx=0,ansy=0; // taking (0,0) as the final (x,y)
for(int i=0;i<b;i++){
double x,y;
cin>>x>>y;
double d1=(x-c)*(x-c)+(y-d)*(y-d);
double d2=x*x+y*y;

if(d1<dis){
dis=d1;
org=d2;
ansx=x;
ansy=y;
}
else if(d1==dis){
if(d2>org){
org=d2;
ansx=x;
ansy=y;
}
}
}

double ans_dis=sqrt(dis);
double ans_org=sqrt(org);
cout<<fixed<<setprecision(6)<<ans_dis<<" "<<fixed << setprecision(6)<<ans_org<<endl;

return 0;
}

Explanation

First, we take all the inputs from the problem. Here, a represents the
maximum course distance, b is the number of water stations and ( c , d ) is the
current position of the runner.
We initialize a variable dis with a very large value to store the minimum
distance from the current position. We also take another variable org to store
the distance of the selected station from the starting point / origin.
Additionally, we use ansx and ansy to store the coordinates of the nearest
station.
Next, we run a loop for all the stations. For each station, we take its
coordinates ( x , y ) .
 We calculate d1 = (x - c)2 + (y - d)2 , which represents the squared
distance from the current position.

 We also calculate d2 = x2 + y2, which represents the squared distance

from the starting point / origin ( 0 , 0 ) .

If d1 is smaller than dis, we update dis to d1, org to d2, and store the current
coordinates in ansx and ansy.
If d1 is equal to the current minimum distance, we check which station is
farther from the starting point / origin. If d2 is greater than org, we update
org, ansx, and ansy accordingly.

Finally, we take the square root of both dis and org to get the actual
distances. Then we print the distance from the current position and the
distance from the starting point / origin with up to 6 decimal precision.
Problem D ( Bulls, Bears & Butterflies )

Editorial

This problem asks us to find the maximum profit we can make by buying a
stock on one day and selling it on a later day. We need to do it efficiently in
O(n) time.

Key Idea

First, we will take all the inputs. Then, we will keep track of the minimum
price seen so far and calculate the profit for each day by subtracting this
minimum price from the current price. We will store the maximum profit
among all days.

Note

If no profit is possible, we will print 0, because it is better not to trade.

#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

int n;cin>>n; // n = number of days

vector<int>v; // for storing the price of stocks
for(int i=0;i<n;i++){
int x;cin>>x;
v.push_back(x);
}
int mn=v[0]; // assuming 1st day's price as minimum price
int prf=0; // at very beginning considering profit as 0
for(int i=1;i<n;i++){
prf=max(prf,v[i]-mn);
mn=min(mn,v[i]);
}
cout<<prf<<endl;
return 0;
}

Explanation

First, we take the input n, which represents the number of days. Then, we
store all the stock prices in a vector v.

We initialize a variable mn with the first day's price, which represents the
minimum price seen so far. We also take another variable prf to store the
maximum profit, initially set to 0.
Next, we run a loop from the second day to the last day. For each day:

 We calculate the profit by subtracting the minimum price so far (mn)

from the current price v[i].

 We update prf with the maximum value between the current prf and
this profit.

 Then, we update mn with the minimum value between the current mn

and v[i].

This way, we always keep track of the best day to buy (minimum price) and
the best profit we can get by selling later.

Finally, we print the maximum profit stored in prf. If no profit is possible, it

will remain 0, which is our answer.
Problem E1 ( Fix my Strings )

Editorial

This problem asks us to convert a given string into a simple string, where
no two adjacent characters are the same. We need to do it using the
minimum number of operations.

Key Idea

First, we will take the input string. Then, we will traverse the string and check
every adjacent pair of characters. If two adjacent characters are the same,
we will change one of them to a different character so that it becomes
distinct from its neighbors.

Note

We can choose any valid character from 'a' to 'z' as long as it is different
from the previous and next characters.
#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

string s; // s = initializing the given string

cin>>s;
int n=[Link](); // measuring size of string "s"

for(int i=1;i<n;i++){
if(s[i]==s[i-1]){
char pr=s[i-1];
char nx;

if(i+1<n){
nx=s[i+1];
}
else {
nx='!';
}
for(char c='a';c<='z';c++){
if(c!=pr&&c!=nx){
s[i]=c;
break;
}
}
}
}

cout<<s<<endl;

return 0;
}

Explanation

First, we take the input string s and find its length n.

Then, we run a loop from index 1 to n-1. For each position i, we check if the
current character s[i] is equal to the previous character s[i-1].

If they are equal, it means the string is not simple at this position. So, we
need to change s[i].

 We store the previous character in pr = s[i-1].

 We also check the next character nx. If i+1 is within the range, then nx
= s[i+1], otherwise we take a dummy value.

Now, we try all characters from 'a' to 'z' and pick the first character c such
that:

 c is not equal to pr

 c is not equal to nx

Once we find such a character, we replace s[i] with c.

This ensures that the current character is different from both its adjacent
characters, making the string valid at this position.

Finally, after processing the whole string, we print the modified string. This
will be a valid simple string with the minimum number of changes.
Problem G ( Where does the points reside? )

Editorial

This problem asks us to determine the position of a point p3 ( x 3 , y 3 ) relative to

a line formed by two points p1 ( x1 , y 1 ) and p2 ( x 2 , y 2 ). We need to check whether
the point is on the left side, right side, or on the line (touch).
Key Idea

First, we will take all the inputs. Then, we will use the cross product formula:
val=( x 2−x 1 ) ( y 3− y 1 )−( y 2− y 1 ) ( x3 −x 1)

 If val > 0 → point is on the LEFT

 If val < 0 → point is on the RIGHT

 If val == 0 → point TOUCHES the line

#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

int t;cin>>t; // t = number of testcases

while(t--){
long long x1,y1,x2,y2,x,y; // (x1,y1) = p1 , (x2,y2) = p2 , (x,y) = p3
cin>>x1>>y1>>x2>>y2>>x>>y;
long long ans=(x2-x1)*(y-y1)-(y2-y1)*(x-x1);
if (ans==0) {
cout<<"TOUCH"<<endl;
}
else if (ans>0){
cout<<"LEFT"<<endl;
}
else{
cout<<"RIGHT"<<endl;
}
}

return 0;
}

Explanation
First, we take the input t, which represents the number of test cases.

For each test case, we take six values: ( x 1 , y 1 ), ( x 2 , y 2 ), and ( x , y ) , where ( x , y ) is

the third point.
We calculate a value ans using the formula:
ans=( x 2−x 1 ) ( y− y1 ) −( y 2− y 1 ) ( x−x 1 )

This value helps us determine the direction of the point relative to the line.
 If ans == 0, it means the point lies exactly on the line, so we print
"TOUCH".

 If ans > 0, it means the point is on the left side of the line, so we print
"LEFT".

 If ans < 0, it means the point is on the right side of the line, so we print
"RIGHT".

We repeat this process for all test cases and print the result for each one.
This solution works efficiently in O(T) time, which is optimal for large inputs.
Problem I ( Newbie's Checkout )

Editorial

This problem asks us to calculate the final amount of coins we need to pay
after buying different products. First, we calculate the total cost, then we
apply shipping fee and discount based on given conditions.
Key Idea

First, we will take all the inputs. Then, we will calculate the subtotal using the
formula:
N
subtotal=∑ ( Pi × Qi )
i=1

After that:
 If subtotal is less than S, we will add shipping fee K.

 If total number of items is at least T, we will subtract discount C.

#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

int n; // n = number of product types

long long s,k,t,c; // s = free shipping threshold , k = shipping fee , t = minimum items
for discount , c = coupon discount

cin>>n>>s>>k>>t>>c;
long long sum=0,itm=0; // sum = to store the subtotal , itm = to store total number of
items

for(int i=0;i<n;i++){
long long x,y;cin>>x>>y;
sum+=x*y;
itm+=y;
}

if(sum<s){sum+=k;}
if(itm>=t){sum-=c;}
cout<<sum<<endl;
return 0;
}
Explanation

First, we take the input n, s, k, t, and c.

Here,

 n = number of product types

 s = free shipping threshold

 k = shipping fee

 t = minimum items for discount

 c = coupon discount

We initialize two variables:

 sum to store the subtotal

 itm to store total number of items

Then, we run a loop for all products. For each product:

 We take price x and quantity y

 We update sum += x * y

 We update itm += y

After calculating the subtotal:

 If sum < s, we add shipping fee → sum += k

 If itm >= t, we apply discount → sum -= c

Finally, we print the value of sum, which is the final amount to pay.

We loop through all n products once.

So, the time complexity is O(n).
Problem J ( Some Progression we got !? )

Editorial

This problem asks us to construct an arithmetic progression of N terms such

that every value stays within the range [A, B] and the common difference is
d.

Key Idea

First, we will take all the inputs. Then, we will try to build the sequence
starting from A using the formula of arithmetic progression:
x i= A+ ( i × D )

We need to check whether the last term stays within B.

Note

If the last term of the sequence becomes greater than B, then it is not
possible to construct such a sequence, so we print -1.
#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);
long long a,b,d,n; // a = starting value , b = maximum allowed value , d = common
difference , n = number of terms
cin>>a>>b>>d>>n;
if((a+(n-1)*d)>b){
cout<<-1<<endl;
}
else{
for(long long i=0;i<n;i++){
cout<<a+i*d<<" ";
}
}
return 0;
}

Explanation

First, we take the input values a, b, d, and n.

Here,
 a = starting value
  b = maximum allowed value

 d = common difference

 n = number of terms

To check if a valid sequence is possible, we calculate the last term:

last term=a+ ( n−1 ) ×d
If this value is greater than b, then the sequence will go outside the allowed
range. So, we print -1.
Otherwise, it is possible to construct the sequence. We run a loop from 0 to
n-1, and for each index i, we print:

a+ i× d
This will generate a valid arithmetic progression of n terms.
Finally, we print all the values in one line.

We run a loop of size n to print the sequence.

So, the time complexity is O(n).
Problem K1 ( Similar Ticket Pairs [Easy] )

Editorial

This problem asks us to count how many pairs of ticket numbers have
exactly S matching digits in the same positions.
Each ticket number is treated as a 6-digit number, so we add leading zeros
if needed.

Key Idea

First, we will take all the inputs. Then, we will convert all numbers into 6-digit
strings by adding leading zeros.
After that, we will compare every pair of ticket numbers. For each pair, we
count how many positions have the same digit. If the count is exactly S, we
increase our answer.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

int n,s;cin>>n>>s; // n = ticket numbers , s = number of digit at same position have to

be same
string arr[n]; // storing all the string of numbers'
for(int i=0;i<n;i++){
string st;cin>>st;
while([Link]() < 6) {
st = '0' + st;
}
arr[i]=st;
}

long long count=0;

for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
long long match=0;
for(int k=0;k<6;k++){
if(arr[i][k]==arr[j][k]) match++;
}
if(match==s)count++;
}
}
cout<<count<<endl;
 return 0;
}

Explanation

First, we take the input n and s. Then, we store all ticket numbers as strings.
If any number has less than 6 digits, we add leading zeros to make it 6 digits.

Next, we compare every pair of ticket numbers using two loops. For each
pair, we check all 6 positions and count how many digits match.

If the number of matching positions is exactly s, we increase our answer.

Finally, we print the total count of such pairs.

We check all pairs using two loops and for each pair we compare 6 digits.

So, the time complexity is: O(n 2)

Problem L ( Orbital Shift )

Editorial

This problem asks us to check whether it is possible to choose a phase of a

repeating cycle so that all cargo ships arrive on clear days.

The cycle has length A + B days. In each cycle:

 A consecutive days are clear

 Next B consecutive days are blocked

We are allowed to shift the cycle starting day.

Key Idea

First, we take all arrival days and convert them into positions inside one cycle
using Di % (A + B).Then we sort these positions. After that, we check if all
positions can fit inside a continuous segment of length A.

If yes → print Yes, otherwise → print No.

#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

long long N, A, B; // N = the number of arriving ships , A = the number of consecutive

clear days in one cycle , B = the number of consecutive blocked days in one cycle
cin >> N >> A >> B;

long long L = A + B;

vector<long long> v(N);

for (int i = 0; i < N; i++) {

cin >> v[i]; // vi is the calendar day on which the i-th ship arrives
v[i] %= L;
}

sort([Link](), [Link]());

vector<long long> v2(2 * N);

for (int i = 0; i < N; i++) {
v2[i] = v[i];
v2[i + N] = v[i] + L;
}
 bool check = false;
for (int i = 0; i < N; i++) {
long long min_val = v2[i];
long long max_val = v2[i + N - 1];

if (max_val - min_val <= A - 1) {

check = true;
break;
}
}

if (check) cout << "Yes";

else cout << "No";

return 0;
}

Explanation

First, we take the input N, A, and B.

Then, we compute L = A + B.

Next, we store all arrival days after taking modulo L.

After that, we sort the values.

Then, we duplicate the array by adding L to handle circular checking.

Now, we check every group of N consecutive elements.

For each group:

 We take the minimum and maximum value

 If max_val - min_val <= A - 1, we set check = true

Finally:

 If check == true, we print Yes

 Otherwise, we print No
Problem M ( The Missing Beacon Cell )

Editorial

This problem asks us to find the position of the missing beacon cell inside a
rectangle.

Originally, there was one rectangle filled with #, and all cells outside were ..
After that, exactly one # inside the rectangle became ..

We need to find the row and column of that missing cell.

Key Idea

First, we take the input grid.

Then, we look for the cell which is . but is surrounded by ‘#’ cells in a
pattern that matches the inside of the rectangle.

Since the rectangle is fully filled with ‘#’ except one missing cell, the missing
cell will be inside and connected to # neighbors.

We check each ‘ . ’ cell and verify its nearby cells.

If a ‘ . ’ cell has ‘#’ in its neighboring positions (up, down, left, right
combinations), we identify it as the missing cell.
#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

int a,b;cin>>a>>b; // a = H (number of rows) , b = W (number of columns)

char arr[a][b]; // array of HxW size matrix
int x=-1,y=-1; // at very beginning initializing (x,y) outside of the matrix
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
cin>>arr[i][j];
}
}

for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
if(arr[i][j]=='.'){
int check=0;
if(arr[i][j+1]=='#'&&arr[i+1][j]=='#'){check=1;}
if(arr[i][j-1]=='#'&&arr[i+1][j]=='#'){check=1;}
if(arr[i-1][j]=='#'&&arr[i][j+1]=='#'){check=1;}
if(arr[i][j-1]=='#'&&arr[i-1][j]=='#'){check=1;}
 if(check==1){x=i+1,y=j+1;break;}
}

}
cout<<x<<" "<<y;
return 0;
}

Explanation

First, we take the input H and W.

Then, we store the grid in a 2D array.

Next, we run two nested loops to check every cell.

For each cell:

 If the cell is ‘ . ’

 We check its nearby cells (up, down, left, right combinations)

 If we find surrounding ‘#’ cells in valid directions, we mark this as the

missing cell

Once found, we store its position (row and column) in 1-indexed form.

Finally, we print the row and column of the missing cell.

Problem N ( Aura Farming Coder )

Editorial

This problem asks us to determine whether the strongest coder is uniquely

decided based on given reports.

Each report says one coder is stronger than another. We are given a set of
such relations, and we need to check if there is exactly one coder who can be
the strongest.

Key Idea

First, we count how many coders have no one stronger than them.

These coders are called “possible strongest coders”.

If exactly one coder has zero stronger relations, then that coder must be the
strongest.

If more than one coder has zero stronger relations, then the strongest coder
is not unique.
#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
[Link](nullptr);

int a,b;cin>>a>>b; // a = number of coders (N) , b = number of reliable reports (M)

vector<int>v(a+1,0); // for taking input all the weak coder's frequency

for(int i=0;i<b;i++){
int x,y;
cin>>x>>y;
v[y]++;
}
int count=0;
int str=-1;
for(int i=1;i<=a;i++){
if(v[i]==0){
count++;
str=i;
}

}
if(count==1)cout<<str;
else cout<<-1;
return 0;
}
Explanation

First, we take the input N and M.

Then, we create an array v to store how many times each coder appears as a
weaker coder.

For each report (a, b), we increase v[b] by 1 because A is stronger than B.

Next, we count how many coders have v[i] == 0, meaning no one is

stronger than them.

If only one such coder exists, we store its index.

Finally:

 If the count is exactly 1, we print that coder’s index

 Otherwise, we print -1