The clock only shows values from 0 to 59 and wraps around (modulo 60). The only thing to be checked here was if the call duration was a multiple of 60 seconds or not.

• If s % 60 == 0 → print "NO"
• Else → print "YES"

#include <bits/stdc++.h>
using namespace std;

//--------code begins here--------

void solve() {
    int s; cin >> s;
    if(s % 60) cout << "YES";
    else cout << "NO";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;

  while (T--) {
    solve();
    cout << endl;
  }
  return 0;
}

Instead of making $$$1$$$, can we make a $$$0$$$?

The example in the problem statement is a misdirection which could lead to greedy ideas. However, the solution is pretty simple : Any number multiplied by $$$0$$$ is $$$0$$$, and we can add a $$$1$$$ to it.

Thus, for $$$n \geq 4$$$, the solution is simply : $$$X * (1 - 1) + 1$$$, which uses exactly $$$3$$$ 1's.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	int tc; cin >> tc;
	while(tc--) {
		int N; cin >> N;
		cout << min(N - 1, 3) << "\n";
	}

	return 0;
}

We solve the problem using 2D binary search.

Vibhaas is at some hidden point $$$(X,Y)$$$ within the range $$$(0,10^9)$$$ We maintain a rectangle that is guaranteed to contain this point. Initially, this rectangle is the entire grid.

At each step, we query the middle point of the current rectangle. Based on the judge’s response, we learn whether Vibhaas lies to the left or right (affecting the x-coordinate) and/or above or below (affecting the y-coordinate).

Using this information:

• We discard half of the range in the x-direction.
• We discard half of the range in the y-direction.

Thus, with every query, the possible search area shrinks significantly in both dimensions.

Since the coordinate range is at most 10^9, and

$$$2^{30} \gt 10^9$$$

after at most $$$30$$$ queries, the rectangle becomes a single point, which must be Vibhaas’s position.

#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#define debug(...) 0x0
#endif

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using ll = long long;

string query(int x, int y) {
    cout << "? " << x << " " << y << endl;
    string res;
    cin >> res;
    return res;
}

void answer(int x, int y) {
    cout << "! " << x << " " << y << endl;
}

void solve() {
    int l_low = 0, l_hi = 1e9;
    int b_low = 0, b_hi = 1e9;
    for(;;) {
        int l_mid = (l_low + l_hi) / 2;
        int b_mid = (b_low + b_hi) / 2;
        string res = query(l_mid, b_mid);
        if (res == "HERE") {
            answer(l_mid, b_mid);
            return;
        }
        if (res.find("LEFT") != string::npos) {
            l_hi = l_mid - 1;
        }
        if (res.find("RIGHT") != string::npos) {
            l_low = l_mid + 1;
        }
        if (res.find("UP") != string::npos) {
            b_low = b_mid + 1;
        }
        if (res.find("DOWN") != string::npos) {
            b_hi = b_mid - 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    while (T--) {
        solve();
        cout << "\n";
    }
    return 0;
}

We are given the expression:

This can be factorized as:

So the problem reduces to:

Count the number of ordered pairs $$$(a, b)$$$ such that $$$(a+1)(b+1)$$$ is a perfect square.

Let:

Then:

$$$x,y∈[2,N+1]$$$

We need to count pairs $$$(x,y)$$$ such that $$$x⋅y$$$ is a perfect square.

For any integer, we can remove all perfect square factors from it.

Example:

$$$12=4⋅3→$$$ reduced form = 3

$$$18=9⋅2→$$$ reduced form = 2

Now observe:

Two numbers x and y will have $$$x⋅y$$$ as a perfect square if and only if their reduced forms are equal.

For every number $$$x∈[2,N+1]$$$

1. compute its reduced form (by removing square factors).
2. Count how many numbers have the same reduced form.
3. If a reduced form appears c times, it contributes $$$c×c$$$ valid ordered pairs.

We precompute answers for all $$$N≤10^5$$$

• Maintain a frequency array freq

• Iterate $$$x=2$$$ to $$$10^5 + 1$$$

  • Compute reduced form of $$$x$$$
  • Increase its count
  • Maintain running answer:

Store answer for each $$$N$$$

Time Complexity:

$$$O(N*logN)$$$

#include <bits/stdc++.h>
using namespace std;

const int mx = 100000;
#define ll long long
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<ll> red(mx + 2);

    for (int i = 1; i <= mx + 1; i++) {
        int x = i;
        for (int j = 2; j * j <= x; j++) {
            while (x % (j * j) == 0) {
                x /= (j * j);
            }
        }
        red[i] = x;
    }

    vector<ll> ans(mx + 1, 0);
    unordered_map<ll, ll> freq;

    ll cur = 0;

    for (int x = 2; x <= mx + 1; x++) {
        int r = red[x];

        cur -= freq[r] * freq[r];
        freq[r]++;
        cur += freq[r] * freq[r];

        ans[x - 1] = cur;
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << ans[n] << endl;
    }

    return 0;
}

What are the "bad" speeds that cause a collision?

They are the factors of $$$\frac{i}{h_i}$$$. How can we quickly mark them as "bad"?

Assume Laavie is moving at a speed $$$s$$$. Let us consider at raindrop which begins at $$$y = h_i$$$ and is located at $$$x = i$$$. Then, if she reaches position $$$x = i$$$ at the times $$$t = h_i, \ 2h_i, \ 3h_i, \ ...$$$, there would be a collision. In other words, speeds which could cause collisions are

Let us create a boolean array of values which are T / F depending on whether a particular speed is allowed or not (we only care about integral speeds, and obviously a speed of $$$N + 1$$$ is the upper bound on our answer).

Now, for the $$$i$$$-th droplet, the speed $$$\frac{i}{h_i}$$$ can be marked as not allowed. We don't care about non-integral speeds, so only integral speeds of the form $$$\frac{i}{kh_i}$$$ are the factors of $$$\frac{i}{h_i}$$$, which are the "bad" speeds to avoid. We need to mark them as disallowed, and after the entire process, we can check our Boolean array for the smallest speed which is a T.

If we perform naive factorization, the time limit would be $$$O(N \sqrt N)$$$ and can TLE. We can either use SPF array for faster factorization, or even better, simply use the fact that $$$N \ + \ N/2 \ + \ N/3 \ + \ N/4 \ + \ ... = O(N \ log \ N)$$$ to mark factors as F if any of their multiples are F. This leads us to a $$$O(N \ log \ N)$$$ clean solve.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	int tc; cin >> tc;
	while(tc--) {
		int n; cin >> n;
		vector<int> ans(n+2, true); ans[0] = false;
		for(int i = 1; i <= n; i++) {
			int h_i; cin >> h_i;
			if(i % h_i == 0) ans[i / h_i] = false;
		}
		for(int i = 1; i < n+2; i++) {
			for(int j = i; j < n+2; j += i) {
				if(!ans[j]) { ans[i] = false; break; }
			}
			if(ans[i]) {
				cout << i << "\n"; break;
			}
		}
	}

	return 0;
}

