At the beginning of the year i became expert, hopefully at the end of the year(tomorrow) i will become expert again. Nice problemset. Thanks for fast editorial.

Not sure if anyone else has made this connection yet, but Problem $$$A$$$ looks very similar to Bronze Problem 1 from the 2020 December USACO competition: http://www.usaco.org/index.php?page=viewproblem2&cpid=1059

I solved D using Knapsack DP , I found out that last 2*k elements would be paired . So while pairing them I should try to keep elements with same value in a set , as splitting them will contribute 1 to answer , and not splitting will contribute 0 . I implementated it using Bitset Link
Edit : It got hacked :((

Would anyone be kind enough to explain to me why these 2 submissions don't have the same result for problem e(https://codeforces.net/contest/1618/submission/139338958 https://codeforces.net/contest/1618/submission/139339631)? In the first submission I did a calculation using long long's in a cout statement, and in the second submission I swapped that with a calculation using a temp variable first then printing that variable. Is this something that I should be careful about and why does this happen? Thanks!

Why is the pairing in 1618D - Array and Operations optimal? It seems obvious but I can't find a proof for it.

I solved D using Greedy here is the link https://codeforces.net/contest/1618/submission/139346218

Can someone helps me? In 2nd problem why my code fails the test cases https://codeforces.net/contest/1618/submission/139289954

I tried D with DP I was getting WA for testcase 2. I am not getting where I am going wrong,

Please check my submission and please tell where I am going wrong

Submission Link : My Submission Code

Thanks in advance for helping

Hi, I think I might confuse something. But in the F problem ( Reverse) how can you turn 23 (10111) to 59 (111011) ?

I had solved problem C by taking the LCM of both GCDs and then checking if the array is divisible by the LCM for both the cases and printing the respective GCD, but the code didn't pass the test. Below is the link https://codeforces.net/contest/1618/submission/139321336 I did the same thing but this time I used GCD which passed all the tests. Below is the link — https://codeforces.net/contest/1618/submission/139323889 Can someone explain what is the difference between both the codes and why the LCM one didn't pass the test?

can anyone please explain the intuition behind problem C?

Can anyone explain what is "string(1, char('0' + i))" this line doing ??? Thanks!! This is in editorial of F.

can anyone help me figure out why this program for Problem F terminates ? It passes all the test cases:

#include <algorithm>
#include <cassert>
#include <bitset>
#include <chrono>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits> 
#include <stack>


using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const int MOD = 1e9 + 7;
const ll INF = 1e18;

#define ff                              first
#define ss                              second
#define mp                              make_pair
#define lb                              lower_bound
#define ub                              upper_bound
#define setbits(x)                      __builtin_popcountll(x)
#define sz(x)                           (int)(x).size()
#define all(x)                          (x).begin(), (x).end()
#define rall(x)                         (x).rbegin(), (x).rend()
#define sum(x)                          (accumulate ((x).begin(), (x).end(), 0ll))
#define mine(x)                         (*min_element((x).begin(), (x).end()))
#define maxe(x)                         (*max_element((x).begin(), (x).end()))

inline void fastio() {ios_base::sync_with_stdio(false);cin.tie(NULL);}

template<typename A, typename B>
ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifndef ONLINE_JUDGE
    #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", dbg_out(__VA_ARGS__)
#else
    #define dbg(...)
#endif

mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

// memset   (name, value, sizeof(name))
// replace  (list.begin(), list.end(), value1, value2)
// unique   (list.begin(), list.end())
// remove   (list.begin(), list.end(), value)

// lower_bound(list.begin(), list.end(), value) ->  first element >= value
// upper_bound(list.begin(), list.end(), value) ->  first element > value

ll binrev(ll x) {
    vector<int> bits;
    for(int i = 0; i < 63; i++) {
        if ((1LL << i) & x) {
            bits.push_back(1);
        }
        else {
            bits.push_back(0);
        }
    }
    while(!bits.empty() && bits.back() == 0) {
        bits.pop_back();
    }
    reverse(all(bits));
    ll xp {};
    for(int i = 0; i < sz(bits); i++) {
        if (bits[i]) {
            xp += (1LL << i);
        }
    }
    return xp;
}

map<pair<ll, ll>, bool> m;

bool f(ll x, ll y) {
    if (x == y) return true;
    if (m.find(mp(x, y)) != m.end()) {
        return false;
    }
    m[mp(x, y)] = true;
    // either perform operation 1 or operation 2
    ll x1 = binrev(2 * x);
    ll x2 = binrev(2 * x + 1);
    bool res = f(x1, y) || f(x2, y);
    return res;
}

void solve() {
    ll x, y;
    cin >> x >> y;
    cout << (f(x, y) ? "YES" : "NO") << '\n';
}

int main() {
    fastio();
    #ifdef devansh_local
        auto begin = std::chrono::high_resolution_clock::now();
    #endif


    cout << setprecision(15) << fixed;

    int tc = 1;
    while(tc--) {
        solve();
    }

    #ifdef devansh_local
        auto end = std::chrono::high_resolution_clock::now();
		cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << " ms" << endl;
	#endif

    return 0;
}

Stupid question about Problem C:

I'm trying to understand this line of code:

--> good[i % 2] = good[i % 2] && (a[i] % g[(i % 2) ^ 1] > 0);

Specifically this part:

--> && (a[i] % g[(i % 2) ^ 1] > 0);

What's the purpose of the XOR here?

Same question about this line:

--> ans = max(ans, g[i ^ 1]);

good contest but it need to strong pretest cases in problem d and f finally i realy sorry for every one get wrong answer in d test 25 i put it in hacks , i tried to cover corner case not to hack some one

If possible, add graphs tag to problem F.

In problem G can someone clarify how to use DSU to reach the solution. I understand the creation of graph but am unclear on how to use DSU.

https://codeforces.net/contest/1618/submission/139274778 this my code of E question and I just got msg that my code is significantly match with this code https://codeforces.net/contest/1618/submission/139261121. please can anyone look into this because both codes are not same and I haven't done any unfair mean, you can also look into my profile.

Hey Everyone
Can anybody tell me how 'testcase: 1 576460752303423487' for problem F gives YES
According to me if x = 1.
You can change it to only 111...(any no of times)
but in this testcase, you can change it to 10000..(58 times). But How?

Can Somebody help with problem C my code was giving me TLE but I think its logic is similar to the solution?

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
 
using namespace std;
 
//Global variables
ll t, n, k, m;
const ll template_size = 100002;
//template arrays
// ll a[template_size] = {};
// ll b[template_size] = {};
// ll dp[template_size] = {};
 
 
int main()
{
	//makes the io faster
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	t = 1;
	cin >> t;
	while (t--)
	{
		cin >> n;
		vector<ll> a(n,0);
		ll ge,  go;
		cin >> a[0];
		cin >> a[1];
		ge = a[0];
		go = a[1];
		for (int i{2}; i < n; i++){
			cin >> a[i];
			if (i%2 == 0){
				ge = __gcd(ge, a[i]);
			}
			if (i%2 != 0){
				go = __gcd(go, a[i]);
			}
		}
		// if (ge == go){
		// 	cout << 0 << '\n';
		// 	continue;
		// }
		ll ans{0};
		bool flag1 = true, flag2 = true;
		for(int i{}; i < n; i++){
			if (i%2 == 0){
				flag1 = flag1 & (a[i]%go != 0);
			}
			else {
				flag2 = flag2 & (a[i]%ge != 0);
			}
		}
		
		if (flag2){
			ans = max(ans, ge);
		}
		if (flag1){
			ans = max(ans, go);
		}
		cout << ans << '\n';
	}
 
	return 0;
}

1) In problem G, what is the proof that the rebalancing step in the unite function (i.e. while (*bst[a].begin() < *wst[a].rbegin())) won't take too long in total?

2) In problem D, how to prove that the answer is:

