MODULO3-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh

DIFFICULTY:

978

PREREQUISITES:

None

PROBLEM:

Stack likes number 3 a lot.

He has two non negative integers a and b.
He gets happy if atleast one of them to be divisible by 3.

In order to get happy, he can perform some moves(possibly 0).

In one move,

  • he can change a to abs(a-b), or
  • he can change b to abs(b-a)

Find the minimum number of moves after which Stack gets happy.

It can be proved that Stack can get happy after performing finite number of moves.

EXPLANATION:

There are three cases:
Case (a % 3==0 || b % 3==0) : The answer is 0.
Case (a % 3==b % 3 && b % 3!=0) : The answer is 1 as subtracting the minimum of a or b from their maximum results in a number divisible by 3.
Case (a % 3!=b % 3 && b % 3!=0 && a % 3!=0 ) : Let a % 3==1 and b % 3==2(otherwise swap them), subtract a from b twice to get a number divisible by 3. The answer is 2 in this case.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long 
const ll INF_MUL=1e13;                                                             
const ll INF_ADD=1e18; 
#define pb push_back               
#define mp make_pair           
#define nline "\n"                              
#define f first                                       
#define s second                                        
#define pll pair<ll,ll>    
#define vl vector<ll>   
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>> 
#define all(v) v.begin(),v.end()
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);        
#endif                 
void _print(ll x){cerr<<x;}     
void _print(string x){cerr<<x;}  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using muloset=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;        
const ll MAX=500500;
vector<ll> value(MAX);
vector<vector<ll>> adj;
vector<multiset<ll>> track(MAX); 
void dfs(ll cur,ll par){
    for(auto chld:adj[cur]){
        if(chld!=par){   
            dfs(chld,cur);
            if(track[chld].size()>track[cur].size()){
                swap(track[chld],track[cur]);
            }
            for(auto i:track[chld]){
                track[cur].insert(i);
            }
        }
    }
    if(track[cur].empty()){
        track[cur].insert(value[cur]);
    }   
    else{
        auto fs=track[cur].begin();
        ll val=*fs;
        if(val<value[cur]){
            track[cur].erase(fs);
            track[cur].insert(value[cur]); 
        }
    }
}     
void solve(){               
    ll a,b; cin>>a>>b;
    a=a%3,b=b%3;
    if(min(a,b)==0){
        cout<<"0\n";
    }
    else if(a==b){
        cout<<"1\n";
    }
    else{
        cout<<"2\n"; 
    }
    return;           
}                                                        
int main()                                                                            
{ 
    ios_base::sync_with_stdio(false);                                    
    cin.tie(NULL);                         
    #ifndef ONLINE_JUDGE                   
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);      
    freopen("error.txt", "w", stderr);                        
    #endif        
    ll test_cases=1;                   
    cin>>test_cases; 
    while(test_cases--){
        solve();
    }
    cout<<fixed<<setprecision(15);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}    
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int a, b;
    cin >> a >> b;
    if (a % 3 == 0 || b % 3 == 0)
        cout << 0 << '\n';
    else if (a % 3 == b % 3)
        cout << 1 << '\n';
    else
        cout << 2 << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}


Can someone explain how my solution passed? :rofl:
https://www.codechef.com/viewsolution/66347332

because, any two numbers needs at most two operations and always replacing max(a, b) with the abs(a-b) works.

This is a rather interesting case where it turns out your code is somehow optimized by the compiler into being ‘correct’, as far as I can tell.

The first thing to note is that having a function that doesn’t return anything (which is the case with your f when a < b) is undefined behavior, so really anything could happen.

Now is the interesting part: on optimization level O0, your code gives wrong answers as expected; but on O1 or higher it appears the compiler optimizes something so that the output ends up being correct anyway. To your luck, I believe Codechef runs submissions on optimization level O2 by default so you were able to get AC.

Looking at the generated assembly shows a clear difference in what is generated at O0 and on higher levels, but I don’t know assembly so I can’t tell you what’s going on - maybe someone else more knowledgeable in this field can help with that.

At any rate I ran a stresstest against a correct solution for quite a while and failed to find a failing case locally so I’m inclined to believe this works for all 0 \leq a, b \leq 10^{18}, tl;dr you got lucky and that code is actually ‘correct’, congrats.

1 Like

Thank you so much for the analysis!

https://www.codechef.com/viewsolution/66660722
can someone help why this code is wrong?