PROBLEM LINKS:
Author and Editorialist: Bhavya Girotra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
PROBLEM:
Given n cities with initially 0 gifts, you can either drop a gift in a house or have to find the magic number for a house. The magic number for the ith house is the xor of the house numbers of first continuous sequence of houses with house number \geq i and having 0 presents.
QUICK EXPLANATION:
We will be using a set of pairs, where each pair denotes a continuous segment of houses with 0 gifts. For queries of type 1, we will be breaking the segments into newer segments and for queries of type 2, we will use set::upper_bound function to find the desired segment whose xor is to be taken.
EXPLANATION:
Subtask 1
Here we will store the count of gifts for each house in an array.
Queries of type 1 can be answered by incrementing the value if the index of the house by 1.
For queries of type 2, we will iterate from the xth house untill we find a house with 0 gifts. Let this house be ith house. Now we can simply iterate i and take xor until we reach the nth house or find a house with non zero gifts.
Queries of type 1 take O(1) time and queries of type 2 take O(n) time, hence the total complexity is O(nq).
Subtask 2
We will solve this subtask by storing all the continuous houses with 0 gifts as a pair in a set. So initially the set will contain the pair [1,n] since all houses have 0 gifts. Suppose there are 10 houses and the gift distribution is [1,2,0,1,0,0,0,0,1,0] then the set would contain the pairs [3,3], [5,8], [10,10].
For queries of type 1, we are required to add a gift to the xth house. It is easy to observe that if this house already has one or more gifts then we don’t need to update the set. If this house has 0 gifts then we will need to break a segment. Consider the array given before, suppose we add a gift to house number 6, then we would need to split the segment [5,8] to 2 segments [5,5] and [7,8]. To find the segment [5,8], we can use set::upper_bound and update the set.
For queries of type 2, first we need to find the first segment with index \geq xth house. This can again be done by using set::upper_bound. Now that we have the required segment, we are supposed to find the xor of all the elements in it and print it. One way to do it is to iterate through all the elements and take xor but this approach would take O(n) time and will time out. Another way to solve it is to use the property of xor of first n natural numbers.
XOR of first n natural numbers is
n, if n%4=0
1, if n%4=1
n+1, if n%4=2
0, if n%4=3
So suppose the valid segment is [n,m], then the magic number is (xor of first n-1 numbers)⊕(xor of first m numbers)
The complexity of this approach is O(q*log(q)) since number of segments in the set in worst case will be q
SOLUTIONS:
Subtask 1
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,q;
cin>>n>>q;
int gifts[n+1]; // store count of gifts in each house
memset(gifts,0,sizeof(gifts)); // initialise the gift array to 0
while(q--)
{
int c,x;
cin>>c>>x;
if(c==1)
{
gifts[x]++;
}
else
{
int idx=x;
while(gifts[idx]) idx++; // find the first house with 0 gifts and index >= x
int ans=0;
while(idx<=n && gifts[idx]==0) // iterate through all the houses with 0 gifts
{
ans=(ans^idx);
idx++;
}
cout<<ans<<endl;
}
}
return 0;
}
Subtask 2
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll val(ll n) // function to compute xor of first n natural numbers
{
if(n%4==0) return n;
if(n%4==1) return 1;
if(n%4==2) return n+1;
return 0;
}
int main()
{
ll n,q;
cin>>n>>q;
set<pair<ll,ll>> s; // set to store all segments containing 0 gifts
s.insert({1,n}); // initially insert segment [1,n] since all houses have 0 gifts
while(q--)
{
ll c,x;
cin>>c>>x;
if(c==1)
{
auto it=s.upper_bound({x,n+1}); // iterator to first valid segment with index > x
if(it==s.begin()) continue; // no changes need to be made
pair<ll,ll> p = *(--it); // this is the segment that involves the xth house
if(p.second==x) // if the segment is of the type [num,x] where num <= x
{
if(p.first==x) // if num = x
{
s.erase(it); // remove this complete segment
}
else
{
s.erase(it); // remove segment [num,x]
s.insert({p.first,x-1}); // insert segment [num,x-1]
}
}
else if(p.second>x) // segment is of the type [num1,num2] where num1 <= y and num2 > y
{
if(p.first==x) // num1 = x
{
s.erase(it);
s.insert({x+1,p.second});
}
else // here we divide the segment [num1,num2] to [num1,x-1] and [x+1,num2]
{
s.erase(it);
s.insert({p.first,x-1});
s.insert({x+1,p.second});
}
}
else
{
// p.second < x therefore no changes need to be made
}
}
else
{
auto it = s.upper_bound({x,n+1});
ll p,q; // variables to store the valid segment [p,q]
if(it==s.begin()) // the valid segment has all index > x
{
p=it->first;
q=it->second;
}
else
{
it--;
if((it->second)<x) // the valid segment has all index > x
{
it++;
p=it->first;
q=it->second;
}
else // the valid segment includes xth house
{
p=x;
q=it->second;
}
}
cout<<(ll)(val(p-1)^val(q))<<endl;
}
}
return 0;
}
If you have any doubts regarding the problem, feel free to ask them in the comments 