after sorting the array in non-increasing order? (I got AC with it and it seemed very intuitive)

$$$f$$$ is the frequency of the most repeated element in $$$a[1..2k]$$$.

Can someone help me? In problem F, I do not know why my code fails. Thanks a lot.

https://codeforces.net/contest/1618/submission/139439943

what means g[(i % 2) ^ 1] ?

There's an even simpler solution for D. First of all, you greedly add the first n — 2k numbers (after sorting of course), then, for the rest of the numbers, you check how many times each number appears. If there's a number that appears more than k times, then you know that there's no avoiding in adding one to the answer; you simply add the amount it appears — k to the answer.

139271250

Can anyone tell me what is the time complexity of the second solution of problem F?

For E, could you use FFT? I see a system of linear equations, and the resulting matrix is circulant. Hence, you could use a FFT and solve it in nlogn time. It's slower than the accepted solution, however. Still would be interesting to do.

Instead of pairing up the last 2k numbers like described in the tutorial for problem D, is it possible to just run the following O(n^2) algorithm: For each i in the range [n — 2k + 1, n — 1] we will look for the smallest index j such that arr[i] < arr[j] and then set arr[i] and arr[j] to -1 so that they aren't used anymore. And if we can't find any index j that works, just look for the smallest index j such that arr[i] = arr[j]. Then you just increase answer by 1 and once again set arr[i] and arr[j] to be -1. Finally, add the first n — 2k numbers to the answer as described in the tutorial.

