Details
Date: 29th January 2022
Time: 03:00 pm to 06:00 pm
Platform: codeforces
By: The Society of Coders, IIIT Naya Raipur
For: BTech Students
Contest Link: DesCode 4.0
We would like to express our great gratitude to:
- monkedluffy, k_rishabh, shinigami_09 and momotaroUWU for the coordination of the round and preparing problems.
- Yoks1729- and sandesh_04_06 for testing the round and providing useful feedback.
- MikeMirzayanov for cool platforms Codeforces and Polygon.
This contest had 3 hours to solve 8 problems.
Editorial
Thanks for participating, hope you enjoyed the problems!
Please do not hesitate to provide feedback, so we can improve in setting problems next time.
Problem — A : Majnu Ki Mishri
We have to make $$$A$$$ equal to $$$B$$$ by adding $$$x$$$ any number of time.
We initially have $$$Rs$$$ $$$A$$$ and we have to achieve amount $$$Rs$$$ $$$B$$$ by adding only $$$Rs$$$ $$$x$$$ any number of time .
If we assume $$$k$$$ is number of notes required . We just have to solve the equation $$$A$$$$$$+$$$$$$k$$$$$$x$$$$$$=$$$$$$B$$$.
The solution exists if $$$B$$$$$$-$$$$$$A$$$ is divisible by $$$x$$$ and the answer will be $$$B$$$$$$-$$$$$$A$$$ divided by $$$x$$$ else $$$-1$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int main(){
fastIO();
ll t;
cin>>t;
while(t--){
ll a,b,x;
cin>>a>>b>>x;
if((b-a)%x==0 && b>=a){
cout<<(b-a)/x<<endl;
}
else cout<<-1<<endl;
}
return 0;
}
a, b, x = map(int, input().split())
if((b - a) % x == 0):
print((b - a) // x)
else:
print(-1)
Problem — B : Hello Ramanujan
Prerequisites: 2-d array.
The idea behind this problem is pretty simple, Iterate through the 2-d array from the top-left corner ie. $$$1$$$st row and $$$1$$$st column, and find out if there are $$$k$$$ consecutive unoccupied rooms on the current row. If rooms are found, replace them with \t{'F'} otherwise print no. As the higher floored rooms are preferred, the normal iteration would give the optimal results.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) (x).begin(),(x).end()
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
void solve(){
//inputs
ll n , m , k ; cin >> n >> m >> k ;
vector<string> v ;
string req;
for(int i = 0 ; i < k ; i++){
req.pb('O');
}
for(int i = 0 ; i < n ; i++){
string s ; cin >> s ;
v.pb(s);
}
//iterating through the matrix :
for(auto &x : v){
string t = x ;
for(int i = 0 ; i <= m-k ; i++){
if(t.substr(i,k) == req){ //required condition
yes;
ll yo = i;
while(k--){
x[yo] = 'F'; //replacing with F
yo++;
}
for(auto x : v){
cout << x << endl;
}
return;
}
}
}
no;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc = 1;
// cin >> tc;
while(tc--)
{
cout << setprecision(15) << fixed ;
solve();
cout << endl;
}
}
n, m, k = map(int, input().split())
a = ["" for i in range(n)]
for i in range(n):
a[i] = list(input())
# print(a)
flag = False
row = -1
for i in range(n):
cur, cnt = -1, 0
for j in range(m):
if(a[i][j] == "O" and cur == -1):
cur = j
cnt = 1
elif(a[i][j] == "O"):
cnt += 1
else:
cur = -1
cnt = 0
if(cnt == k):
row = i
flag = True
break
if(flag):
break
if(flag):
for i in range(k):
a[row][cur + i ] = 'F'
print("YES")
for i in a:
print(''.join(i))
else:
print("NO")
Problem — C : Good Bye Bhabha
As we need to construct set's of the form $$$1$$$ to $$$k$$$. We can solve this problem by storing frequencies of the baggage's.
Think about the maximum size of the set you can construct given the number of baggage's is $$$n$$$ ($$$1$$$ $$$≤$$$ $$$n$$$ $$$≤$$$ $$$10^5$$$).
For minimizing the baggage's to be carried, we need to maximize the size of each set of baggage's.
The idea behind the solution is to store the frequencies of all the baggage's which have value $$$≤$$$ $$$10^5$$$ because the maximum number of baggage's we can have is $$$10^5$$$. For minimizing the baggage's to be carried, we need to maximize the size of each set of baggage's. For maximizing size of each set, we start constructing set's of maximum possible size and reducing their frequencies after each set. For keeping track of number of baggage's for all set's, we add the size of each set in a $$$cnt$$$ variable. We do this until the frequency of value $$$1$$$ becomes $$$0$$$ because $$$1$$$ is the first baggage for every set. We cannot construct more set's if there is no $$$1$$$ available.
So the minimum number baggage's to be carried by $$$Rishabh$$$ is $$$n$$$ $$$-$$$ $$$cnt$$$.
Overall Complexity : $$$O(n)$$$ or $$$O(nlogn)$$$ (for map) for each testcase
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
int main() {
ll t ;
cin >> t ;
while (t--)
{
ll n , cnt = 0 ;
cin >> n ;
ll a[100002] = {0} ;
for(ll i = 0 ; i < n ; i++)
{
ll x ;
cin >> x ;
if(x <= 100000)
a[x]++ ;
}
while(a[1] != 0){
cnt++ ;
a[1]-- ;
ll x = 2 ;
while(a[x] != 0){
cnt++ ;
a[x]-- ;
x++ ;
}
}
cout << n - cnt << endl ;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std ;
using namespace std::chrono;
#define ll long long
#define pb push_back
#define yes cout << "YES"
#define no cout << "NO"
#define all(x) (x).begin(),(x).end()
const long long int mod = 1e9 + 7 ;
const long long int INF = 1e18 ;
void readvec(vector<ll> &v){
for(int i = 0 ; i < v.size() ; i++){
cin >> v[i] ;
}
}
void printvec(vector<ll> &v){
for(int i = 0 ; i < v.size() ; i++){
cout << v[i] << " ";
}
}
//For debugging :
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(long long t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(long double t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(unsigned long long t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
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 << "]";}
//binary exponentiation
long long binpow(long long a, long long b) {
if (b == 0)
return 1;
long long res = binpow(a, b / 2);
if (b % 2)
return res * res * a;
else
return res * res;
}
void solve(){
ll n ; cin >> n ;
vector<ll> v(n); readvec(v);
map<ll,ll> m ;
for(auto x : v){
m[x]++;
}
ll a = INF , maxi = *max_element(all(v));
for(int i = 1 ; i <= maxi ; i++){
if(m[i] == 0){
a = i ;
break;
}
}
debug(a)
if(a == INF){
a = maxi;
}
debug(a)
debug(m)
ll ans = 0 ;
while(m[1] > 0){
debug(m)
ll yo = 1 ;
while(m[yo] > 0){
ans++;
m[yo]--;
yo++;
}
}
cout << n - ans;
}
int main(){
auto start = high_resolution_clock::now();
ios::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("Error.txt", "w", stderr);
#endif
int tests = 1 , test_case = 1;
cin >> tests ;
while(tests--){
cout << setprecision(15) << fixed ;
solve() ;
cout << '\n' ;
// cout << "Case #" << test_case << ": " << ans << '\n' ;
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cerr << "\n\nTime taken : " << fixed << duration.count() / 1000000.0 << "seconds" << "\n";
}
from collections import defaultdict
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
mp = defaultdict(int)
for i in a:
mp[i] += 1
if(mp[1] == 0):
print(n)
else:
cur = -1
prev = -1
good = 0
for k, v in mp.items():
if(prev == -1):
prev = k
cur = v
good += cur
else:
if(k != prev + 1):
break
else:
prev = k
cur = min(v, cur)
good += cur
print(n - good)
Problem — D : Dhaval Trouble
Handle the corner cases for $$$a$$$ $$$>$$$ $$$b$$$ and $$$a$$$ $$$=$$$ $$$b$$$.
Make two different cases for $$$even$$$ and $$$odd$$$ values of $$$a$$$.
On seeing the constraints on $$$a$$$ ($$$1$$$ $$$≤$$$ $$$a$$$ $$$≤$$$ $$$10^6$$$), $$$b$$$ ($$$1$$$ $$$≤$$$ $$$b$$$ $$$≤$$$ $$$10^{12}$$$) and following the pattern given operations will follow, we can say that the number of operations will never exceed $$$10^6$$$. So we can apply binary search to find the number of operations needed to make $$$a$$$ $$$=$$$ $$$b$$$.
If $$$a$$$ is even, then we can only apply the first operation on it because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. After following the pattern, we get that till $$$n^{th}$$$ operation we add $$$n(n+1)$$$ to $$$a$$$. Now we can easily apply binary search, to find the $$$n^{th}$$$ operation after which $$$a$$$ $$$=$$$ $$$b$$$. If the binary search gives no result, then the answer is $$$NO$$$ cause $$$n$$$ must be an integer, otherwise the answer is $$$YES$$$ and the number of operations is $$$n$$$.
If a is odd, then first we have to apply the second operation which adds $$$2i-1$$$ (an odd number) to $$$a$$$ making $$$a$$$ an even number. After this operation we can only apply the first operation on $$$a$$$ because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. Now we have already applied one operation, so $$$i$$$ starts from $$$2$$$ for next operation. After following the pattern, we get that till $$$n^{th}$$$ operation we add $$$n(n+1)-2$$$ to $$$a$$$. Now we can easily apply binary search, to find the $$$n^{th}$$$ operation after which $$$a$$$ $$$=$$$ $$$b$$$. If the binary search gives no result, then the answer is $$$NO$$$ cause $$$n$$$ must be an integer, otherwise the answer is $$$YES$$$ and the number of operations is $$$n+1$$$.
Overall Complexity : $$$O(logn)$$$ for each testcase
#include<bits/stdc++.h>
using namespace std;
void solve()
{
long long int a,b;
cin>>a>>b;
if(a==b)
{
cout<<"YES"<<'\n'<<0<<'\n';return;
}
if(a%2==0)
{
long long int s=0,e=1000000,ans=-1;
while(s<=e)
{
long long int mid=s+(e-s)/2;
long long int here=a+mid*(mid+1);
if(here>b)e=mid-1;
else if(here<b)s=mid+1;
else {ans=mid;break;}
}
if(ans==-1)
{
cout<<"NO"<<'\n';return;
}
cout<<"YES"<<'\n'<<ans<<'\n';return;
}
a++;
long long int s=0,e=1000000,ans=-1;
b+=2;
while(s<=e)
{
long long int mid=s+(e-s)/2;
long long int here=a+mid*(mid+1);
if(here>b)e=mid-1;
else if(here<b)s=mid+1;
else {ans=mid;break;}
}
if(ans==-1)
{
cout<<"NO"<<endl;return;
}
cout<<"YES"<<'\n';
cout<<ans<<'\n';
}
int main()
{
int tc=1;
cin>>tc;
while(tc--)
{
solve();
}
}
def solve():
a, b = map(int, input().split())
if(a == b):
print("YES")
print(0)
elif(a % 2 == 0):
l , r = -1, 1000000
while(r - l > 1):
m = (l + r)//2
if(a + m*(m+1) >= b):
r = m
if(a + m*(m+1) == b):
print("YES")
print(m)
return
else:
l = m
print("NO")
else:
a -= 1
l , r = -1, 1000000
while(r - l > 1):
m = (l + r)//2
if(a + m*(m+1) >= b):
r = m
if(a + m*(m+1) == b):
print("YES")
print(m)
return
else:
l = m
print("NO")
for _ in range(int(input())):
solve()
The idea behind the solution is to divide them in two cases for $$$even$$$ and $$$odd$$$ values of $$$a$$$.
If a is even, then we can only apply the first operation on it because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. Let us assume that after the $$$n^{th}$$$ operation, a becomes equal to b then if we follow the pattern after every operation we get the following equation $$$a$$$ $$$+$$$ $$$n(n+1)$$$ $$$=$$$ $$$b$$$. If we solve the following equation for n, we get two values for $$$n$$$ one positive and one negative. But as $$$n$$$ cannot be negative, we choose the positive value. Also n should be an integer (we cannot apply half of an operation), if n is an integer then answer is $$$YES$$$ and the number operation's applied is $$$n$$$. But if $$$n$$$ is not an integer, there is no possible integer value of $$$n$$$ for which $$$a$$$ $$$=$$$ $$$b$$$ and the answer is $$$NO$$$.
If a is odd, then first we have to apply the second operation which adds $$$2i-1$$$ (an odd number) to $$$a$$$ making $$$a$$$ an even number. After this operation we can only apply the first operation on $$$a$$$ because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. Let us assume that after the $$$n^{th}$$$ operation, a becomes equal to b then if we follow the pattern after every operation we get the following equation $$$a$$$ $$$+$$$ $$$n(n+1)$$$ $$$-$$$ $$$1$$$ $$$=$$$ $$$b$$$. If we solve the following equation for n, we get two values for $$$n$$$ one positive and one negative. But as $$$n$$$ cannot be negative, we choose the positive value. Also n should be an integer (we cannot apply half of an operation), if n is an integer then answer is $$$YES$$$ and the number operation's applied is $$$n$$$. But if $$$n$$$ is not an integer, there is no possible integer value of $$$n$$$ for which $$$a$$$ $$$=$$$ $$$b$$$ and the answer is $$$NO$$$.
Overall Complexity : $$$O(logn)$$$ (complexity of sqrt() function) for each testcase
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
int main() {
ll t ;
cin >> t ;
while (t--)
{
ll a , b ;
cin >> a >> b ;
if(a > b)
{
cout << "NO" ;
}
else if(a == b)
{
cout << "YES" << endl ;
cout << 0 ;
}
else
{
ll x = b - a ;
if(a%2 == 0)
{
ll n = (sqrt(4*x + 1) - 1)/2 ;
if(n*(n+1) == x)
{
cout << "YES" << endl ;
cout << n ;
}
else
{
cout << "NO" ;
}
}
else
{
ll n = (sqrt(4*x + 5) - 1)/2 ;
if(n*(n+1) == x + 1)
{
cout << "YES" << endl ;
cout << n ;
}
else
{
cout << "NO" ;
}
}
}
cout << endl ;
}
return 0;
}
from math import sqrt
for _ in range(int(input())):
a, b = map(int, input().split())
if(a > b):
print("NO")
elif (a == b):
print("YES")
print(0)
elif (a % 2 == 0):
n = int(((sqrt(4*(b-a) + 1) - 1)/2))
if(n*(n+1) == b - a):
print("YES")
print(n)
else:
print("NO")
else:
a -= 1
n = int(((sqrt(4*(b-a) + 1) - 1)/2))
if(n*(n+1) == b - a):
print("YES")
print(n)
else:
print("NO")
Problem — E : XOR Hate
Frequencies of all the elements in the array are enough to solve the problem.
For a subsequence of equal elements to have $$$XOR$$$ equal to $$$0$$$, the length of the subsequence should be even. So, the number of even length subsequences has to be calculated for all distinct numbers.
Number of even length subsequences from $$$n$$$ elements $$$=$$$ $$$2^{(n-1)}$$$.
Consider the edge case ($$$a_{i}$$$ $$$=$$$ $$$0$$$) and integer overflows.
Prerequisites: Properties of $$$XOR$$$, Maps.
For the $$$XOR$$$ of all the numbers in the subsequence with equal elements to be equal to $$$0$$$, it should have an even number of elements because $$$A$$$ XOR $$$A$$$ = $$$0$$$, therefore all the pairs would cancel each other up. But if the subsequence contains $$$0$$$ only, then odd length subsequences would also be feasible. So, the final goal is to calculate the number of even lengthed subsequences for all numbers other than $$$0$$$ and the number of subsequences containing $$$0$$$.
Let $$$n$$$ be the frequency of a non-zero element, then the number of even lengthed subsequences is $$$2^{n-1}$$$ $$$-$$$ $$$1$$$ and if the number of zeroes $$$=$$$ $$$n$$$, then the number of feasible subsequences are $$$2^{n}$$$ $$$-$$$ $$$1$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define yes cout << "YES"
#define no cout << "NO"
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9 + 7;
const ll INF = 1e9;
long long int power(long long int n, long long int b){
long long int ans = 1 ;
for(int i = 0 ; i < b ; i++){
ans = (ans*n)%mod;
}
return ans%mod;
}
void solve(){
ll n ; cin >> n ;
map<ll,ll> m ;
for(int i = 0 ; i < n ; i++){
ll x ; cin >> x ;
m[x]++;
}
ll s = m.size();
ll count = 0 , zeroes = (power(2, m[0])) % mod - 1;
for(auto x : m){
if(x.first == 0){
continue;
}
count += (power(2, x.second-1))%mod - 1;
count %= mod;
}
cout << (count + zeroes%mod)%mod ;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc = 1;
cin >> tc;
while(tc--)
{
cout << setprecision(15) << fixed ;
solve();
cout << endl;
}
}
from collections import defaultdict
def binpow(x, y, p) :
res = 1 # Initialize result
# Update x if it is more
# than or equal to p
x = x % p
if (x == 0) :
return 0
while (y > 0) :
# If y is odd, multiply
# x with result
if ((y & 1) == 1) :
res = (res * x) % p
# y must be even now
y = y >> 1 # y = y/2
x = (x * x) % p
return res
mod97 = 1000000007
for _ in range(int(input())):
# Input
n = int(input())
a = list(map(int, input().split()))
# To Store Frequency
dt = defaultdict(int)
for i in range(n):
dt[a[i]] += 1
ans = 0
for k in dt.keys():
v = dt[k]
if(k == 0):
ans = (ans + binpow(2, v, mod97) - 1)%mod97
else:
ans = (ans + binpow(2, v-1, mod97) - 1)%mod97
print(ans)
Problem — F : Unique Numbers
Carefully see the constraints on $$$t$$$ ($$$1$$$ $$$≤$$$ $$$t$$$ $$$≤$$$ $$$10^5$$$) and $$$n$$$ ($$$1$$$ $$$≤$$$ $$$n$$$ $$$≤$$$ $$$10^5$$$).
You can apply brute force for calculating $$$Unique$$$ $$$Numbers$$$ for each value of $$$n$$$.
The idea behind the solution is to pre-compute the number of $$$Unique$$$ $$$Numbers$$$ for each value of $$$n$$$ as constraints are of order $$$10^5$$$. We maintain a $$$cnt$$$ variable which stores number of $$$Unique$$$ $$$Numbers$$$ till given $$$n$$$. Let us start from $$$n$$$ $$$=$$$ $$$1$$$, it is a $$$Unique$$$ $$$Number$$$ increment $$$cnt$$$ by $$$1$$$ and store this value for $$$n$$$ $$$=$$$ $$$1$$$ which is $$$1$$$. Now for $$$n$$$ $$$=$$$ $$$2$$$, it is a $$$Unique$$$ $$$Number$$$ increment $$$cnt$$$ by $$$1$$$ and store this value for $$$n$$$ $$$=$$$ $$$2$$$ which is $$$2$$$. Now perform this for all values of n till $$$10^5$$$.
Now we can tell the number of $$$Unique$$$ $$$Numbers$$$ for any value of $$$n$$$ till $$$10^5$$$ in $$$O(1)$$$.
Overall Complexity : $$$O(N)$$$
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
int main() {
ll ans[100001] , cnt = 0;
for(ll i = 1 ; i <= 100000 ;i++)
{
set<ll> s ;
ll temp = i , x = 0;
while(temp != 0){
s.insert(temp%10) ;
temp = temp/10 ;
x++ ;
}
if(s.size() == x)
cnt++ ;
ans[i] = cnt ;
}
ll t ;
cin >> t ;
while (t--)
{
ll n ;
cin >> n ;
cout << ans[n] << endl ;
}
return 0;
}
m = 100000 + 1
cnt = [0 for i in range(m)]
def solve():
n = int(input())
print(cnt[n])
cnt[0] = 0
cur = 0
for i in range(1, m):
s = str(i)
uniDigits = set(s)
if(len(uniDigits) == len(s)):
cur += 1
cnt[i] = cur
for _ in range(int(input())):
solve()
Problem — G : Magnificent Numbers
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
int main() {
ll f[10] ;
f[0] = 0 ;
for(ll i = 1 ; i < 10 ; i++){
ll cnt = 9 , x = 9;
for(ll j = 1 ; j < i ; j++){
cnt *= x ;
x-- ;
}
f[i] = cnt + f[i-1] ;
}
ll t ;
cin >> t ;
while (t--)
{
ll n , ans = 0 ;
cin >> n ;
if(n <= 9){
ans = n ;
}
else
{
set<ll> s ;
vector<ll> v ;
ll temp = n ;
while(temp!=0){
v.push_back(temp%10) ;
temp = temp/10 ;
}
reverse(v.begin(),v.end()) ;
ans = f[v.size()-1] ;
for(ll i = 0 ; i < v.size() ; i++){
ll x = v[i] , y = 9 - i ;
if(i == 0)
x-- ;
for(ll j = 0 ; j < i ; j++){
if(v[i] > v[j])
x-- ;
}
for(ll j = 1 ; j < v.size()-i ; j++){
x *= y ;
y-- ;
}
ans += x ;
s.insert(v[i]) ;
if(s.size() != i + 1)
break ;
}
// Checking whether n is Unique Number or not
if(s.size() == v.size()){
ans++ ;
}
}
ll cnt = 0 ;
set<ll> s ;
while(ans != 0){
s.insert(ans%10) ;
cnt++ ;
ans = ans/10 ;
}
if(cnt == s.size())
cout << "YES" ;
else
cout << "NO" ;
cout << endl ;
}
return 0;
}
Problem — H : Moon-Moon Event
Prerequisites: Disjoint Set Union and Segment Tree.
The main observation to make about the problem is that we are asked to answer range query and keep the record of different groups in the rooms. As it is evident from the the problem that we are required to make range query with updates and we already know that min function follows associative property therefore is it optimal to use segment tree. As for maintaining the number of groups in different rooms for that we can use disjoint set union data structure with path compression and rank heuristic for best time and space complexity. We need to maintain different disjoint set union for each room.
#include<bits/stdc++.h>
using namespace std;
const long long INF = (1e18);
class segtree {
private:
// Data Members
long long size;
vector<long long> tree;
// Encapaclation
void set(long long i, long long v, long long x, long long lx, long long rx){
if(rx - lx == 1){
tree[x] = v;
return;
}
long long m = (lx + rx)/2;
if(i < m){
set(i, v, 2*x+1, lx, m);
} else {
set(i, v, 2*x+2, m, rx);
}
tree[x] = min(tree[2*x+1], tree[2*x+2]);
}
long long op(long long l, long long r, long long x, long long lx, long long rx){
if(l >= rx or r <= lx){
return INF;
}
if(l <= lx and rx <= r){
return tree[x];
}
long long m = (lx + rx)/2;
long long s1 = op(l, r, 2*x+1, lx, m);
long long s2 = op(l, r, 2*x+2, m, rx);
return min(s1, s2);
}
public:
// Functions
void init(long long n){
size = 1;
while(size < n) size *= 2;
tree.assign(2*size, INF);
}
void set(long long i, long long v){
set(i, v, 0, 0, size);
}
long long op(long long l, long long r){
return op(l, r, 0, 0, size);
}
};
template<typename T>
class DSU {
public:
std::vector<T> p;
std::vector<T> r;
DSU(size_t n){
p = std::vector<T>(n);
std::iota(p.begin(), p.end(), 0);
r = std::vector<T>(n, 1);
}
T find(T x) {
if(x > p.size()){
cerr << "Error element not in array or vector" << endl;
return LLONG_MIN;
}
T y = x;
while (y != p[y]) {
y = p[y];
}
while (x != p[x]) {
T z = p[x];
p[x] = y;
x = z;
}
return y;
}
void join(T x, T y) {
x = find(x), y = find(y);
if(r[x] > r[y]){
swap(x, y);
}
p[x] = y;
if (r[x] == r[y] and x != y) {
r[y]++;
}
}
};
void solve();
int main(int argc, char const *argv[]){
// For Fast IO
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
// Solution Starts
solve();
return 0;
}
void solve(){
long long n, m; cin >> n >> m;
vector<DSU<long long>> dsu(n, DSU<long long>(m));
segtree st; st.init(n);
for(long long i = 0; i < n; i++){
st.set(i, m);
}
long long q; cin >> q;
while(q--){
long long c; cin >> c;
if(c == 1){
long long sno, x, y;
cin >> sno >> x >> y;
// 0 indexcing
sno--; x--; y--;
// Joining
// O(1)
long long p_x = dsu[sno].find(x), p_y = dsu[sno].find(y);
if(p_x != p_y){
dsu[sno].join(x, y);
long long val = st.op(sno, sno + 1);
val--;
st.set(sno, val);
}
} else {
long long l, r; cin >> l >> r;
// O indexcing
l--; r--;
// Range Query
// O(log(n))
cout << st.op(l, r + 1) << "\n";
}
// set and which people are in same group
// minimum numbers of group in [L, R]
}
}
class DSU(object):
def __init__(self, n):
self.p = [i for i in range(n)]
self.r = [1 for i in range(n)]
def find(self, x):
y = x
while(y != self.p[y]):
y = self.p[y]
while(x != self.p[y]):
z = self.p[x]
self.p[x] = y
x = z
return x
def join(self, x, y):
x, y = self.find(x), self.find(y)
if(self.r[x] > self.r[y]):
x, y = y, x
self.p[x] = y
if(self.r[x] == self.r[y] and x != y):
self.r[y] += 1
INF = float('inf')
class segtree(object):
def __init__(self, n):
self.size = 1
while(self.size < n):
self.size *= 2
# self.size *= 2
self.tree = [INF for i in range(2*self.size)]
def assign(self, i, v):
self.assignf(i, v, 0, 0, self.size)
def assignf(self, i, v, x, lx, rx):
if(rx - lx == 1):
self.tree[x] = v
return
m = (lx + rx) // 2
if(i < m):
self.assignf(i, v, 2*x + 1, lx, m)
else:
self.assignf(i, v, 2*x + 2, m, rx)
self.tree[x] = min(self.tree[2*x + 1], self.tree[2*x + 2])
def query(self, l, r):
return self.queryf(l, r, 0, 0, self.size)
def queryf(self, l, r, x, lx, rx):
if(l >= rx or r <= lx):
return INF
if(l <= lx and rx <= r):
return self.tree[x]
m = (lx + rx) // 2
s1 = self.queryf(l, r, 2*x + 1, lx, m)
s2 = self.queryf(l, r, 2*x + 2, m, rx)
return min(s1, s2)
def solve():
n, m = map(int, input().split())
dsu = [DSU(m) for i in range(n)]
st = segtree(n)
for i in range(n):
st.assign(i, m)
q = int(input())
for _ in range(q):
c = list(map(int, input().split()))
if(c[0] == 1):
sno, x, y = c[1], c[2], c[3]
sno -= 1
x -= 1
y -= 1
p_x, p_y = dsu[sno].find(x), dsu[sno].find(y)
if(p_x != p_y):
dsu[sno].join(x, y)
val = st.query(sno, sno + 1)
val -= 1
st.assign(sno, val)
else:
l, r = c[1], c[2]
print(st.query(l - 1, r))
if __name__=="__main__":
solve()
Standing
Top 5
Rank | Codeforces Handle |
---|---|
1. | vinay272001 |
2. | piyush225 |
3. | vadlamani19100 |
4. | crazy_stardusts |
5. | ciao |