codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1746.md (33541B)


      1 Source: https://codeforces.com/blog/entry/108011
      2 
      3 Hi Codeforces,
      4 
      5 I've tried my best to make a different editorial, I wish you enjoy it ...
      6 
      7 [1746A - Maxmina](/contest/1746/problem/A "Codeforces Global Round 23")
      8 
      9 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
     10 
     11 **step by step solution**
     12 
     13 step 1:
     14 
     15 It's obvious that the answer is "NO" if $a_{i} = 0$ for all $1 \le i \le n$.
     16 
     17 step 2:
     18 
     19 Lets prove that the answer is "YES" if $a_{i} = 1$ for at least one $1 \le i \le n$.
     20 
     21 step 3:
     22 
     23 If size of $a$ is equal to $k$, just use second type operation once and we are done.
     24 
     25 step 4:
     26 
     27 Otherwise (if $|a| \gt k$), there will be three cases: (assume that $a_{j} = 1$)
     28 
     29 * if $j \gt 2$, you can use first type operation on first and second element and decrease size of $a$ by 1.
     30 * else if $j \lt |a|-1$, you can use first type operation on last and second to last element and decrease size of $a$ by 1.
     31 * else, it can be shown easily that $|a| = 3$ and $k = 2$ so you can use second type operation twice and turn $a$ into a single $1$.
     32 
     33 In first and second case, you can continue decreasing size of $a$ until $|a| = k$ (or you reach $3$-rd case) and you can use second type operation to reach your aim.
     34 
     35 step 5:
     36 
     37 So we proved that the answer is "YES" iff $a_{i} = 1$ for at least one $1 \le i \le n$ or in other words, iff $\sum_{i = 1}^n a_{i} \gt 0$.
     38 
     39 **solution**
     40 
     41 ```
     42 // In the name of God
     43 #include <iostream>
     44  
     45 using namespace std;
     46  
     47 int main()
     48 {
     49     int t;
     50     cin >> t;
     51     while(t--)
     52     {
     53         int n, k;
     54         cin >> n >> k;
     55         int sum = 0;
     56         for(int i = 0 ; i < n ; i++){
     57             int a;
     58             cin >> a;
     59             sum += a;
     60         }
     61         if(sum > 0) cout << "YES" << endl;
     62         else cout << "NO" << endl;
     63     }
     64     return 0;
     65 }
     66 // Thank God
     67 ```
     68 
     69 [1746B - Rebellion](/contest/1746/problem/B "Codeforces Global Round 23")
     70 
     71 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh")
     72 
     73 **step by step solution**
     74 
     75 step 1:
     76 
     77 **task**
     78 
     79 Assume that $a_{i} = 0$ for each $1 \le i \le n$, what should we do?
     80 
     81 **solution**
     82 
     83 Nothing! The array is already sorted and the answer is $0$.
     84 
     85 step 2:
     86 
     87 **task**
     88 
     89 After sorting the array, consider the first non-zero element of $a$, how many elements after that are equal to zero? In other words, consider smallest $i$ such that $a_{i} \gt 0$, how many indices $k$ exist such that $i \lt k$ and $a_{k} = 0$?
     90 
     91 **solution**
     92 
     93 0, because we call an array $a$ sorted (in non-decreasing order), if for all $1 \le i \lt j \le n$, $a_{i} \le a_{j}$ holds. So all numbers after leftmost non-zero element must be non-zero too.
     94 
     95 step 3:
     96 
     97 **task**
     98 
     99 assume that after sorting $a$, $a_{i}$ ($1 \le i \le n$) is the leftmost non-zero element. Define $G_{1}$ as the set of indices $j$ such that $1 \le j \lt i$ and $a_{j} \gt 0$ at the beginning, also define $G_{2}$ as the set of indices $j$ such that $i \le j \le n$ and $a_{j} = 0$ at the beginning. What is the answer?
    100 
    101 **solution**
    102 
    103 $max(|G_{1}|, |G_{2}|)$. It's obvious that in one operation at most one element will be deleted from each group. So we must perform at least $max(|G_{1}|, |G_{2}|)$ operations. Now we want to show that it's sufficient too. There are three cases:
    104 
    105 $min(|G_{1}|, |G_{2}|) \gt 1$, at this point, we know that all elements of $a$ are $0$ or $1$. So we can pick one element from $G_{1}$ and add it to an element from $G_{2}$, so the size of both groups will decrease by $1$. It's obvious that all elements of $a$ will remain less than or equal to $1$ after this operation.
    106 
    107 $|G_{1}| = 0$, it's easy to see that we can add $a[k]$ ($k \in G_{2}$) to a random element. So $|G_{2}|$ will decrease by $1$.
    108 
    109 $|G_{2}| = 0$, it's easy to see that we can add $a[k]$ ($k \in G_{1}$) to the last element of $a$. So $|G_{1}|$ will decrease by $1$.
    110 
    111 step 4:
    112 
    113 **task**
    114 
    115 Now how can we solve the problem using previous steps?
    116 
    117 **solution**
    118 
    119 If all elements are equal to $0$, the answer is obviously zero. Otherwise we will calculate two arrays, number of ones in each prefix and number of zeros in each suffix. We will also fix the leftmost non-zero element and calculate the answer for it easily by using Step 3 algorithm in O(n).
    120 
    121 **solution**
    122 
    123 ```
    124 /// In the name of God
    125 #include <iostream>
    126  
    127 using namespace std;
    128  
    129 int main()
    130 {
    131 	int t;
    132 	cin >> t;
    133 	while(t--)
    134 	{
    135 		int n;
    136 		cin >> n;
    137 		int A[n], cnt[2][n+1];
    138 		cnt[0][0] = cnt[1][0] = 0;
    139 		for(int i = 0; i < n; i++)
    140 		{
    141 			cin >> A[i];
    142 			cnt[0][i+1] = cnt[0][i]+(A[i]==0?1:0);
    143 			cnt[1][i+1] = cnt[1][i]+(A[i]==1?1:0);
    144 		}
    145 		int ans = n-1;
    146 		for(int last_zero = 0; last_zero <= n; last_zero++)
    147 			ans= min(ans, max(cnt[1][last_zero], cnt[0][n]-cnt[0][last_zero]));
    148 		cout << ans << endl;
    149 	}
    150 }
    151  
    152 /// Thank God . . .
    153 ```
    154 
    155 [1746C - Permutation Operations](/contest/1746/problem/C "Codeforces Global Round 23")
    156 
    157 problem author: [napstablook](/profile/napstablook "Candidate Master napstablook")
    158 
    159 **step by step solution**
    160 
    161 step 1:
    162 
    163 **task**
    164 
    165 Try to prove that the answer is always zero. Or in other words, we can always make the array $a$ non-decreasing.
    166 
    167 **solution**
    168 
    169 We will prove this fact in next steps.
    170 
    171 step 2:
    172 
    173 **task**
    174 
    175 If some array $a$ is non-decreasing, what can we say about array $d=[a_{2}-a_{1}, a_{3}-a_{2}, ... a_{n}-a_{n-1}]$?
    176 
    177 **solution**
    178 
    179 It's obvious that all elements of array $d$ should be non-negative.
    180 
    181 step 3:
    182 
    183 **task**
    184 
    185 If we perform the $i$-th operation on the suffix starting at index $j$, what happens to array $d$?
    186 
    187 **solution**
    188 
    189 All elements of it will remain the same except $d_{j-1}=a_{j}-a_{j-1}$ which will increase by $i$.
    190 
    191 step 4:
    192 
    193 **task**
    194 
    195 Considering the fact that array $a$ consists only of positive integers, what can we say about $d_{i}=a_{i+1}-a_{i}$?
    196 
    197 **solution**
    198 
    199 Since $a_{i+1} \ge 0$, we can say that $d_{i} \ge -a_{i}$.
    200 
    201 step 5:
    202 
    203 **task**
    204 
    205 Using step 3 and 4 and knowing that $a$ is a permutation of numbers $1$ to $n$, what can we do to make all elements of $d$ non-negative?
    206 
    207 **solution**
    208 
    209 for $i \le n-1$, we can perform $a_{i}$-th operation on the suffix starting from index $i+1$. So $d_{i}$ will increase by $a_{i}$ and since we knew that $d_{i} \ge -a_{i}$, after performing this operation $d_{i} \ge 0$ will hold. So after this steps, elements of $d$ will be non-negative and according to Step 2, that's exactly what we want. It's also easy to see that it doesn't matter how we perform $a_{n}$-th operation, so we can do anything we want.
    210 
    211 **solution**
    212 
    213 ```
    214 /// In the name of God
    215 #include <bits/stdc++.h>
    216 
    217 using namespace std;
    218 
    219 inline void solve()
    220 {
    221 	int n;
    222 	cin >> n;
    223 	int permutation[n], location[n];
    224 	for(int i = 0; i < n; i++)
    225 	{
    226 		cin >> permutation[i];
    227 		permutation[i]--;
    228 		location[permutation[i]] = i;
    229 	}
    230 	for(int i = 0; i < n; i++)
    231 	{
    232 		if(location[i] == n-1)
    233 			cout << rand()%n+1 << (i == n-1?'\n':' ');
    234 		else
    235 			cout << location[i]+2 << (i == n-1?'\n':' ');
    236 	}
    237 }
    238 
    239 int main()
    240 {
    241 	int t;
    242 	cin >> t;
    243 	while(t--)
    244 		solve();
    245 	return 0;
    246 }
    247 /// Thank God . . .
    248 ```
    249 
    250 [1746D - Paths on the Tree](/contest/1746/problem/D "Codeforces Global Round 23")
    251 
    252 problem author: [AquaMoon](/profile/AquaMoon "International Master AquaMoon"), [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka"), [mejiamejia](/profile/mejiamejia "Expert mejiamejia"), [ChthollyNotaSeniorious](/profile/ChthollyNotaSeniorious "Master ChthollyNotaSeniorious"), [SSerxhs](/profile/SSerxhs "International Grandmaster SSerxhs"), [TomiokapEace](/profile/TomiokapEace "Expert TomiokapEace")
    253 
    254 **single step solution**
    255 
    256 Define $f(u, cnt)$ represents the maximum score of $cnt$ balls passing through the subtree of node $u$.
    257 
    258 Define $num$ as the number of the sons of node $u$. The transition is only related to $\lceil cnt / num \rceil$ and $\lfloor cnt / num \rfloor$ two states of the subtree.
    259 
    260 For each node $u$, $cnt$ can only be two adjacent integer $(x, x + 1)$.
    261 
    262 It can be proved that the four numbers $\lfloor x/num \rfloor$, $\lceil x/num \rceil$, $\lceil (x + 1)/num \rceil$ and $\lfloor (x + 1)/num \rfloor$ can only have two kinds of numbers at most, and they are adjacent natural numbers.
    263 
    264 So the number of states can be proved to be $\mathcal{O}(n)$.
    265 
    266 **solution**
    267 
    268 ```
    269 /// In the name of God
    270 #include <bits/stdc++.h>
    271 using namespace std;
    272 typedef long long ll;
    273 
    274 const int N = 200000;
    275 ll V[N], dp[N];
    276 int dad[N];
    277 vector<int> child[N];
    278 vector<pair<int, ll>> answers[N];
    279 
    280 inline ll DP(int v, ll k)
    281 {
    282 	for(auto [kp, ans]: answers[v])
    283 		if(k == kp)
    284 			return ans;
    285 	ll cnt_child = (ll)child[v].size();
    286 	ll ans = k*V[v];
    287 	if(cnt_child == 0)
    288 		return ans;
    289 	if(k%cnt_child == 0)
    290 		for(auto u: child[v])
    291 			ans += DP(u, k/cnt_child);
    292 	else
    293 	{
    294 		ll dp1[cnt_child], dp2[cnt_child], diff[cnt_child];
    295 		for(int i = 0; i < cnt_child; i++)
    296 			dp1[i] = DP(child[v][i], k/cnt_child), dp2[i] = DP(child[v][i], k/cnt_child+1);
    297 		for(int i = 0; i < cnt_child; i++)
    298 			diff[i] = dp2[i] - dp1[i];
    299 		sort(diff, diff+cnt_child, greater<int>());
    300 		for(int i = 0; i < cnt_child; i++)
    301 			ans += dp1[i];
    302 		for(int i = 0; i < k%cnt_child; i++)
    303 			ans += diff[i];
    304 	}
    305 	answers[v].push_back({k, ans});
    306 	return ans;
    307 }
    308 
    309 inline ll solve()
    310 {
    311 	ll n, k;
    312 	cin >> n >> k;
    313 	for(int i = 0; i < n; i++)
    314 		child[i].clear(), answers[i].clear();
    315 	dad[0] = 0;
    316 	for(int i = 0; i < n-1; i++)
    317 	{
    318 		cin >> dad[i+1];
    319 		dad[i+1]--;
    320 		child[dad[i+1]].push_back(i+1);
    321 	}
    322 	for(int i = 0; i < n; i++)
    323 		cin >> V[i];
    324 	return DP(0, k);
    325 }
    326 
    327 int main()
    328 {
    329 	int t;
    330 	cin >> t;
    331 	while(t--)
    332 		cout << solve() << '\n';
    333 	return 0;
    334 }
    335 /// Thank God . . .
    336 ```
    337 
    338 [1746E1 - Joking (Easy Version)](/contest/1746/problem/E1 "Codeforces Global Round 23")
    339 
    340 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh")
    341 
    342 **step by step solution**
    343 
    344 step 1:
    345 
    346 **task**
    347 
    348 How can we make sure that some statement is not joking?
    349 
    350 **solution**
    351 
    352 If something is told for two times in a row, we can be sure that it's true. For example if we are told that $x \ne 3$ in two consecutive questions, we can be sure that it's true. Because at least one of those questions is answered correctly and that's enough.
    353 
    354 step 2:
    355 
    356 **task**
    357 
    358 What can be found out if we ask about a set $S$? (assume that we will be answered correctly)
    359 
    360 **solution**
    361 
    362 If the answer is "YES", then $x \in S$ and we can reduce our search domain to $S$. Otherwise, we can remove $S$ from the search domain.
    363 
    364 step 3:
    365 
    366 **task**
    367 
    368 Using previous steps, how can we really reduce our search domain? Step 2 can do it only if we have a correct statement about $x$ and using Step 1, we can find something that is surely correct.
    369 
    370 **solution**
    371 
    372 Assume that $V$ is our current search domain. Split it into $4$ subsets $V_{1}, V_{2}, V_{3}$ and $V_{4}$. then ask about following sets:
    373 
    374 * $V_{1} \cup V_{2}$
    375 * $V_{1} \cup V_{3}$
    376 
    377 It's easy to show that no matter what the answers are, we can always remove at least one of the subsets from the search domain. For example if both answers are "YES", we can remove $V_{4}$ and if both answers are "NO", then we can remove $V_{1}$.
    378 
    379 So after these questions, we can reduce size of search domain by at least $min(|V_{1}|,|V_{2}|,|V_{3}|,|V_{4}|)$, and it's obvious to see that we can choose $V_{i}$'s in such a way that this value is at least $\frac{|V|}{4}$.
    380 
    381 Finally, as long as size of the search domain is greater than $3$, we can reduce it using this algorithm. It can be shown easily that we can reduce our search domain to only $3$ numbers with at most $76$ questions.
    382 
    383 step 4:
    384 
    385 **task**
    386 
    387 Now assume that we have only $3$ candidates for $x$, since we have only $2$ chances to guess, we must remove one of them. How can we do it? Note that since we've used $76$ questions in previous step, we only have $6$ questions left.
    388 
    389 **solution**
    390 
    391 Assume that our three candidates are $a, b$ and $c$. it can be shown that using following questions, we can always remove at least one of them from the search domain:
    392 
    393 * ${a}$
    394 * ${b}$
    395 * ${b}$
    396 * ${a}$
    397 
    398 After that, when we have only two candidates for $x$, we can guess them one by one and we are done.
    399 
    400 **solution**
    401 
    402 ```
    403 /// In the name of God
    404 #pragma GCC optimize("Ofast","unroll-loops","O3")
    405 #include <bits/stdc++.h>
    406 
    407 using namespace std;
    408 
    409 inline bool get_answer(){string s; cin >> s; return s == "YES";}
    410 
    411 inline bool f(int i){return i&1;}
    412 inline bool g(int i){return i&2;}
    413 
    414 void solve(const vector<int> &Valid)
    415 {
    416     if(Valid.size() < 3u)
    417 	{
    418 	    cout << "! " << Valid[0] << endl;
    419 		string s;
    420 		cin >> s;
    421 		if(s == ":)")return;
    422 		cout << "! " << Valid[1] << endl;
    423 		return;
    424 	}
    425 	else if(Valid.size() == 3u)
    426 	{
    427 		bool is[4];
    428 		cout << "? 1 " << Valid[0] << endl;is[0] = get_answer();
    429 		cout << "? 1 " << Valid[1] << endl;is[1] = get_answer();
    430 		cout << "? 1 " << Valid[1] << endl;is[2] = get_answer();
    431 		cout << "? 1 " << Valid[0] << endl;is[3] = get_answer();
    432 		if(is[1] and is[2])return solve({Valid[1]});
    433 		else if(!is[1] and !is[2])return solve({Valid[0], Valid[2]});
    434 		else if((is[0] and is[1]) or (is[2] and is[3]))return solve({Valid[0], Valid[1]});
    435 		else if((is[0] and !is[1]) or (!is[2] and is[3]))return solve({Valid[0], Valid[2]});
    436 		else return solve({Valid[1], Valid[2]});
    437 	}
    438 	else
    439 	{
    440 		vector<int> query[2];
    441 		for(int i = 0; i < (int)Valid.size(); i++)
    442 		{
    443 			if(f(i))query[0].push_back(Valid[i]);
    444 			if(g(i))query[1].push_back(Valid[i]);
    445 		}
    446 		bool is[2];
    447 		for(int i = 0; i < 2; i++)
    448 		{
    449 			cout << "? " << query[i].size();
    450 			for(auto u: query[i])cout << ' ' << u;
    451 			cout << endl;
    452 			is[i] = get_answer();
    453 		}
    454 		vector<int> NewValid;
    455 		for(int i = 0; i < (int)Valid.size(); i++)
    456 		{
    457 			if((!f(i) ^ is[0]) or (!g(i) ^ is[1]))NewValid.push_back(Valid[i]);
    458 		}
    459 		return solve(NewValid);
    460 	}
    461 }
    462 int main()
    463 {
    464 	int n = 0;
    465 	cin >> n;
    466 	vector<int> all(n);
    467 	for(int i = 0; i < n; i++)all[i] = i+1;
    468 	solve(all);
    469 	return 0;
    470 }
    471 /// Thank God . . .
    472 ```
    473 
    474 [1746E2 - Joking (Hard Version)](/contest/1746/problem/E2 "Codeforces Global Round 23")
    475 
    476 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
    477 
    478 **step by step solution**
    479 
    480 step 1:
    481 
    482 First note that in any question we ask, a set will be introduced as the set that contains $x$. If the answer is "YES", then the set that we asked is introduced and otherwise, its complement.
    483 
    484 **task**
    485 
    486 Assume that our current search domain is some set $V$. In addition, assume that $V = A \cup B$ such that set $A$ is the set that introduced to contain $x$ in very last step and $B$ is the set of other candidates for $x$ (candidates that don't belong to $A$). Now assume that in next question, a set $C$ is introduced to contain $x$ such that $C = a \cup b, (a \in A , b \in B)$. what can we do? how can we reduce our search domain after this question?
    487 
    488 **solution**
    489 
    490 Considering the solution of E1, it's not so hard to see that we can remove $B-b$ from our search domain. So our new search domain will be $V' = A' \cup B'$ such that $A' = C = a \cup b$ is the set of candidates that introduced in last question and $B' = A - a$ is the set of other candidates.
    491 
    492 step 2:
    493 
    494 **task**
    495 
    496 Let's calculate minimum needed questions for a search domain of size $n$ using the idea of previous step.
    497 
    498 **solution**
    499 
    500 We can do it using a simple dp, let $dp[A][B]$ be the minimum number of questions needed to find $x$ in a search domain of size $A+B$ in which $A$ numbers are introduced in last question and $B$ numbers are not. In order to calculate our dp, if we ask about some set which consists of $a$ numbers from first set and $b$ numbers from second set, we should update $dp[A][B]$ from $dp[A-a][a+b]$. So we can say that:
    501 
    502 $dp[A][B] = \min_{a \le A , b \le B} dp[A-a][a+b]$
    503 
    504 . Using this dp and keeping track of its updates, we can simply solve the task. But there is a problem, we don't have enough time to calculate the whole dp. So what can we do?
    505 
    506 step 3:
    507 
    508 **task**
    509 
    510 Since calculating $dp[A][B]$ for $A \lt = n , B \lt = m$ is $O(n^2 \cdot m^2)$, we can only calculate it for small $n$ and $m$ like $n,m \le 100$. What can we do for the rest? Maybe some heuristic method?
    511 
    512 **solution**
    513 
    514 It's not so hard to see that for most $A$ and $B$ (especially for large values) it's best to update $dp[A][B]$ from something around $dp[A-A/2][A/2+B/2]$ (in other words, asking $A/2$ numbers from the first set and $B/2$ numbers from the second one). Using such method, we can calculate dp in a reasonable time and with a very good accuracy, and this accuracy is enough to find the answer in less than $53$ questions.
    515 
    516 **solution**
    517 
    518 ```
    519 /// In the name of God
    520 #pragma GCC optimize("Ofast","unroll-loops","O3")
    521 #include <bits/stdc++.h>
    522  
    523 using namespace std;
    524  
    525 const int SUM = 50;
    526 int dp[SUM][SUM];
    527 pair<int,int> updater[SUM][SUM];
    528 map<pair<int,int>, int> Dp;
    529 map<pair<int,int>, pair<int,int>> Updater;
    530  
    531 inline void preprocess()
    532 {
    533 	for(int i = 0; i < SUM; i++)
    534 	{
    535 		for(int j = 0; j < SUM; j++)
    536 		{
    537 			dp[i][j] = SUM;
    538 			updater[i][j] = {i, j};
    539 		}
    540 	}
    541 	dp[0][0] = dp[0][1] = dp[1][0] = dp[2][0] = dp[1][1] = dp[0][2] = 0;
    542 	for(int sum = 0; sum < SUM; sum ++)for(int last = sum; last >= 0; last--)
    543 	{
    544 		int now = sum - last;
    545 		for(int SelectLast = 0; SelectLast <= last; SelectLast++)for(int SelectNow = 0; SelectNow <= now; SelectNow++)
    546 		{
    547 			if(dp[last][now] > 1 + max(dp[now-SelectNow][SelectNow+SelectLast], dp[SelectNow][sum-SelectNow-SelectLast]))
    548 			{
    549 				dp[last][now] = 1 + max(dp[now-SelectNow][SelectNow+SelectLast], dp[SelectNow][now+last-SelectNow-SelectLast]);
    550 				updater[last][now] = {SelectLast, SelectNow};
    551 			}
    552 		}
    553 	}
    554 }
    555  
    556 inline int DP(const int last, const int now)
    557 {
    558 	if(last < 0 || now < 0)return SUM;
    559 	if(last + now < SUM)return dp[last][now];
    560 	if(Dp.find({last, now}) != Dp.end())return Dp[{last, now}];
    561 	if((last&1) && (now&1))
    562 	{
    563 		Dp[{last, now}] = 1 + DP((now+1)/2, (last+ now)/2);
    564 		Updater[{last, now}] = {(last+1)/2, now/2};
    565 	}
    566 	else
    567 	{
    568 		Dp[{last, now}] = 1 + DP((now+1)/2, (last+1)/2+(now+1)/2);
    569 		Updater[{last, now}] = {(last+1)/2, (now+1)/2};
    570 	}
    571 	return Dp[{last, now}];
    572 }
    573  
    574 inline bool IsIn(const int x, const vector<int> &Sorted)
    575 {
    576 	auto u = lower_bound(Sorted.begin(), Sorted.end(), x);
    577 	if(u == Sorted.end() or *u != x)return false;
    578 	return true;
    579 }
    580  
    581 vector<int> solve(const vector<int> &LastAns, const vector<int> &Valid)
    582 {
    583 	if((int)Valid.size() < 3)
    584 	{
    585 		return Valid;
    586 	}
    587 	pair<int,int> Select;
    588 	if((int)Valid.size() < SUM)
    589 	{
    590 		Select = updater[LastAns.size()][Valid.size()-LastAns.size()];
    591 	}
    592 	else
    593 	{
    594 		DP((int)LastAns.size(), (int)(Valid.size()-LastAns.size()));
    595 		Select = Updater[{LastAns.size(), Valid.size()-LastAns.size()}];
    596 	}
    597 	vector<int> query;
    598 	int p = 0;
    599 	while(Select.first --)query.push_back(LastAns[p++]);
    600 	p = 0;
    601 	vector<int> LastAnsSorted = LastAns;
    602 	sort(LastAnsSorted.begin(), LastAnsSorted.end());
    603 	while(Select.second --)
    604 	{
    605 		while(IsIn(Valid[p], LastAnsSorted)) p++;
    606 		query.push_back(Valid[p++]);
    607 	}
    608 	cout << "? " << query.size();
    609 	for(auto u: query)cout << ' ' << u;
    610 	cout << endl;
    611 	
    612 	string s;
    613 	cin >> s;
    614 	bool correct = (s == "YES");
    615 	sort(query.begin(), query.end());
    616 	vector<int> NewLast, NewValid;
    617 	for(auto u: Valid)
    618 	{
    619 		if(!IsIn(u, LastAnsSorted) and (correct ^ IsIn(u, query)))
    620 		{
    621 			NewLast.push_back(u);
    622 		}
    623 		if(!IsIn(u, LastAnsSorted) or !(correct ^ IsIn(u, query)))
    624 		{
    625 			NewValid.push_back(u);
    626 		}
    627 	}
    628 	vector<int> ans = solve(NewLast, NewValid);
    629 	return ans;
    630 }
    631  
    632 int main()
    633 {
    634 	preprocess();
    635  
    636 	int n;
    637 	cin >> n;
    638 	vector<int> all(n);
    639 	for(int i = 0; i < n; i++)all[i] = i+1;
    640 	vector<int> valid = solve({}, all);
    641 	for(auto guess: valid)
    642 	{
    643 		cout << "! " << guess << endl;
    644 		string s;
    645 		cin >> s;
    646 		if(s == ":)")return 0;
    647 	}
    648 	
    649 	return 0;
    650 }
    651 /// Thank God . . .
    652 ```
    653 
    654 [1746F - Kazaee](/contest/1746/problem/F "Codeforces Global Round 23")
    655 
    656 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh")
    657 
    658 **step by step solution**
    659 
    660 step 1:
    661 
    662 First of all, we can compress $a_{i}$'s and $x$'s (in second type query). so we can assume that all numbers are less than $n+q \le 6 \cdot 10^5$.
    663 
    664 step 2:
    665 
    666 **task**
    667 
    668 Lets first solve the problem for smaller constrains.
    669 
    670 **solution**
    671 
    672 We can use data structures like fenwick tree or segment tree to count the number of occurrences of each number and check if it's divisible by $k$ to answer second type query. And we can simply update our data structure after each query of the first type.
    673 
    674 So if we use something like fenwick tree, we can handle everything in $O((n+q) \cdot n + (n+q) \cdot q \cdot log_{2}(n))$.
    675 
    676 step 3:
    677 
    678 **task**
    679 
    680 Obviously we can not use previous step solution for original constrains. In other words, we don't have enough time to check all numbers one by one. How can we do better? Checking them together?!
    681 
    682 **solution**
    683 
    684 It's obviously not a good idea to check all numbers together (checking that sum of their occurrences is divisible by $k$). So what can we do? What if we check a random subset of numbers?
    685 
    686 step 4:
    687 
    688 **task**
    689 
    690 Assume that $S$ is a random subset of all numbers, it's obvious that if the answer of the query is "YES" (number of occurrences of every number is divisible by $k$), the condition holds for $S$ too (sum of number of occurrences of numbers that belong to $S$ is divisible by $k$). What about the opposite? What is the probability that the answer of the query is "NO" and yet sum of occurrences of numbers belonging to $S$ is divisible by $k$?
    691 
    692 **solution**
    693 
    694 It's not so hard to prove that the probability is equal to $\frac{1}{2}$ for $k = 2$ and it's less than $\frac{1}{2}$ for $k \ge 2$. So in general, the probability that a random subset $S$ leads to a wrong answer is less than or equal to $\frac{1}{2}$. So if we use something like $30$ random subsets, the probability will be less than $\frac{1}{2^{30}}$ which is reasonable for problem constrains and we can use this random method to solve the task.
    695 
    696 **solution**
    697 
    698 ```
    699 #include <bits/stdc++.h>
    700  
    701 using namespace std;
    702  
    703 typedef long long int ll;
    704  
    705 mt19937 rnd(time(0));
    706  
    707 const int N = 300'000 + 5; 
    708 const int Q = 300'000 + 5; 
    709 const int T = 50;
    710 bitset<N+Q> RandomSet[T];
    711 unordered_map<int, int> id; int cnt_id = 0;
    712 int n, q, A[N];
    713  
    714 struct fenwick
    715 {
    716 	int PartialSum[N];
    717 	fenwick()
    718 	{
    719 		for(int i = 0; i < N; i++)PartialSum[i] = 0;
    720 	}
    721 	inline void add(int index, bool increase)
    722 	{
    723 		while(index < N)
    724 		{
    725 			PartialSum[index] += (increase? 1 : -1);
    726 			index += index&-index;
    727 		}
    728 	}
    729 	inline int get(int index)
    730 	{
    731 		int sum = 0;
    732 		while(index)
    733 		{
    734 			sum += PartialSum[index];
    735 			index -= index&-index;
    736 		}
    737 		return sum;
    738 	}
    739 }Fen[T];
    740  
    741 inline int GetId(const int x)
    742 {
    743 	auto id_iterator = id.find(x);
    744 	if(id_iterator == id.end())
    745 	{
    746 		return id[x] = cnt_id++;
    747 	}
    748 	else return (*id_iterator).second;
    749 }
    750  
    751 inline void ChooseRandomSets()
    752 {
    753 	for(int i = 0; i < T; i++)
    754 	{
    755 		for(int j = 0; j < N+Q; j++)
    756 		{
    757 			if(rnd()&1)RandomSet[i].set(j);
    758 		}
    759 	}
    760 }
    761  
    762 inline void AddArrayToFenwick()
    763 {
    764 	for(int i = 0; i < n; i++)
    765 	{
    766 		int MyId = GetId(A[i]);
    767 		for(int j = 0; j < T; j++)
    768 		{
    769 			if(RandomSet[j][MyId])Fen[j].add(i+1, true);
    770 		}
    771 	}
    772 }
    773 	
    774 inline void Query()
    775 {
    776 	int index, l, r, k, x, type;
    777 	for(int i = 0; i < q; i++)
    778 	{
    779 		cin >> type;
    780 		if(type == 1)
    781 		{
    782 			cin >> index >> x;
    783 			index --;
    784 			int IdPre = GetId(A[index]);
    785 			int IdNew = GetId(x);
    786 			A[index] = x;
    787 			for(int j = 0; j < T; j++)
    788 			{
    789 				if(RandomSet[j][IdPre])Fen[j].add(index+1, false);
    790 				if(RandomSet[j][IdNew])Fen[j].add(index+1, true);
    791 			}
    792 		}
    793 		if(type == 2)
    794 		{
    795 			cin >> l >> r >> k;
    796 			l--;
    797 			if(k == 1){cout << "YES\n"; continue;}
    798 			else if((r-l)%k != 0){cout << "NO\n"; continue;}
    799 			bool answer = true;
    800 			for(int j = 0; j < T; j++)
    801 			{
    802 				if((Fen[j].get(r)-Fen[j].get(l))%k != 0){answer = false; break;}
    803 			}
    804 			cout << (answer?"YES":"NO") << '\n';
    805 		}
    806 	}
    807 }
    808  
    809 int main()
    810 {
    811     ios::sync_with_stdio(false) , cin.tie(0);
    812     ChooseRandomSets();
    813     cin >> n >> q;
    814     for(int i = 0; i < n; i++) cin >> A[i];
    815     AddArrayToFenwick();
    816     Query();
    817     return 0;
    818 }
    819 ```
    820 
    821 [1746G - Olympiad Training](/contest/1746/problem/G "Codeforces Global Round 23")
    822 
    823 problem idea: [SirShokoladina](/profile/SirShokoladina "International Grandmaster SirShokoladina")
    824 
    825 problem development: [SomethingNew](/profile/SomethingNew "Grandmaster SomethingNew"), [pakhomovee](/profile/pakhomovee "Master pakhomovee"), [SirShokoladina](/profile/SirShokoladina "International Grandmaster SirShokoladina")
    826 
    827 **single step solution**
    828 
    829 Consider all subsets of the original set in which tasks can be performed in some order to satisfy the constraints on their completion, and also that the size of each of them does not exceed $a+b+c$. It is easy to show that this set is a weighted matroid. This means that the optimal set of tasks can be found using a greedy algorithm.
    830 
    831 So, we can find a set of tasks with maximum total usefulness, which:
    832 
    833 * satisfies all deadline constraints
    834 * has no more than $a+b+c$ elements
    835 
    836 For the given parameters $(x, y, z)$, we introduce the following transformation:
    837 
    838 * Increase the usefulness of all tasks of the first type by $x$, the second type~--- by $y$, and the third type~--- by $z$.
    839 
    840 Let's assume that the optimal solution after the transformation is described by the triple $[a',b',c']$~--- the number of problems of each type, respectively. We need to get a solution described by the triple $[a,b,c]$. For $[a,b,c] \neq [a',b',c']$, $a+b+c=a'+b'+c'$ holds. Then (without limitation of generality, since there are at least two inequalities among $a\vee a',b\vee b',c\vee c'$) we assume that $a' \gt a,b' \lt b$.
    841 
    842 Consider the following coordinate system on a two-dimensional plane (modulo the addition of $\overrightarrow{(1;1;1)})$:
    843 
    844 ![ ](/predownloaded/43/05/430562ca422dd1b9ba53702ce9da9a4af8b83b2e.jpeg)
    845 
    846 For the coordinates of the point, we take the value $\vec{x}\times x+\vec{y}\times y + \vec{z}\times z$$(\vec{x}+\vec{y}+\vec{z} =\vec{0})$. It is easy to understand that the coordinates of the point $(x; y)$ on the plane are uniquely set by the triple $(x; y; z)$ up to the addition of $\overrightarrow{(1;1;1)} \times k, k \in\mathbb{Z}$
    847 
    848 Let's assume that there are parameters $(x,y,z)$ for which the optimal solution is unique and equal to $[a,b,c]$ (see "But what if..?" to see what needs to be done to the input to make this hold).
    849 
    850 Consider the solution $[a',b',c']$ for the "center" of the current polygon (initially it is a hexagon with infinitely distant coordinates). The "center" is the center of the triangle formed by the middle lines of our polygon.
    851 
    852 On this plane, decreasing $z$ or $y$ does not increase $b'+c'$, therefore, it does not decrease $a'$. Thus, the red area in the picture below does not suit us.
    853 
    854 Increasing $x$ or $z$ does not decrease $a'+c'$, therefore, it does not increase $b'$. Because of this, the blue area in the picture below does not suit us either.
    855 
    856 ![ ](/predownloaded/00/dd/00dd9347e4b71ed2808cd1bfeb0a1e1a2493c5fe.jpeg)
    857 
    858 So, we need to cut off one half-plane along the $z$ axis. It can be shown that the area of the polygon under consideration decreases by a constant time for every 2-3 iterations.
    859 
    860 But what if the number of tasks of the desired color jumps from $a-1$ to $a+1$ at once? This is possible if and only if with the addition of some $x$ we get several pairs of elements of equal weight at the same time. To get rid of this, we can simply add a random number from $0$ to $\frac{1}{3}$ to each weight. The fact that such a change will fix the problem described above and will not change the optimal answer to the original problem remains to the reader as an exercise (the authors have proof).
    861 
    862 After $O(\log C)$ iterations, our algorithm will converge to a point (a triple of real numbers). It remains only to check that the solution found is suitable for us.
    863 
    864 $O(n\log n\log C)$
    865 
    866 **solution**
    867 
    868 ```
    869 #include <bits/stdc++.h>
    870 using namespace std;
    871  
    872 #ifdef SG
    873 	#include <debug.h>
    874 #else
    875 	template<typename T> struct outputer;
    876 	struct outputable {};
    877 	#define PRINT(...)
    878 	#define OUTPUT(...)
    879 	#define show(...)
    880 	#define debug(...)
    881 	#define deepen(...)
    882 	#define timer(...)
    883 	#define fbegin(...)
    884 	#define fend
    885 	#define pbegin(...)
    886 	#define pend
    887 #endif
    888  
    889 #define ARG4(_1,_2,_3,_4,...) _4
    890  
    891 #define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
    892 #define forn2(i,n) forn3 (i, 0, n)
    893 #define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)
    894  
    895 #define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
    896 #define ford2(i,n) ford3 (i, 0, n)
    897 #define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)
    898  
    899 #define ve vector
    900 #define pa pair
    901 #define tu tuple
    902 #define mp make_pair
    903 #define mt make_tuple
    904 #define pb emplace_back
    905 #define fs first
    906 #define sc second
    907 #define all(a) (a).begin(), (a).end()
    908 #define sz(a) ((int)(a).size())
    909  
    910 typedef long double ld;
    911 typedef signed __int128 lll;
    912 typedef unsigned __int128 ulll;
    913 typedef int64_t ll;
    914 typedef uint64_t ull;
    915 typedef uint32_t ui;
    916 typedef uint16_t us;
    917 typedef uint8_t uc;
    918 typedef pa<int, int> pii;
    919 typedef pa<int, ll> pil;
    920 typedef pa<ll, int> pli;
    921 typedef pa<ll, ll> pll;
    922 typedef ve<int> vi;
    923  
    924 template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
    925 template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
    926 template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}
    927  
    928 const int N = 100000;
    929 const int X = 1000000000;
    930 const int T = 3;
    931  
    932 struct Input {
    933 	int n;
    934 	std::array<int, T> k;
    935 	int a[N], t[N], d[N];
    936 	
    937 	bool read() {
    938 		if (!(cin >> n)) {
    939 			return 0;
    940 		}
    941 		forn (i, T) {
    942 			cin >> k[i];
    943 		}
    944 		forn (i, n) {
    945 			cin >> a[i] >> t[i] >> d[i];
    946 			--t[i];
    947 			--d[i];
    948 		}
    949 		return 1;
    950 	}
    951  
    952 	void init(const Input& input) {
    953 		*this = input;
    954 	}
    955 };
    956  
    957 struct Data: Input {
    958 	ll ans;
    959 	
    960 	void write() {
    961 		cout << ans << endl;
    962 	}
    963 };
    964  
    965  
    966 namespace Main {
    967 	const lll P = 2 * N + 1;
    968 	const lll Q = 2 * N + 2;
    969 	const lll R = 2 * N + 3;
    970 	const lll A[3] = {3 * P * Q, 3 * P * R, 3 * Q * R};
    971 	const lll M = 3 * P * Q * R * N;
    972 	const lll inf = (X + 1) * M;
    973  
    974 	struct SNM {
    975 		int rnd = 0;
    976 		int n;
    977 		int pr[N];
    978  
    979 		void init(int cnt) {
    980 			n = cnt;
    981 			forn (i, n) {
    982 				pr[i] = i;
    983 			}
    984 		}
    985  
    986 		int get_p(int v) {
    987 			if (v < 0 || pr[v] == v) {
    988 				return v;
    989 			}
    990 			return pr[v] = get_p(pr[v]);
    991 		}
    992  
    993 		bool add(int v) {
    994 			v = get_p(v);
    995 			if (v == -1) {
    996 				return 0;
    997 			}
    998 			pr[v] = v - 1;
    999 			return 1;
   1000 		}
   1001 	};
   1002 	
   1003 	struct Solution: Data {
   1004 		SNM snm;
   1005  
   1006 		int m;
   1007 		lll b[N], c[N];
   1008 		vi ord[T];
   1009  
   1010 		array<int, T> check(const array<lll, T>& adds) {
   1011 			forn (i, n) {
   1012 				c[i] = b[i] + adds[t[i]];
   1013 			}
   1014 			auto cmp = [&](int lhs, int rhs) {
   1015 				return c[lhs] > c[rhs];
   1016 			};
   1017 			static vi q;
   1018 			q.clear();
   1019 			forn (i, T) {
   1020 				static vi w;
   1021 				w.resize(sz(q) + sz(ord[i]));
   1022 				merge(all(q), all(ord[i]), w.begin(), cmp);
   1023 				q.swap(w);
   1024 			}
   1025  
   1026 			snm.init(n);
   1027 			array<int, T> cnt{};
   1028 			int tot = 0;
   1029 			ll val = 0;
   1030 			for (int i : q) {
   1031 				if (tot >= m) {
   1032 					break;
   1033 				}
   1034 				if (snm.add(d[i])) {
   1035 					cnt[t[i]]++;
   1036 					tot++;
   1037 					val += a[i];
   1038 				}
   1039 			}
   1040 			if (cnt == k) {
   1041 				ans = val;
   1042 			}
   1043 			return cnt;
   1044 		}
   1045  
   1046 		// x[i] == adds[(i + 1) % T] - adds[i]
   1047  
   1048 		array<lll, T> get_middle_point(const array<lll, T>& lb, const array<lll, T>& rb) {
   1049 			array<lll, T> x;
   1050 			forn (i, T) {
   1051 				x[i] = lb[i] + rb[i];
   1052 			}
   1053 			lll sum = accumulate(all(x), lll(0));
   1054 			forn (i, T) {
   1055 				x[i] = T * x[i] - sum;
   1056 				if (x[i] >= 0) {
   1057 					x[i] /= (2 * T);
   1058 				} else {
   1059 					x[i] = (x[i] - 2 * T + 1) / (2 * T);
   1060 				}
   1061 			}
   1062 			sum = accumulate(all(x), lll(0));
   1063 			forn (i, T) {
   1064 				if (sum < 0 && x[i] < rb[i]) {
   1065 					x[i]++;
   1066 					sum++;
   1067 				}
   1068 				assert(x[i] >= lb[i]);
   1069 				assert(x[i] <= rb[i]);
   1070 			}
   1071 			assert(sum == 0);
   1072 			return x;
   1073 		}
   1074  
   1075 		bool search() {
   1076 			array<lll, T> lb, rb;
   1077 			forn (i, T) {
   1078 				lb[i] = -2 * inf;
   1079 				rb[i] = 2 * inf;
   1080 			}
   1081  
   1082 			while (true) {
   1083 				{
   1084 					lll sum_l = accumulate(all(lb), lll(0));
   1085 					lll sum_r = accumulate(all(rb), lll(0));
   1086 					forn (i, T) {
   1087 						lll sol = sum_l - lb[i];
   1088 						lll sor = sum_r - rb[i];
   1089 						umx(lb[i], -sor);
   1090 						umn(rb[i], -sol);
   1091 						if (lb[i] > rb[i]) {
   1092 							return 0;
   1093 						}
   1094 					}
   1095 				}
   1096 				array<lll, T> x = get_middle_point(lb, rb);
   1097 				array<lll, T> adds{};
   1098 				forn (i, T - 1) {
   1099 					adds[i + 1] = adds[i] + x[i];
   1100 				}
   1101 				array<int, T> cnt = check(adds);
   1102 				assert(accumulate(all(cnt), 0) == m);
   1103 				if (cnt == k) {
   1104 					return 1;
   1105 				}
   1106 				forn (i, T) {
   1107 					lll d1 = cnt[i] - k[i];
   1108 					lll d2 = cnt[(i + 1) % T] - k[(i + 1) % T];
   1109 					if (d1 > 0 && d2 < 0) {
   1110 						lb[i] = x[i] + 1;
   1111 					}
   1112 					if (d1 < 0 && d2 > 0) {
   1113 						rb[i] = x[i] - 1;
   1114 					}
   1115 				}
   1116 			}
   1117 		}
   1118 		
   1119 		void solve() {
   1120 			forn (i, n) {
   1121 				b[i] = a[i] * M + i * A[t[i]];
   1122 			}
   1123 			forn (i, n) {
   1124 				ord[t[i]].pb(i);
   1125 			}
   1126 			forn (i, T) {
   1127 				sort(all(ord[i]), [&](int lhs, int rhs) {
   1128 					return b[lhs] > b[rhs];
   1129 				});
   1130 			}
   1131 			m = accumulate(all(k), 0);
   1132  
   1133 			{
   1134 				array<int, T> r = check({});
   1135 				if (accumulate(all(r), 0) != m) {
   1136 					ans = -1;
   1137 					return;
   1138 				}
   1139 			}
   1140 			forn (i, T) {
   1141 				array<lll, T> adds{};
   1142 				adds[i] = inf;
   1143 				if (check(adds)[i] < k[i]) {
   1144 					ans = -1;
   1145 					return;
   1146 				}
   1147 				adds[i] = -inf;
   1148 				if (check(adds)[i] > k[i]) {
   1149 					ans = -1;
   1150 					return;
   1151 				}
   1152 			}
   1153 			assert(search());
   1154 		}
   1155 		
   1156 		void clear() {
   1157 			forn (i, T) {
   1158 				ord[i].clear();
   1159 			}
   1160 		}
   1161 	};
   1162 }
   1163  
   1164  
   1165 Main::Solution sol;
   1166  
   1167 int main() {
   1168 	#ifdef SG
   1169 		freopen((problemname + ".in").c_str(), "r", stdin);
   1170 //		freopen((problemname + ".out").c_str(), "w", stdout);
   1171 	#endif
   1172 	
   1173 	int t;
   1174 	cin >> t;
   1175 	forn (i, t) {
   1176 		sol.read();
   1177 		sol.solve();
   1178 		sol.write();
   1179 		sol.clear();
   1180 	}
   1181 	
   1182 	return 0;
   1183 }
   1184 ```