PROBLEM LINK:
Author: Laksh Chauhan
Tester: Pankaj Sharma
Editorialist: Laksh Chauhan
DIFFICULTY:
MEDIUM
PREREQUISITES:
Bit Manipulation, Bitsets
PROBLEM:
Given a subset S of power set of \{1,2,3,4,5,6,7,8,9,10\}, we need to find a set K \subseteq \{1,2,3,4,5,6,7,8,9,10\} such that
S^\prime = \{F(X, K) \forall X \in S\} is the same as S.
QUICK EXPLANATION:
Each schedule in N weeks represents a 10-bit integer where, if i \in schedule then, {i-1}^{th} bit is set in the
number representing that schedule and F(X,Y) is nothing but an x-or operation on integers. Then, the problem is reduced to:
Given a set S of N integers, find a positive integer k such that S^\prime = \{{i}\oplus{k}\ \forall i \in S\} is the same as S.
EXPLANATION:
To solve this problem, we need to make two crucial observations,
-
F(X, Y) looks a lot similar to an xor operation.
How? Imagine we represent integers by a set of positions where the bit is set. For example: 6_{10} = 110_{2} hence, we represent 6 as \{2,3\}.
So, lets take two numbers 3 and 6, 3\oplus6 = 5 which can be represented as \{1,3\} as 5_{10} = 101_2.
Let us assume X= \{1,2\} as 3_{10} = 11_{2} and Y = \{2,3\} as 6_{10} = 110_2
Then, F(X,Y) = \{1,3\}. - Once we understand that F(X,Y) is pretty much just an xor operation on two binary numbers, the second observation is that each schedule just represents a 10 bit integer.
After these two observations, the problem just boils down to:
Given a set S of N integers, find a positive integer k such that S^\prime = \{{i}\oplus{k}\ \forall i \in S\} is the same as S.
So, to solve the problem, we can just convert our set of schedules into a set of positive integers and find k for that set and then just print out the set bit positions of k.
Now to find k:
Consider the i^{th} least significant bit, if it is set in k and not in s \in S, then it will be set in {s}\oplus{k}.
Now, consider the smallest bit position p such that 2^{p} > s \forall s \in S. So, k cannot have any bit set with a position \geq p. Thus, k < 2^p.
As the constraints on this problem are not too big, we can just verify if any integer from 1 to 2^p satisfies our condition for it to a feasible k. Otherwise, we can print out -1
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
bool check(int k, vector<bool> &present, vector<int> &a, int n){
for(int i = 0; i<n; i++){
if(!present[a[i] ^ k]){
return false;
}
}
return true;
}
void solve(){
int n;
cin >> n;
vector<int> a(n);
vector<bool> present(1025, false);
for(int i = 0; i<n; i++){
int x;
cin >> x;
bitset<11> number;
while(x--){
int setBit;
cin >> setBit;
--setBit;
number.set(setBit);
}
a[i] = (int)number.to_ulong();
present[a[i]] = true;
}
for(int i = 1; i<=1024; i++){
if(check(i, present, a, n)){
vector<int> pos;
for(int p = 0; p<=10; p++){
if(i&(1<<p)){
pos.push_back(p+1);
}
}
cout << pos.size() << "\n";
for(int p: pos){
cout << p << " ";
}
cout << endl;
return;
}
}
cout << "-1\n";
}
int main(){
int tc = 1;
cin >> tc;
while(tc--){
solve();
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}
vector<int> a;
bitset<1024> present;
bool check(int &kset) {
for (int i : a) {
// trace(kset, i, a[kset ^ i]);
if (present[kset ^ i] == 0) return false;
}
return true;
}
void unsetAll() {
present.reset();
return;
}
int getSetBits(int n) {
int ans = 0;
while (n > 0) {
n &= (n - 1);
ans++;
}
return ans;
}
void solve() {
int n, ans;
int x;
unsetAll();
cin >> n;
a = vector<int>(n);
// assert(n >= 1 and n <= 1024);
for (int i = 0; i < n; i++)
{
cin >> x;
// assert(x >= 0 and x <= 10);
int temp = 0;
for (int j = 0; j < x; j++) {
int r;
cin >> r;
// assert(r >= 1 and r <= 10);
r--;
temp |= (1 << r);
}
a[i] = temp;
present[temp] = 1;
}
for (int mask = 1; mask < 1024; mask++) {
if (check(mask)) {
ans = getSetBits(mask);
// trace(ans, mask);
cout << ans << "\n";
for (int i = 0; i < 10; i++)
{
if ((1 << i) & mask) {
cout << i + 1 << " ";
}
}
cout << "\n";
return;
}
}
cout << -1 << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
// assert(t >= 1 && t <= 6000);
while (t--)
solve();
return 0;
}
For doubts, please leave them in the comment section, I’ll address them.