PROBLEM LINK:
Setter- Igor Barenblat
Tester- Misha Chorniy
Editorialist- Abhishek Pandey
DIFFICULTY:
Cakewalk
PRE-REQUISITES:
Basic Maths of power and exponents, if-else statements
PROBLEM:
Given a, b and n , we need to tell if {a}^{n}>{b}^{n} or not.
QUICK EXPLANATION:
Key to Success: While its a cakewalk question, and everyone gets AC, edge is gained over others by implementing the correct solution quickly. A proper insight of conditions is the key to success here.
There are many ways to do the question. As I said, a good insight in condition helps. We simply make cases for-
- if a==b or (n is even AND abs(a)==abs(b))
- if n is even - we check if a is greater or b
- if n is odd, compare a and b and print corresponding answer.
Try making a solution using these if this question gave you a problem during contest!!
EXPLANATION:
We will have a single section in this editorial, and will refer to tester @mgchâs solution for reference.
Full Solution-
âOMG SO MANY CONDITIONS. WTF?! A AND B CAN BE NEGATIVE AS WELL!!! HOLY COW INFINITE IF-ELSE WTFFFFFF RIP EVERYTHING RIP GGWP I M DEADâ
If you are one of those who have similar problems, then this editorial is just for you. There are multiple ways to tackle this statement, but I will discuss testerâs approach here as I find it elegant
We will, this time, use Divide and conquer. Divide the cases into sub-cases until they are easy to conquer!! xD
Lets formalize our cases. I assume you know about absolute function ( abs() ) of C++. If not, check tab below.
Click to view
If input is a positive number, return it. If input is a negative number, multiply it with -1 to make it positive and then return it. This is abs() function in simple words.
a. When will answer be 0?
Simple. If A==B OR If (N is even and abs(A)==abs(B)). Only these cases are possible.
We hence get the following condition-
If A==B OR (N is even AND abs(A)==abs(B) ):
Print(0);
Good, we have done 33\% of the problem. But making cases more cases like, when will answer be 1 or when will it be 2 is tedious. What is a bugging thing right now? Oh yes! The signs are of A and B may not be same. Lets deal with it.
If N is even, then we dont care of signs. Thats a great case. We can easily frame this condition now-
If N is EVEN:
Print 1 if abs(a)>abs(b)
Print 2 if abs(b)>abs(a)
Now, we are left with cases where N is odd. Signs will matter here, so lets deal with it now. In case you feel âNow we are left with cases where N is oddâ a too sudden conclusion, the tab below is for you :).
Click to view
Recall that we are using an if-else-if ladder. An else or else-if block (of statements) will not execute if condition of any of the if's above it are satisfied which leads to that if block being executed. Atmost one of the blocks get executed.
\implies if our second condition (N is even) didnt execute, then N is odd.
Now, if N is odd, I said signs matter. Yes, they âmatterâ a lot indeed :). Hence, ignore them! Nobody should matter so much xD. Our next condition is-
If N is odd: //automatically implied
Compare if A>B or B<A and print corresponding answer.
We are DONE with this question after this! :D. A question for you, why did we not care for signs here?
Any bonus content is in Chef Vijjuâs Corner.
SOLUTIONS:
It takes time for @admin to link solutions and get the links working. If they arent working for you, please open the tab below to check the codes.
Click to view
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
#define int long long
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;
///---program start---///
void solve()
{
int a,b,n;
cin>>a>>b>>n;
if (n%2==0){
int ans=0;
a=abs(a);
b=abs(b);
if (a>b){
ans=1;
}
elif (a<b){
ans=2;
}
else{
ans=0;
}
cout<<ans<<"\n";
}
else{
pii cur1={a<0?-1:a==0?0:1,a};
pii cur2={b<0?-1:b==0?0:1,a};
if (cur1.fir>cur2.fir){
cout<<1<<"\n";
}
elif (cur1.fir<cur2.fir){
cout<<2<<"\n";
}
else{
if (cur1.fir<0){
if (abs(a)<abs(b)){
cout<<1<<"\n";
}
elif (abs(a)>abs(b)){
cout<<2<<"\n";
}
else{
cout<<0<<"\n";
}
}
elif (cur1.fir==0){
cout<<0<<"\n";
}
else{
if (abs(a)<abs(b)){
cout<<3-1<<"\n";
}
elif (abs(a)>abs(b)){
cout<<3-2<<"\n";
}
else{
cout<<0<<"\n";
}
}
}
}
}
main()
{
#ifdef I_love_Maria_Ivanova
files("barik");
freopen("debug.txt","w",stderr);
#endif
int test;
cin>>test;
while (test--){
solve();
}
}
Click to view
#include <bits/stdc++.h>
using namespace std;
const int MaxN = (int)4e5 + 10;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
void solve() {
int a, b, n;
scanf("%d%d%d", &a, &b, &n);
if (a == b || (n % 2 == 0 && a + b == 0)) {
printf("0\n");
return;
}
if (n % 2 == 0) {
printf("%d\n", 1 + (abs(b) > abs(a)));
return;
}
if ((a < 0) != (b < 0)) {
printf("%d\n", 1 + (a < 0));
return;
}
printf("%d\n", 1 + (a < b));
}
int main() {
// freopen("input.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t --> 0) {
solve();
}
return 0;
}
Editorialistâs solution will be put on demand.
Time Complexity=O(1) per test case.
CHEF VIJJUâS CORNER
1. Why not care for signs if N is odd?
Click to view
Say signs are not same. A simple comparison will tell which number is positive (as a positive number is always greater!) and hence no need to consider sign here. Say signs are same, again we handle this case by checking which of the two is greater.
2. Why we dont care to calculate {a}^{n} and {b}^{n}
Click to view
Exponents are same!! Hence, a larger number raised to power n is always greater than smaller number raised to power n!!
3.Test Case Bank-
Click to view
Official Input- 1000-334467 334467 2348876334467 -334467 2348876-334467 334467 234887733 - Pastebin.com
Official Output- 002121211222112211110212112 - Pastebin.com
4. Related Problems-
- B. High School: Become Human - A tougher version of this problem