My submission implements this algorithm and didn't pass, so I am wondering if there are any edge cases that break my O(n^2) algorithm. Here is my submission, just in case it is needed.

143369978

Here is a very interesting way to do E through solving a system of equations. Firstly, it is very easy to transcribe the problem into a system of equations. For example, when $$$n=3$$$, we have:

$$$1a_1 + 3a_2 + 2a_3 = b_1$$$

$$$2a_2 + 1a_2 + 3a_3 = b_2$$$

$$$3a_1 + 2a_2 + 1a_3 = b_3$$$

I chose to solve the systems using the inverse matrix method. In this method the goal is to calculate the inverse matrix of the system and multiply it by the constant vector ($$$b$$$) to get the solution vector.

Of course, calculating the inverse of our matrix is too computationally expensive, but due to the patterns exhibited on our matrix, the inverse matrix will also show some patterns.

After some experimentation with web tools to calculate some inverse matrices, I came to the conclusion that the inverse matrix for matrices derived from this problem:

• Are composed of one single row that is cyclically shifted to the right to form subsequent rows
• Have only 3 unique cell values, all 3 of which can be represented as fractions with equal denominators
• In the first row, the middle $$$n-2$$$ cells have a numerator of $$$1$$$
• The first element of the first row has a negative numerator
• The last element of the first row has a positive numerator.

Furthermore, each of the 3 unique cell values exhibit a pattern of their own as $$$n$$$ varies:

• The common denominator is the $$$n$$$-th pentagonal pyramidal number.
• The negative numerator follows the sequence $$$0, -2, -5, -9, ...$$$
• The positive numerator follows the sequence $$$2, 4, 7, 11, ...$$$

We now have enough knowledge to generate the inverse matrix of our system of equations very quickly. By taking advantage of the pattern in each row (noted previously), we can calculate the product of our inverse matrix with the constant vector in $$$O(n)$$$ time through a sliding window method.

Here is the final solution: https://codeforces.net/contest/1618/submission/208803182

While this solution is interesting, it's biggest crutch is that my observations for the inverse matrix would have to be correct for all $$$n$$$. I have very little experience in this area so all I could do is hope for the best. I would love to hear some rationales from some people who are more experienced in this area!

Can We Solve Problem D Using Dynamic Programming?