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;
}

...

...

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 a degree >= 4. - O(n) 2) Find bridges incident on the center. - Using Tarjan's algorithm to find bridges we can count the number of bridges incident on the center. - O(n + m) 3) Count non bridge edges incident on the center. - We can find this by subtracting the number of bridges from the degree of the center. - O(1) 4) Determine result. - If the number of non bridge edges is >= 4 then the graph has an 8-structure so output YES otherwise output NO. - 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 for understanding how it works

DP STATE

to define a unique state during string construction, we must track three main params: 1. $$$i$$$: The number of characters placed so far in $$$S'$$$ ($$$0 \le i \le N + K$$$) 2. $$$j$$$: The number of characters of the main string $$$S$$$ successfully matched as a subsequence ($$$0 \le j \le N$$$) 3. $$$\text{state}$$$: The current matching prefix length of the pattern $$$P$$$ according to the KMP automaton ($$$0 \le \text{state} \le M$$$)

So, dp[i][j][state] represents the maximum number of times $$$P$$$ can be completed using the remaining characters, given our current position $$$i$$$, main string progress $$$j$$$, and pattern progress $$$\text{state}$$$

Base case :

At $$$i = N + K$$$, the string is complete * If $$$j = N$$$, the entire main string $$$S$$$ was successfully placed. The sequence is valid, and no further pattern can be formed. We initialize: dp[N+K][N][state] = 0 * For all other values of $$$j \lt N$$$, the sequence failed to include $$$S$$$ as a subsequence. This is an invalid configuration. We initialize: dp[N+K][j][state] = -INF

Transitions :

For dp[i][j][state] we iterate through all possible candidate characters $$$c \in {a, \dots, z}$$$

Adding $$$c$$$ moves the KMP automaton to a new state: $$$\text{next_state} = \text{aut}[\text{state}][c]$$$. If $$$\text{next_state} == M$$$, we have completed an occurrence of $$$P$$$ and increase score by 1. Otherwise, the bonus is increase is 0

If we have not finished the main string i.e, ($$$j \lt N$$$) and the char $$$c$$$ matches the next required main string char ($$$S[j] == c$$$), we successfully advance the main string progress: $$$\text{next_j} = j + 1$$$. Otherwise, progress remains unchanged: $$$\text{next_j} = j$$$

we must make sure the path is logically possible. The remaining free spaces in the string after this move will be $$$(N + K) - (i + 1)$$$. The number of main string characters still required is $$$N - \text{next_j}$$$. If the required characters strictly exceed the available slots, this is a dead end. The transition is only evaluated if:

If the constraint is met, we look at the potential of the next state

STRING CONSTRUCTION :

After dp is over, + start from $$$i = 0$$$, $$$\text{curr_j} = 0$$$, and $$$\text{curr_state} = 0$$$. The target optimal score is dp[0][0][0] + At each index $$$i$$$, iterate through character $$$c$$$ strictly from 'a' to 'z' + Calculate $$$\text{next_j}$$$, $$$\text{next_state}$$$, and $$$\text{bonus}$$$ same as the dp + Check if selecting $$$c$$$ is correct as the optimal choice at that poitn

• since $$$c$$$ is tested in alphabetical order, the first character to satisfy will always be the smallest choice
• add $$$c$$$ to the answer string, update $$$\text{curr_j} = \text{next_j}$$$, update $$$\text{curr_state} = \text{next_state}$$$, subtract the extra score from the target score, and break and go to $$$i + 1$$$.

#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;
}