Contest Link: ENCO2020
Problem Marble Game
Problem Setter vasu2907
Logic
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math
PROBLEM:
There are N marbles. A and B plays alternately, and A goes first. Each player can choose 1 marble or even a number of marbles in his turn. The player who is not able to choose any marbles loses the game. Print the name of the loser.
QUICK EXPLANATION:
A will only lose when the number of marbles is 3. For all the other values if marbles, B will lose.
EXPLANATION
There are 2 cases
1st case (when n is even)
A will take all n marbles and B will loose
2nd case ( when n is 2k +1 and n>3)
A will take even number of marbles say 2m
Hence B will left with 2*(k-m) +1 marbles such that 2*(k-m) +1 != 1
This is again odd and hence the process repeats until A is left with only 1 marble ( Since A got the first chance he will play optimally, and will always choose 2*k-2 marbles so that B is left with 3 marbles).
For example, in the case of 5 Marbles
A will take 2 marbles
B is left with 3 Marbles
B will again take 2 Marbles and A is left with one marble so he will take it and win
The only case where A will loose is the case when the number of Marbles is 3
Here no matter whatever Marbles A take
He will loose
1st case: A takes 1 marble, B is left with 2 marble, he will take all as it is even, A Loose.
2nd case: A takes 2 marble, B is left with 1 marble only, He will take it (as taking 1 marble is permissible )
A will Loose.
Editorialist's Solution
#include<bits/stdc++.h>
typedef long long int ll;
#define pb push_back
#define mod 1000000007
using namespace std;
ll t,n;
bool flag;
int main()
{ cin>>t;
while(t–){
cin>>n;
if(n==3) cout<<“B”<<endl;
else cout<<“A”<<endl;
}
return 0;
}
Problem Contaminated Matrix
Problem Setter vasu2907
Logic
DIFFICULTY:
Easy
PREREQUISITES:
Matrix operations
PROBLEM:
Given a matrix of size N*M, where each cell can be empty, blocked, or contain the coronavirus. The virus can move only in the same row or in the same column until it gets blocked. Count the number of cells, where the virus can be present.
QUICK EXPLANATION:
We can traverse the matrix in four directions and mark the effect of a virus till it is not blocked by the wall. The effect of a virus can be denoted by a boolean array of the same size as that of the original matrix, N*M.
EXPLANATION:
The problem is just about implementation.
We can simply solve the problem by traversing the
m*n matrix in all four direction (left,right,up, down).
We can do it as…
Let Suppose We have m*n vis matrix
vis[M][N] which is all set to false;
Now traverse from left to right to find all the affecting pos right to the virus
bool virus_here=false;
if(there is an virus){
set the virus_here var true;
virus_here=true;
}else if(here is a block){
from this positon the affect of previous virus will be nullified
virus_here=false
}
if(virus_here){
vis[row][col]=true;
}
this was for simulation of one direction
similarly, you can do it for rest directions.
Editorialist's Solution
#include<bits/stdc++.h>
#include
typedef long long int ll;
using namespace std;
ll ar[1003][1003],dprow[1003][1003],dpcol[1003][1003];
ll n,m,k;
bool flag;
ll solve(){
cin>>n>>m;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>ar[i][j]; dprow[i][j]=0,dpcol[i][j]=0;
}
}
// Checking row wise
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(ar[i][j]==-1) continue;
k=j;flag=0;
while(k<=m && ar[i][k]!=-1){
if(ar[i][k]==1) flag=1;
k++;
}
if(flag) dprow[i][j]+=1,dprow[i][k]+=-1;
j=k;
}
}
// Checking column wise
for(ll j=1;j<=m;j++){
for(ll i=1;i<=n;i++){
if(ar[i][j]==-1) continue;
k=i;flag=0;
while(k<=n && ar[k][j]!=-1){
if(ar[k][j]==1) flag=1;
k++;
}
if(flag) dpcol[i][j]+=1,dpcol[k][j]+=-1;
i=k;
}
}
// taking cumulative
for(ll i=1;i<=n;i++) for(ll j=2;j<=m;j++) dprow[i][j]+=dprow[i][j-1];
for(ll j=1;j<=m;j++) for(ll i=2;i<=n;i++) dpcol[i][j]+=dpcol[i-1][j];
ll ans=0;
for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) ans+=(dprow[i][j]>0 || dpcol[i][j]>0);
return ans;
}
int main()
{ ll t;
cin>>t;
while(t–){
ll ans=solve();
cout<<ans<<endl;
}
return 0;
}
Problem Contest Setting
Problem Setter dshaurya
Logic
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Binary Search
PROBLEM:
Given 2 integers n, q. You are also given n integers d1, d2, d3,. . . , dn. You need to pick q integers out of these n integers such that the difference between the two closest integers is maximum.
QUICK EXPLANATION:
Sort the numbers and find the desired number by binary search.
EXPLANATION:
Since the maximum value of n is 10^6 and q<=n, we won’t be able to use brute force by selecting all the combinations of q numbers and finding the largest minimum difference in each iteration. What we need to do is basically take all number from 1 to 10^9 and check if anyone of these will be able to fit the desired difference correctly. The largest difference that works for the array (that is we are able to pick q integers out of n) can be found using binary search.
Let us say we pick a number x and consider it as the largest minimum difference between two numbers among the selected q numbers. If for value x it is possible to pick q integers then we know that for any value less than x we will definitely be able to pick q integers and if for value x it is not possible to pick q integers then we know that for any value greater than x we cannot pick q integers. So on this principle we find the maximum value of x using binary search.
Time Complexity -
O(n logn) for both, sorting and binary search with checking operation.
Editorialist's Solution
#include<bits/stdc++.h>
typedef long long int ll;
#define pb push_back
#define mod 1000000007
using namespace std;
int main()
{ ll n,c;
cin>>n>>c;
vector arr(n);
for(ll i=0;i<n;i++) cin>>arr[i];
sort(arr.begin(),arr.end());
ll start=0,end=arr[n-1]-arr[0],mid,counter=1,k,maxi=INT_MIN;
while(start<=end)
{ k=0;
counter=1;
mid=(end-start)/2;
mid+=start;
for(ll i=0;i<n;i++)
{ if(arr[i]-arr[k]>=mid)
{ k=i;
counter++;
}
}
if(counter>=c) start=mid+1,maxi=mid;
else end=mid-1;
}
cout<<maxi<<endl;
return 0;
}
Problem Mysterious Tree
Problem setter vasu2907
Logic
DIFFICULTY:
Hard
PREREQUISITES:
Trees, LCA, Binary Search.
PROBLEM:
Given a rooted tree at vertex 1 and consisting of n nodes. The nodes are connected by edges having some weight w. Node v can move to node u, only if node u is not node v and node u is in the subtree of node v, and the path weight (from node v to node u) is less than or equals to the value associated at the destination node, i.e, value at node u. Thus, for each node v, print the number of vertices it can reach from node v.
QUICK EXPLANATION:
For every node, count the number of ancestors who can visit the given node.
EXPLANATION:
Let’s fix a vertex v . This node adds +1 to all the ancestors whose depth depth [v] - a[v] ≤ depth[p] ( depth[v] = the sum of the weights of edges on the path from the root to the vertex v ). It’s a segment of the ancestors, ending in v, as the depth increases when moving to the leaves. It remains to find the first ancestor on the way up, it does not hold for him - so you can make a binary lifting or binary search if you will be storing the path to the root in dfs. With the partial sums, you can calculate the answer for each vertex.
Editorialist's Solution
#include<bits/stdc++.h>
#include
typedef long long int ll;
#define pb push_back
#define mod 1000000007
using namespace std;
vector ar(200005),dp(200005);
vector<pair<ll,ll> > adj[200005],g[200005],v2;
vector vect[200005];
vector mark(200005);
bool comp(pair<ll,ll> a,pair<ll,ll> b)
{ return a.first<b.first;
}
ll par[200005];
void dfs(ll u,ll p,ll dis,ll lev)
{ mark[u]=1; par[u]=p;
vect[lev].pb(u);
if(u!=1)
{ auto id=lower_bound(v2.begin(),v2.end(),make_pair(dis-ar[u],0LL),comp)-v2.begin();
if(id!=v2.size())
{ dp[p]+=1;
dp[par[v2[id].second]]-=1;
}
}
v2.pb({dis,u});
for(auto v:adj[u])
{ if(!mark[v.first])
dfs(v.first,u,dis+v.second,lev+1);
}
v2.pop_back();
}
vector ans(200005),weight(200005);
void find_par(ll u,ll p,ll w){
mark[u]=1;
par[u]=p;
weight[u]=w;
for(auto e: g[u]){
if(!mark[e.first]) find_par(e.first,u,e.second);
}
}
int main()
{ ll n,a,b,u,v,w;
cin>>n;
for(ll i=1;i<=n;i++) cin>>ar[i];
for(ll i=1;i<n;i++){
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
}
find_par(1,1,0);
for(ll i=2;i<=n;i++){
adj[par[i]].pb({i,weight[i]});
}
fill(mark.begin(),mark.end(),false);
dfs(1,0,0,0);
for(ll i=n-1;i>=0;i–)
{ for(auto j:vect[i])
{ ans[j]+=dp[j];
for(auto k:adj[j])
{ ans[j]+=ans[k.first];
}
}
}
for(ll i=1;i<=n;i++) cout<<ans[i]<<" ";
}
Problem Mirzapur Election
Problem Setter gabilash
Logic
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Math, Data Structures
PROBLEM:
The question boils down to two simple queries:
- To update an array element.
- To find Max-Potential ( = maximum of gcd of any pair in the array).
QUICK EXPLANATION:
Find the largest number f which is a factor of at least two numbers present in the array.
EXPLANATION:
Say, f is a factor for more than one array elements, then Max-Potential >= f.
Proof: There are at least two elements in the array which can be represented as fk1 and fk2 whose gcd(fk1, fk2) >= f.
From the above point, it is evident that Max-Potential is the largest f, which is a factor of at least 2 elements in the array.
IMPLEMENTATION DETAILS
Maintain the count of the array elements which is divisible by f.
( count[f] = no of array elements divisible by f)
To find the max f whose count[f] >= 2, we can make use of a data-structure like the set.
Note 1: Since there is a need to find the factors for numbers in the range [1…A=1e5], we should pre-process and store the factors for every number priorly, before starting to process the queries. It can be done with an approach, very similar to Sieve of Eratosthenes in O(A*log(A)).
Note 2: Time Constraints were intentionally made strict to restrict the solutions using O(sqrt(A)) for finding the factors during query handling.
Time Complexity: O(A*log(A)log(A) + qlog(A)*log(A))
Please see the code for more details.
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
using namespace std::chrono;
const int MAX_A=1e5, N=1e5;
vectordivisors[MAX_A+5];
int a[N+5],_count[MAX_A+5];
setgcds;
void pre_process(){
for(int i=1;i<=MAX_A;i++){
for(int j=i;j<=MAX_A;j+=i){
divisors[j].push_back(i);
}
}
}
void add(int data){
for(auto x:divisors[data]){
_count[x]++;
if(_count[x]==2){
gcds.insert(x);
}
}
}
void remove(int data){
for(auto x:divisors[data]){
_count[x]–;
if(_count[x]==1){
gcds.erase(x);
}
}
}
void solve(){
pre_process();
int n,q;cin>>n>>q;
for(int i=0;i<n;i++) cin>>a[i],add(a[i]);
while(q–){
int type;cin>>type;
if(type==1){
int index,data;
cin>>index>>data;
remove(a[index]);
a[index]=data;
add(a[index]);
continue;
}
cout<<(*gcds.rbegin())<<“\n”;
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
solve();
}