Instead of counting how many values do not have a particular XOR-sum, we can count how many do have a particular XOR-sum and subtract it from the total number of subarrays (i.e. $$$\frac{N(N+1)}{2}$$$). How can we do that?

We can use prefix XOR array. Now how to handle updates?

Each update is a point update on the prefix XOR array.

Okay, there are a lot of components to this question.

Let us first focus on the main query which requires an answer from us, i.e., count how many non-empty subarrays which do not have an XOR-sum of the form $$$p^e$$$ ($$$e \gt 1$$$).

We can count how many do have a particular XOR-sum and subtract it from the total number of subarrays (i.e. $$$\frac{N(N+1)}{2}$$$).

This can be done by a standard prefix XOR trick. For $$$A[l] \oplus A[l+1] \oplus ... \oplus A[r] = K$$$, we need $$$P[r] \oplus P[l-1] = K$$$, or $$$P[r] = K \oplus P[l-1]$$$, which can be maintained and checked in a prefix XOR hastable (frequency table).

How to handle updates? We only need to keep track of updates on around relevant $$$200$$$ numbers which are of the form $$$p^e$$$ ($$$e \gt 1$$$). Conveniently for us, each update is a point update on the prefix XOR array. So, we can simply maintain the prefix XOR arrays, as well as the prefix XOR hashtable. Then, we simply need to see how each update affects the values of $$$K \oplus P[l-1]$$$ in the hashtable. (i.e., For an XOR-sum of $$$K$$$, we can update the count of the XOR sum with $$$count[K] += freq[new \oplus K] - freq[old \oplus K]$$$.)

