Note from Author:
Congrats to all the Winners. Glad to see so much participation. Hope to see you all participate in the next biweekly as well. You can contact me (Abhijit Mishra) for any queries related to the contest or problem discussion.
I would recommend first looking at the hints for the problem if your facing logical issue, if you are absolutely clear with logic then move on to look at the solution and the code. efforts will be made towards making code for other languages (Java and Python) available as well.
A — Try-logy
Think of the cases in which the team will solve a problem.
Repeat for the n problems.
A problem will be solved by the team if there are atleast two 1s in a row. count this for every row i.e n times.
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll n;
cin >> n;
ll a, b, c;
ll ans = 0;
for (int i = 0; i < n; i++)
{
cin >> a >> b >> c;
if (a + b + c >= 2)
{
ans++;
}
}
cout << ans;
nl;
return 0;
}
B — Nikhil Penon
The remaining pens are begin divided into 2 people. So In case of no fight, the sum of the pens will be even or odd ?
Is it possible to remove a packet and make the sum of remaining even ?
When will we select the odd packet to remove ? When will we select the even packet to remove ?
If the sum is even initially then we select the even packets because if we remove a packet containing an even number of pens the sum of the remaining is even therefore no fights so the ans will be the number of even packets.
If the sum is odd initially then we select the odd packets because if we remove a packet containing an odd number of pens the sum of the remaining is even therefore no fights so the ans will be the number of even packets.
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll n = 1;
cin >> n;
vi a(n);
ll even = 0, odd = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] & 1) { odd++; }
else { even++; }
}
if (odd & 1)
{
cout << odd;
}
else
{
cout << even;
}
nl;
return 0;
}
C — Is It Possible ?
Can two numbers be equal when the sequence is sorted in strictly increasing or decreasing order ?
Read the first hint again !
If there are two elements with the same value, then the answer is NO, because neither of these values is less than the other.
Otherwise, the answer is YES, since we can just sort the array.
The time complexity is O(nlogn) or O(n) depending on the implementation.
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--)
{
ll n;
cin >> n;
set <ll>a;
for (int i = 0; i < n; i++)
{
ll temp;
cin >> temp;
a.insert(temp);
}
if (a.size() == n)
{
cout << "YES";
}
else
{
cout << "NO";
}
nl;
}
return 0;
}
D — Messenger of God
How many consecutive a are possible ?
can the letters alternate between a and b ?
Every character in strings aa, aaa, bb and bbb has at least one character adjacent to it that is the same. So, if there is an isolated character in our string (a character that has no neighbors equal to it), we cannot build it.
It's easy to see that in the other case, we can build the string: we can split it into blocks of consecutive equal characters, and since there are no isolated characters, each block will have at least 2 characters, so it can be formed from strings of length 2 and/or 3 consisting of equal characters.
So, the problem is reduced to checking if each character has a neighbor equal to it.
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--)
{
string s;
cin >> s;
bool ans = true;
for (int i = 0; i < s.length(); i++)
{
if ((i == 0 || s[i] != s[i - 1]) && (i == s.length() - 1 || s[i] != s[i + 1]))
{
ans = false;
}
}
ans ? cout << "YES" : cout << "NO";
nl;
}
return 0;
}
E — Mess is a Mess
If the elements are same but the order is different, then how many operation will it take ?
which type of operation should we focus on ?
Count the number of 1's from both the sequences, if the number of ones in both the sequence is same then we can simply rearrange the sequence. else we take the absolute value of the difference + 1 (rearrangement)
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll inc = 0;
ll suma = 0, sumb = 0;
vi a(n), b(n);
for (int i = 0; i < n; i++) { cin >> a[i]; suma += a[i]; }
for (int i = 0; i < n; i++) { cin >> b[i]; sumb += b[i]; }
for (int i = 0; i < n; i++) { if (a[i] != b[i]) { inc++; } }
if (suma == sumb)
{
(inc == 0) ? cout << "0" : cout << "1";
}
else
{
cout << min(abs(suma - sumb) + 1, inc);
}
nl;
}
return 0;
}
F — Diamond Digger
Bro, Seriously
What's wrong with you.
Draw the grid graph as the problem said.
Just a few basics of your programming language. It's easy.
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll n;
cin >> n;
for (int i = 0; i < n; i++)
{
int t = 0;
int m = n / 2;
if (i > m) t = i - m;
else t = m - i;
for (int j = 0; j < t; j++) { cout << '*'; };
for (int j = 0; j < n - t - t; j++) { cout << "D"; }
for (int j = 0; j < t; j++) { cout << '*'; };
nl;
}
return 0;
}
G — T.T Players
Probably world class TT players. As no datatype can hold these huge values, or atleast cannot quick operations on it.
Imagine 2 numbers 100 and 1000, here 100 < 1000 and if we divide both side by min(100,1000) then it becomes 1 < 10 , the result remains the same if we divide both numbers by some number. Think of some number to divide the powers in the given problems.
First, let's say that appending the number with p zeros is the same as multiplying it by 10^p
The given numbers are so large that they can't fit into any reasonable integer type. Even if you use a language with unlimited length integers (python, for example) or store the numbers in strings, you should still face the time limit issue. So let's learn to shrink the numbers a bit.
Note that the result of the comparison of two numbers doesn't change if you divide both numbers by the same positive number. So we can keep dividing both numbers by 10 until one of them is not divisible anymore. Let's also ignore the trailing zeros in x1 and x2 and leave them as is. If the first number is appended with p1 zeros and the second numbers is appended with p2 zeros, we can subtract min(p1,p2) from both values, effectively dividing both numbers by 10min(p1,p2)
This way, one of the numbers becomes short enough to fit into an integer type (because it has p=0 and x is only up to 10^6). The other number might still be large enough.
However, if it's really large, we can instantly say that it's larger than another one. Say, if its p is at least 7. This number it at least 10^7 and the other number is at most 10^6 Otherwise, we can calculate this number as well and compare the values normally.
Overall complexity: O(1) per testcase.
Credits: BledDest
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--)
{
ll x1, p1, x2, p2;
cin >> x1 >> p1 >> x2 >> p2;
ll mi = min(p1, p2);
p1 -= mi;
p2 -= mi;
if (p1 >= 7)
{
cout << ">";
nl;
}
else if (p2 >= 7)
{
cout << "<";
nl;
}
else
{
for (int i = 0; i < p1; i++) { x1 *= 10; }
for (int i = 0; i < p2; i++) { x2 *= 10; }
if (x1 > x2)
{
cout << ">";
nl;
}
else if (x2 > x1)
{
cout << "<";
nl;
}
else
{
cout << "=";
nl;
}
}
}
return 0;
}
H — Double Sort
Is it possible if a is sorted and b is not and all elements are distinct, can we make b array sorted as well ?
If the elements are not distinct ?
Imagine that all elements of a are distinct. This way, sorting a in increasing order will fix the order of b
If b turns out sorted in a non-decreasing order, then the answer exists. Otherwise, it doesn't. To obtain the sequence of swaps, you can sort a with any comparison-based sorting algorithm you want: even bubble sort will not exceed the allowed number of swaps.
What changes if a has repeated elements? Distinct elements are still ordered among themselves, but now there are also blocks of equal elements. For each block, look into the corresponding values in b. Obviously, these have to be sorted in a non-decreasing order. Rearrange them as they should be.
In fact, this is exactly the same as sorting the sequence of pairs (ai,bi) with a default comparator — first by ai, then by bi
Since we fixed the wanted order, we can proceed with the same steps we made in a distinct case.
Overall complexity: O(nlogn) or O(n2) per testcase. Credits: BledDest
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
vector<int> b(n);
for (int i = 0; i < n; i++)
{
cin >> b[i];
}
vector<pair<int, int>> p(n);
for (int i = 0; i < n; i++)
{
p[i] = make_pair(a[i], b[i]);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<pair<int, int>> res;
bool fail = false;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (p[j] == make_pair(a[i], b[i]))
{
swap(p[i], p[j]);
if (i != j)
{
res.emplace_back(i, j);
}
break;
}
}
if (p[i] != make_pair(a[i], b[i]))
{
fail = true;
break;
}
}
if (fail)
{
cout << -1 << '\n';
}
else
{
cout << res.size() << '\n';
for (auto &p : res)
{
cout << p.first + 1 << " " << p.second + 1 << "\n";
}
}
}
return 0;
}
I — Trick or Treat
First the sequence will increase then decrease then increase again.
You can find the first position where the sequences start decreasing from the beginning. Call it L. You can find the first position where the sequences start increasing from the end. Call it R.
Now we just need to reverse the segment between a[L] to a[R].
Let us define L to be smallest index such that A[i]! = i. Let us also define R to be largest index such that A[i]! = i.
Note that if there is no such L and R, it means that array is sorted already. So answer will be "yes", we can simply reverse any of the 1 length consecutive segment.
Otherwise we will simply reverse the array from [L, R]. After the reversal, we will check whether the array is sorted or not.
Complexity: O(nlogn)
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
bool ispal(vector<ll> a)
{
bool ok = true;
ll n = a.size();
for (int i = 0; i < n; i++)
{
if (a[i] != a[n - 1 - i])
{
ok = false;
}
}
return ok;
}
int main()
{
fast;
ll n;
cin >> n;
vi a(n);
ll cnt = 0;
bool ok = false;
bool ama = true;
for (int i = 0; i < n; i++) { cin >> a[i]; }
int l = 0;
while (l + 1 < n && a[l] < a[l + 1])
{
++l;
}
int r = l + 1;
while (r < n && a[r] < a[r - 1])
{
++r;
}
reverse(a.begin() + l, a.begin() + r);
for (int i = 1; i < n; ++i)
{
if (a[i] < a[i - 1])
{
puts("no");
return 0;
}
}
cout << "yes\n";
cout << l + 1 << " " << r;
return 0;
}
J — Fun Bunk
sort ?
-1 * -1 = 1
negative * negative = positive
Sort the array. if all the numbers are less than 0 or greater than 0, simply multiply the 5 biggest elements. else if the array is containing both negative and positive number then calculate all the possible permutation of the 5 largest and 5 smallest elements. (smallest referring to high magnitude negative numbers.)
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
typedef long long int ll;
typedef vector<ll> vi;
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--)
{
int n; cin >> n;
vi a;
for (int i = 0; i < n; i++)
{
ll x; cin >> x;
a.push_back(x);
}
ll ans = INT64_MIN;
sort(all(a));
for (int i = 0; i < 6; i++)
{
ll cur = 1;
for (int x = 0; x < i; x++)
{
cur *= a[x];
}
for (int x = 0; x < 5 - i; x++)
{
cur *= a[n - 1 - x];
}
ans = max(ans, cur);
}
cout << ans;
nl;
}
return 0;
}