PROBLEM LINK: Fair Load
Explanation
Author: kaneki99
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math
PROBLEM:
Survey Corps are now going outside the Wall for exploration under the commander Hange Zoë. Survey corps use horses for exploration purposes as horses can weigh food for them and they are mobile. So initially all n horses were weighing some w1,w2,w3,…wn weight of grain’s sack before the commander arrived at the camp. We need to find the final weight on each horse which would be the average total weight on all the horses
EXPLANATION:
We just need to add total weight and divide it by the number of horses
Setter Solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define all(a) a.begin(),a.end()
#define x first
#define y second
#define MOD 1000000007
typedef vector vi;
typedef vector vvi;
typedef pair ii;
typedef vector vii;
typedef long long ll;
typedef vector vll;
typedef vector vvll;
typedef double ld;
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while(tc--){
ll n,s = 0;
cin >> n;
for(int i = 0;i> t;
s +=t;
}
cout << s/n << "\n";
}
return 0;
}
PROBLEM LINK: Impressing Mikasa
Explanation
Author: aseet_dhale
DIFFICULTY:
EASY
PREREQUISITES:
Sorting
PROBLEM:
You will be given n strings of any length. You will have to put all the strings together such that you will get the largest number formed from the strings after joining them.
EXPLANATION:
The solution for this problem Is quite simple. We have to sort all the given pieces in such a way that they form the largest number. The tricky part is to write the custom comparator for that. The basic idea for that is that if we join two string a and b then we need to compare concatenation of a and b and concatenation of b and a, i.e, (a+b) and (b+a), and then check which one is greater
Setter Solution
#include <bits/stdc++.h>
using std::string;
using std::vector;
bool custom(string a, string b) {
int x = stoi(a + b);
int y = stoi(b + a);
if (x > y) return true;
return false;
}
string largest_number(vector a) {
// write your code here
sort(a.begin(), a.end(), custom);
std::stringstream ret;
for (size_t i = 0; i < a.size(); i++) {
ret <> result;
return result;
}
int main() {
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
vector a(n);
for (size_t i = 0; i < a.size(); i++) {
std::cin >> a[i];
}
std::cout << largest_number(a) << "\n";
}
}
PROBLEM LINK: Colossal Titan
Explanation
Author: ponder
DIFFICULTY:
EASY
PREREQUISITES:
Sliding Window
PROBLEM:
Soldiers are entering in the gate as queue some soldiers have died due to attack so there are some empty places in the queue each soldier has the power of 1 except the soldiers which are at the first place and last place in the queue, Colossal titan has a foot of size R we need to maximize damage on soldiers by stomping with foot single time
EXPLANATION:
From the question, it was pretty clear that we need to find the maximum sum of contiguous segments with length F.
It was given that Levi and Mikasa have more worth than other horseman so let’s create a new array with their power as values.
Now just find the maximum sum of a subsegment of the array with length F. To achieve the result without TLE go for the sliding window approach.
Setter Solution
def I(): return int(input())
def M(): return map(int, input().split())
def ARR(): return list(map(int, input().split()))
def main():
l, m, f = M()
s = input()
arr = [int(c) for c in s]
n = len(arr)
arr[0], arr[n-1] = l, m
if f >= n:
print(sum(arr))
else:
initSum = sum(arr[:f])
mxSum = initSum
for i in range(f, n):
initSum -= arr[i-f]
initSum += arr[i]
mxSum = max(mxSum, initSum)
print(mxSum)
tc = 1
tc = I()
for _ in range(tc):
main()
PROBLEM LINK: DESTROY ALL
Explanation
Author: raviwarlord
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Knapsack DP
PROBLEM:
Eren’s titan has a damage index D which means if he takes damage strictly greater than D
he will be killed and humanity will lose a great soldier. Each enemy titan has a happy index X
damage index Y, which means for every titan Eren kills his happiness will rise by X, and his titan will take damage by Y.Find Maximum happiness Eren can achieve by killing the titans such that the damage taken by them is not strictly greater than D
EXPLANATION:
This is a classic Dynamic Programming problem called 0/1 knapsack. Here for Eren to have maximum happiness is the same as putting maximum valued objects in a knapsack with each item having a value(happiness index of titan) and weight(the damage it gives to Eren) and the capacity of the knapsack will be the damage index of Eren.
Let’s call the max_damage - damage taken by Eren its health, we can calculate the maximum happiness in O(N * D) by calculating for every titan what will be maximum happiness if Eren kills him at all of his favorable health, it means he must not die after killing the titan.
Let’s consider a vector dp with length D + 1, now for very titan, and for every health index of Eren, we can either kill the titan or not and we will store Eren’s maximum happiness in the dp vector. So for every titan and Every value of Eren’s health, Eren can either kill this titan by raising its happiness by x or he can skip it with keeping his happiness the same:
dp[damage_taken] = max(dp[damge_taken], dp[damage_taken + x] + y)
NOTE - Be sure to process only the health where damage_taken + x <= d
Setter Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 0, d = 0;
cin >> n >> d;
vector dp(d + 1, 0);
long long a = 0, b = 0;
for (int i = 0; i < n; i++) {
cin >> a >> b;
for (int damage_taken = 0; damage_taken + a <= d; damage_taken++) {
dp[damage_taken] = max(dp[damage_taken], dp[damage_taken + a] + b);
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
PROBLEM LINK: Special Bond
Explanation
Author: padma00
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Math, Number Theory, Euler Totient Function
PROBLEM:
This Scout Regiment has it’s a specialty that each soldier has a unique number like 1,2,3,4,5…. where these numbers are in increasing order of their rank.If a soldier has a higher rank that means he is senior for all those with rank lower than him.
recruiter, he will choose only those soldiers who have that special bond with him, so to check that bond he is having one equation if this holds true then and then only he will recruit these soldiers also he will choose juniors only as he wants to be the Head of the New team with the highest rank.
Suppose the recruiter’s rank is N and the soldier he is choosing has rank i
then the Equation by which he is checking that special bond is
X=(i∗N)
where integer X is the least common multiple of i and N.
EXPLANATION:
In this problem basically, we are supposed to find the numbers of integers less than ‘n’, the rank of the recruiter, and which are co-prime with ‘n’.
To get this we can directly apply Euler’s Totient Function or by using phi function that is
phi(n) = n x (1-1/p1) x (1-1/p2) x (1-1/p3) x…(1-1/pn)
Where gives the number of integers which are less than n and coprime with n where phi(n) are prime factors of n. Here we have to find up to phi function let’s just calculate all phi functions up to and store10^6 then as our question demands that answer should be containing that recruiter so always phi function value + 1 is the answer but when n is one then phi function has value 1 but our ans must be also 1 as a recruiter is only one in the team
Setter Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n = 1000001;
vector phi(n);
// fill everyone with n itself
for (ll i = 0; i <= n; i++) {
phi[i] = i;
}
// apply n(1-1/p1)(1-1/p2)......
for (ll i = 2; i <= n; i++) {
if (phi[i] == i) {
for (ll j = i; j <= n; j += i) {
phi[j] -= (phi[j] / i);
}
}
}
ll tc;
cin >> tc;
while (tc--) {
ll n;
cin >> n;
if (n == 1)
cout << "1"
<< "\n";
else
cout << phi[n] + 1 << "\n";
}
return 0;
}
PROBLEM LINK: Attack On Titan
Explanation
Author: kaneki99
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Math, Number Theory, Modular Arithmatic
PROBLEM:
We need to find
\prod_{1 <= i < j <= n} |b_{i} - b_{j}|
EXPLANATION:
We can see that if n>m then the answer would always be 0 as there would be at least one pair that lies in the same equivalence class thus for at least one pair |(bi - bj)| mod m = 0, thus if n <= m we just need to brute force the answer as constraints for m are very small .i.e m <= 2000
Setter Solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define all(a) a.begin(), a.end()
#define x first
#define y second
#define MOD 1000000007
typedef vector vi;
typedef vector vvi;
typedef pair ii;
typedef vector vii;
typedef long long ll;
typedef vector vll;
typedef vector vvll;
typedef double ld;
int main() {
// your code goes here
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m;
cin >> n >> m;
vll a(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n > m)
cout << 0 << "\n";
else {
ll s = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
s *= abs(a[i] - a[j]);
s %= m;
}
}
cout << s << "\n";
}
return 0;
}