Time Complexity: $$$O(C(N+Q))$$$.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	// prime seive till 10^4 (safe limit)
	const int NMAX = 1e4;
	bitset<NMAX/2> bits;
	bits.set();
	vector<int> primes = {2}; // stores primes here
	for (int i = 3; i / 2 < (int)bits.size(); i = 2 * bits._Find_next(i / 2) + 1) {
	    primes.push_back(i);
	    for (auto j = (int64_t) i * i / 2; j < (int)bits.size(); j += i) bits[j] = 0;
	}
	// numbers of form p^e (e > 1)
	int MX = (1 << 20) - 1; // max xor of any subarray
	vector<int> special;
	for(auto p : primes) {
		for(ll val = (ll)p*p; val <= MX; val *= p) {
			special.push_back(val);
		}
	}

	// main code
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for(auto &x : a) cin >> x;

	// pre-process
	vector<int> prefix_xors;
	vector<int> prefix_freq(MX+1);
	vector<ll> cnt(MX+1);

	int pref = 0; prefix_freq[pref]++;
	for(int i = 0; i < n; i++) {
		pref ^= a[i];
		prefix_xors.push_back(pref);
		prefix_freq[pref]++;

		for(auto k : special) {
			cnt[k] += prefix_freq[pref ^ k];
		}
	}

	// answer
	while(q--) {
		int t; cin >> t;
		if(t == 1) {
			int i, x; cin >> i >> x; i--;
			for(auto k : special) cnt[k] -= prefix_freq[prefix_xors[i] ^ k];
			prefix_freq[prefix_xors[i]]--;
			prefix_xors[i] ^= x;
			prefix_freq[prefix_xors[i]]++;
			for(auto k : special) cnt[k] += prefix_freq[prefix_xors[i] ^ k];
		}
		else {
			int p; cin >> p;
			ll ans = (ll)n*(n+1)/2;
			for(ll val = (ll)p*p; val <= MX; val *= p) {
				ans -= cnt[val];
			}
			cout << ans << "\n";
			continue;
		}
	}


	return 0;
}

The center of the 8-structure must have degree >= 4. The 8-structure is formed by the intersection of two cycles at exactly one node. So for each cycle it will have 2 distinct edges connected to it, giving us a total of at least 4. The problem guarantees that exactly one such node is present in the graph. So if there is an 8-structure present that node must be intersection point, let's call it the center.

To form an 8-structure the 4 incident edges must not be bridges. An edge is part of a cycle if and only if removing it doesn't make the graph disconnected. So we can safely ignore all bridges that are incident on the center.

4 incident edges which aren't bridges guarantee an 8-structure. Every node other than the center has a degree <= 3, so they can't be intersection points of two cycles. Thus the cycles formed by the 4 incident edges which aren't bridges have nowhere else to intersect but the center.

1) Find the potential center.
Iterate over all nodes and choose the only one with degree $$$\ge 4$$$.
Time: $$$O(n)$$$

2) Find bridges incident on the center.
Use Tarjan's algorithm to find bridges and count those incident on the center.
Time: $$$O(n + m)$$$

3) Count non-bridge edges incident on the center.
Let deg = degree of the center.
Let bridges = number of bridges incident on the center.
Then non_bridge_edges = deg — bridges.
Time: $$$O(1)$$$

4) Determine result.
If non_bridge_edges >= 4, output YES.
Otherwise, output NO.
Time: $$$O(1)$$$

Time Complexity: $$$O(n + m)$$$
Space Complexity: $$$O(n + m)$$$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

bool solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n);
    while (m--) {
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // Finding the center
    int center = 0;
    for (int i = 0; i < n; i++)
        if (adj[i].size() >= 4) {
            center = i;
            break;
        }

	// Tarjan's algorithm to find bridges
    int center_bridges = 0;
    vector<int> tin(n), low(n);
    vector<bool> viz(n);
    int time = 0;
    auto dfs = [&](auto&& dfs, int curr, int par) -> void {
        viz[curr] = true;
        tin[curr] = low[curr] = time++;
        for (auto x : adj[curr]) {
            if (x == par)
                continue;
            if (viz[x])
                low[curr] = min(low[curr], tin[x]);
            else {
                dfs(dfs, x, curr);
                low[curr] = min(low[curr], low[x]);
                if (low[x] > tin[curr] && curr == center)
                    center_bridges++;
            }
        }
    };
    dfs(dfs, center, center);

	int non_bridge_edges = (int)adj[center].size() - center_bridges;
    return non_bridge_edges >= 4;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        cout << (solve() ? "YES" : "NO");
        cout << "\n";
    }
    return 0;
}

KMP automaton -> Refer this

DP State:

We define a state using three parameters:

1) $$$i$$$ = number of characters placed so far $$$(0 \le i \le N + K)$$$
2) $$$j$$$ = number of characters of $$$S$$$ matched as a subsequence $$$(0 \le j \le N)$$$
3) $$$state$$$ = current prefix match length in KMP $$$(0 \le state \le M)$$$

So $$$dp[i][j][state]$$$ = maximum number of times $$$P$$$ can be completed from this state.

Base case:

At $$$i = N + K$$$:

• If $$$j = N$$$, then $$$dp[N+K][N][state] = 0$$$
• Otherwise, $$$dp[N+K][j][state] = -INF$$$

Transitions:

For each character $$$c \in {a, \dots, z}$$$:

• $$$nextState = aut[state][c]$$$
• If $$$nextState = M$$$, bonus $$$= 1$$$, else $$$0$$$

