During his last MindCoding Round, Bob encountered the following problem:
Given an empty set, implement a data structure that supports the following operations:
- insert(val) - adds val to the set; if it already exists, nothing is done.
- erase(val) - removes val from the set; if it doesn't exist, nothing is done.
- find(val) - prints YES if val is in the set, NO otherwise.
Input
The first line of input contains N, the number of queries.
The following N lines contain two integers each: type and val, where type can be 1, 2 or 3.Output
The output should contain the result of each type 3 operation, on different lines.
Constraints
- 1 < N ≤ 100
- 0 ≤ val ≤ 1018
Bob knows his hash tables rather well, so he came up with this solution quickly:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const long long MOD1 = ???; 5 const long long MOD2 = ???; 6 7 int N; 8 long long type, val; 9 map <pair <long long, long long>, bool> M; 10 11 int main() { 12 cin>>N; 13 14 while(N--) { 15 cin>>type>>val; 16 17 auto hash = make_pair(val % MOD1, val % MOD2); 18 19 if(type == 1) 20 M[hash] = true; 21 if(type == 2) 22 M[hash] = false; 23 24 if(type == 3) { 25 if(M.find(hash) == M.end() || (M.find(hash) != M.end() && !M[hash])) 26 cout<<"NO\n"; 27 else 28 cout<<"YES\n"; 29 } 30 } 31 32 return 0; 33 }
To his suprise, this solution failed pretests. Bob even tried to tinker with the values of MOD1 and MOD2, hoping that was the cause of his failure. Now he insists that his solution is correct, and the pretests are flawed. As his friend, you offer to generate a testcase that proves his solution is wrong, before he starts threatening Comisia.
Input
Two space separated values: the values of MOD1 and MOD2 that Bob used.
Output
A valid testcase for the given problem, on which Bob's output is incorrect.
Constraints
- 1 ≤ MOD1, MOD2 ≤ 106
Sample
Input | Output | Correct answer | Bob's answer | Explanation |
---|---|---|---|---|
2 4 | 3 1 20 1 17 3 4 | NO | YES | After the first two operations, the set contains values 17 and 20. The third operation searches for 4, which is not in the set. However, Bob's solution outputs YES. |
The problem reduces to finding two values A and B such that:
- A % MOD1 = B % MOD1
- A % MOD2 = B % MOD2
Any such pair constitutes a collision for the hash function. An appropriate testcase can then be generated as follows: 2
1 A
3 B
Choosing A and B is not that difficult. A very simple solution is A = 0 and B = any common multiple of MOD1 and MOD2. Any positive constant can be added to these values without losing the collision property.