• If $$$j \lt N$$$ and $$$S[j] = c$$$, then $$$nextJ = j + 1$$$, else $$$nextJ = j$$$

Feasibility check:

Transition:

String construction:

• Start from $$$i = 0$$$, $$$currJ = 0$$$, $$$currState = 0$$$
• Target value = $$$dp[0][0][0]$$$

For each position:

• Try characters $$$c$$$ from 'a' to 'z'
• Compute $$$nextJ$$$, $$$nextState$$$, $$$bonus$$$

Check:

• First valid $$$c$$$ is chosen (lexicographically smallest)
• Append $$$c$$$, update $$$currJ$$$, $$$currState$$$, and continue

#include<bits/stdc++.h>
using namespace std; 
typedef long long int ll; 

int INF = 1000000000;

template<typename T>
struct KMP {
    vector<T> p;
    vector<int> pi;

    KMP() {}

    KMP(const vector<T> &pattern) : p(pattern) {
        pi = LPS(p);
    }

    void patterner(const vector<T> &pattern){
        p = pattern;
        pi = LPS(p);
    }

    vector<int> search(const vector<T> &s){
        int m((int)p.size()), n((int)s.size()), j(0);
        if(!m){
            vector<int> pos;
            return pos;
        }

        if(pi.empty()) pi = LPS(p);
        vector<int> pos;
        for(int i = 0; i < n; i++){
            while(j && s[i] != p[j]) j = pi[j-1];
            if(s[i] == p[j]) j++;
            if(j == m){
                pos.push_back(i-m+1);
                j = pi[j-1];
            }
        }
        return pos;
    }

    vector<vector<int>> automaton(const vector<T> &alphabet){
        int m((int)p.size());
        if(!m){
            vector<vector<int>> empty;
            return empty;
        }

        if(pi.empty()) pi = LPS(p);
        int a((int)alphabet.size());
        vector<vector<int>> nxt(m, vector<int>(a));
        for(int state = 0; state < m; state++){
            for(int k = 0; k < a; k++){
                T c = alphabet[k];
                int cur(state);
                while(cur && p[cur] != c) cur = pi[cur-1];
                if(p[cur] == c) ++cur;
                nxt[state][k] = cur; // may be == m
            }
        }
        return nxt;
    }

    static vector<char> to_vec(const string &s){
        return vector<char>(s.begin(), s.end());
    }

private:
    vector<int> LPS(const vector<T> &v){
        int n((int)v.size());
        vector<int> pi(n);
        for(int i = 1; i < n; i++){
            int j(pi[i-1]);
            while(j && v[i] != v[j]) j = pi[j-1];
            if(v[i] == v[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
};

void solve(){
    string s, p; cin >> s >> p;
    int k; cin >> k;

    int n(s.size()), m(p.size()), tl(n+k);

    KMP<char> kmp(KMP<char>::to_vec(p));
 
    vector<char> alpha(26);
    for(int i = 0; i < 26; i++) alpha[i] = (char)('a' + i);
    
    vector<vector<int>> aut(kmp.automaton(alpha));
    vector<vector<vector<int>>> dp(tl+1, vector<vector<int>>(n+1, vector<int>(m, -INF)));

    for(int i = 0; i < m; i++) dp[tl][n][i] = 0;

    for(int i = tl-1; i >= 0; i--){
        for(int j = 0; j <= n; j++){
            for(int l = 0; l < m; l++){ 
                for(int c = 0; c < 26; c++){
                    int next(aut[l][c]), score((next== m) ? 1 : 0), next_st((next == m) ? kmp.pi[m-1] : next), next_j(j);
 
                    if(j < n && (s[j] - 'a' == c)) next_j++;

                    if((tl-(i+1)) >= (n-next_j)){
                        if(dp[i + 1][next_j][next_st] == -INF) continue;
                        dp[i][j][l] = max(dp[i][j][l], dp[i + 1][next_j][next_st]+score);
                    }
                }
            }
        }
    }

    string ans("");
    int c_j(0), c_st(0);

    for(int i = 0; i < tl; i++){
        for(int c = 0; c < 26; c++){
            int next(aut[c_st][c]), score((next== m) ? 1 : 0), next_st((next == m) ? kmp.pi[m-1] : next), next_j(c_j);

            if((c_j < n) && (s[c_j] - 'a' == c)) next_j++;

            if((tl-(i + 1)) >= (n-next_j)){
                if((dp[i + 1][next_j][next_st] != -INF) && (dp[i][c_j][c_st] == dp[i + 1][next_j][next_st] + score)){ 
                    ans += (char)(c + 'a');
                    c_j = next_j;
                    c_st = next_st;
                    break;
                }
            }
        }
    }

    cout << ans;

}

int main(){
    ios::sync_with_stdio(0); 
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }

    return 0;
}