Tesseract '26 Editorial

Try entering aa and aaa in the sandbox.

aa (Length 2) $$$\to$$$ 2a (Length 2). No space is saved, so it stays aa.

aaa (Length 3) $$$\to$$$ 3a (Length 2). Space is saved!

This is a variation of Run-Length Encoding (RLE). The goal is to compress a string based on consecutive character counts, but with specific rules designed to "only compress if it saves space":

If a character appears once (e.g., a), keep it as a. If a character appears twice (e.g., aa), keep it as aa (do not compress to 2a because length remains 2). If a character appears 3 or more times (e.g., aaaaa), compress it to 5a.

Approach: Iterate through the string while counting consecutive identical characters. If count is 1: Append s[i]. If count is 2: Append s[i] twice. If count > 2: Append count + s[i].

Time Complexity: $$$O(|S|)$$$

#include <bits/stdc++.h>
// Coded by Mr.Quantum (Darshan Patel)
using namespace std;

void solve()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        string compressed;
        int n = s.size();
        int i = 0;
        while (i < n)
        {
            int cnt = 1;
            while (i < n - 1 && s[i] == s[i + 1])
            {
                cnt++;
                i++;
            }
            if (cnt == 1)
                compressed.append(1, s[i]);
            else if( cnt == 2)
                compressed.append(2, s[i]);
            else
                compressed.append(to_string(cnt)).append(1, s[i]);
            i++;
        }
        cout << compressed << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
    return 0;
}

The title is short for "Pythagoras". Given $$$a \gt b$$$, think of right-angled triangles where $$$a$$$ is the hypotenuse.

For each test case, we are given two integers $$$a$$$ and $$$b$$$ such that $$$a \gt b$$$. We need to compute an integer value $$$c$$$. The value of $$$c$$$ is derived using the Pythagoras theorem:

Rearranging for $$$c$$$:

Since the problem asks for an integer output, we take the floor value:

Algorithm For each test case:

Read integers $$$a$$$ and $$$b$$$.

Compute $$$x = a^2 - b^2$$$.

Compute $$$c = \text{floor}(\sqrt{x})$$$.

Output $$$c$$$.

Correctness Proof From the Pythagoras theorem, $$$a^2 - b^2$$$ gives $$$c^2$$$. Taking the square root gives the exact value of $$$c$$$. When the result is not an integer, taking the floor gives the largest integer $$$c$$$ such that $$$c^2 \le a^2 - b^2$$$. Hence, the algorithm always produces the correct output.

Time Complexity: Each test case is processed in $$$O(1)$$$ time. Total time complexity is $$$O(t)$$$. Space Complexity: $$$O(1)$$$ extra space.

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

void solve() {
    long long a, b;
    cin >> a >> b;
    // Calculate c = sqrt(a^2 - b^2)
    long long c = sqrt(a * a - b * b);
    cout << c << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Key Insight: This is a linear recurrence relation of order 3 and can be solved iteratively.

We need to generate a sequence of $$$N$$$ integers using a recurrence relation. All values are printed modulo $$$10^9 + 7$$$.

Recursive Definition

$$$f(1) = 1$$$

$$$f(2) = (n + 1) / 2$$$

$$$f(3) = n$$$

For $$$n \ge 4$$$: $$$f(n) = f(n-1) + 2 \cdot f(n-2) + 7 \cdot f(n-3)$$$

Approach We only store the last three values of the sequence. Using iteration, we compute each new term efficiently.

Complexity Time Complexity: $$$O(N)$$$ Space Complexity: $$$O(1)$$$

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

using ll  = long long;
ll mod=1e9+7;
void solve(){
    ll n;
    cin>>n;
    ll a=1,b=(n+1)/2,c=n;

    cout<<a<<" "<<b<<" "<<c<<" ";
    for(int i=3;i<n;i++){
        a=(7*a +2*b+c)%mod;
        swap(a,b);
        swap(c,b);
        cout<<c<<" ";
    }
    cout<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1;
    // cin>>t;
    while (t--) solve();
    return 0;
}

Think about the distance to the nearest infected person. If the distance is $$$\le K$$$, you get infected.

The virus spreads $$$K$$$ units in both directions. This means any person at index $$$i$$$ will get infected if there is an initially infected person at index $$$j$$$ such that $$$|i - j| \le K$$$.

Approach Instead of simulating the spread step-by-step (which would be slow for large $$$K$$$), we can calculate the distance to the nearest 1 for every position.

Initialize a dist array with infinity.

Left-to-Right Pass: Iterate from $$$0$$$ to $$$N-1$$$. Maintain the position of the last seen 1. Update dist[i] based on this distance.

Right-to-Left Pass: Iterate from $$$N-1$$$ to $$$0$$$. Maintain the position of the last seen 1. Update dist[i] again.

Final Check: For each $$$i$$$, if dist[i] <= K, output 1, else 0.

Time Complexity: $$$O(N)$$$ Space Complexity: $$$O(N)$$$

#include <bits/stdc++.h>
// Coded by Mr.Quantum (Darshan Patel)
using namespace std;

void solve()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        int n;
        cin >> s >> n;

        int len = s.length();
        vector<int> dist(len, 1e9);

        int last1 = -1e9;
        for (int i = 0; i < len; i++)
        {
            if (s[i] == '1')
                last1 = i;
            dist[i] = min(dist[i], i - last1);
        }

        last1 = 2e9;
        for (int i = len - 1; i >= 0; i--)
        {
            if (s[i] == '1')
                last1 = i;
            dist[i] = min(dist[i], last1 - i);
        }

        for (int i = 0; i < len; i++)
        {
            if (dist[i] <= n)
                cout << '1';
            else
                cout << '0';
        }
        cout << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
    return 0;
}

Intel: "System Log: Request at T=90 rejected. Request at T=110 accepted. (Cooldown K=100, Start T=0)."

This suggests that rejected packets do not reset the timer. You only check the cooldown against the last accepted packet.

We need to enforce a minimum time difference limit between consecutive allowed requests.

Pitfall A common mistake is checking current_time — previous_packet_time >= limit. This is incorrect because if the previous packet was blocked, it shouldn't reset the timer. The correct logic is: current_time — last_accepted_time >= limit.

Approach

Always accept the first request (as there is no prior history). Set lastAllowed = a[0].

Iterate through the subsequent timestamps:

If a[i] — lastAllowed >= limit, accept the packet (1) and update lastAllowed = a[i].

Otherwise, reject the packet (0) and keep lastAllowed unchanged.

Time Complexity: $$$O(N)$$$

#include <bits/stdc++.h>
// Coded by Mr.Quantum (Darshan Patel)
using namespace std;

void solve()
{
    int t;
    cin >> t;
    while (t--)
    {
        // n = number of requests, limit = minimum time difference required between two allowed requests
        int n, limit;
        cin >> n >> limit;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];

        vector<int> ans;
        // first request is allowed
        // 1 - allowed, 0 - not allowed
        ans.push_back(1);
        int lastAllowed = a[0];
        for (int i = 1; i < n; i++)
        {
            if (a[i] - lastAllowed >= limit)
            {
                ans.push_back(1);
                lastAllowed = a[i];
            }
            else
            {
                ans.push_back(0);
            }
        }
        for (auto x : ans)
            cout << x << " ";

        cout << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
    return 0;
}

Problem Overview

This problem is based on a numeric sequence and multiple query types. The main challenge is to efficiently answer queries on the sequence under large constraints.

Sequence Definition

The sequence begins as: 3, 9, 18, 30, 45, ... From these values, it can be deduced that the n-th term of the sequence is given by: $$$P_n = 3 \times n \times (n + 1) / 2$$$

Query Handling

The problem includes both update and query operations. Only specific query types produce output, while others modify the sequence.

Efficient Strategy

To handle the constraints efficiently, prefix sums and lazy propagation techniques can be used. This allows each query to be processed in logarithmic or constant time.

Conclusion

By identifying the closed-form expression for the sequence and using appropriate data structures, all queries can be answered efficiently within the given limits.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long MOD = 1e9 + 7;
const int MAXN = 200005;

long long S1[MAXN];
long long S2[MAXN];

void precompute() {
    S1[0] = 0;
    S2[0] = 0;
    for (long long i = 1; i < MAXN; i++) {
        S1[i] = (S1[i - 1] + i) % MOD;
        S2[i] = (S2[i - 1] + i * i) % MOD;
    }
}

long long get_sum_i(int l, int r) {
    return (S1[r] - S1[l - 1] + MOD) % MOD;
}

long long get_sum_sq_i(int l, int r) {
    return (S2[r] - S2[l - 1] + MOD) % MOD;
}

vector<long long> treeP, treePi, lazy;
int n;

void push(int v, int tl, int tr) {
    if (lazy[v] == 0) return;
    int tm = (tl + tr) / 2;
    long long k = lazy[v];

    treeP[2 * v] = (treeP[2 * v] + k * get_sum_i(tl, tm)) % MOD;
    treePi[2 * v] = (treePi[2 * v] + k * get_sum_sq_i(tl, tm)) % MOD;
    lazy[2 * v] = (lazy[2 * v] + k) % MOD;

    treeP[2 * v + 1] = (treeP[2 * v + 1] + k * get_sum_i(tm + 1, tr)) % MOD;
    treePi[2 * v + 1] = (treePi[2 * v + 1] + k * get_sum_sq_i(tm + 1, tr)) % MOD;
    lazy[2 * v + 1] = (lazy[2 * v + 1] + k) % MOD;

    lazy[v] = 0;
}

void build(int v, int tl, int tr) {
    lazy[v] = 0;
    if (tl == tr) {
        long long i = tl;
        long long val = (3 * i * (i + 1)) / 2;
        val %= MOD;
        treeP[v] = val;
        treePi[v] = (val * i) % MOD;
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        treeP[v] = (treeP[2 * v] + treeP[2 * v + 1]) % MOD;
        treePi[v] = (treePi[2 * v] + treePi[2 * v + 1]) % MOD;
    }
}

void update(int v, int tl, int tr, int l, int r, int k) {
    if (l > r) return;
    if (l == tl && r == tr) {
        treeP[v] = (treeP[v] + (long long)k * get_sum_i(tl, tr)) % MOD;
        treePi[v] = (treePi[v] + (long long)k * get_sum_sq_i(tl, tr)) % MOD;
        lazy[v] = (lazy[v] + k) % MOD;
    } else {
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, min(r, tm), k);
        update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, k);
        treeP[v] = (treeP[2 * v] + treeP[2 * v + 1]) % MOD;
        treePi[v] = (treePi[2 * v] + treePi[2 * v + 1]) % MOD;
    }
}

long long queryP(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return treeP[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return (queryP(2 * v, tl, tm, l, min(r, tm)) + queryP(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)) % MOD;
}

long long queryPi(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return treePi[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return (queryPi(2 * v, tl, tm, l, min(r, tm)) + queryPi(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)) % MOD;
}

void solve() {
    int q;
    cin >> n >> q;
    treeP.assign(4 * n + 1, 0);
    treePi.assign(4 * n + 1, 0);
    lazy.assign(4 * n + 1, 0);

    build(1, 1, n);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            cout << queryP(1, 1, n, l, r) << "\n";
        } else if (type == 2) {
            int x;
            cin >> x;
            cout << queryP(1, 1, n, x, x) << "\n";
        } else if (type == 3) {
            int l, r, k;
            cin >> l >> r >> k;
            update(1, 1, n, l, r, k);
        } else if (type == 4) {
            int l, r;
            cin >> l >> r;
            cout << queryPi(1, 1, n, l, r) << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

The problem asks for an order of installation. If $$$U$$$ depends on $$$V$$$, $$$V$$$ must be processed before $$$U$$$. This suggests a directed graph where edges represent dependencies. Also, look out for "IMPOSSIBLE", this happens when there is a circular dependency.

We need to linearize a set of dependencies. This is the definition of Topological Sorting. Since we need to output the lexicographically smallest order when there are choices, a standard Queue based BFS (Kahn's Algorithm) needs a modification.

Graph Construction: Map each string to an integer ID (0 to N-1) based on alphabetical order. This makes handling lexicographical requirements easier.

If Module $$$U$$$ requires Module $$$V$$$, draw a directed edge $$$V \to U$$$ (since $$$V$$$ comes first).

Kahn's Algorithm:

Calculate in-degrees for all nodes.

Push all nodes with in-degree == 0 into a Min-Priority Queue (instead of a standard Queue). This ensures we always pick the alphabetically smallest available module.

Pop a node, add to result, and decrement in-degrees of neighbors.

If a neighbor's in-degree becomes 0, push to PQ.

Cycle Detection: If the size of the topological sort is less than $$$N$$$, a cycle exists. Output IMPOSSIBLE.

Time Complexity: $$$O(V + E \log V)$$$ due to the Priority Queue. Space Complexity: $$$O(V + E)$$$

#include <bits/stdc++.h>
// Coded by Mr.Quantum (Darshan Patel)
using namespace std;

void solve()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        vector<pair<string, string>> edges(n);
        set<string> names;
        for (int i = 0; i < n; i++)
        {
            cin >> edges[i].first >> edges[i].second;
            names.insert(edges[i].first);
            names.insert(edges[i].second);
        }
        
        // assign id based on alphabetical order
        vector<string> idToName(names.begin(), names.end());
        unordered_map<string, int> nameToId;
        for (int i = 0; i < idToName.size(); i++)
            nameToId[idToName[i]] = i;

        int numNodes = idToName.size();
        vector<vector<int>> adj(numNodes);
        vector<int> indegree(numNodes, 0);

        for (auto &edge : edges)
        {
            int u = nameToId[edge.first], v = nameToId[edge.second];
            adj[v].push_back(u); // v -> u
            indegree[u]++;
        }

        // priority_queue for lexicographical greedy choice :)
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < numNodes; i++)
        {
            if (indegree[i] == 0)
                pq.push(i);
        }

        vector<int> order;
        while (!pq.empty())
        {
            int u = pq.top();
            pq.pop();
            order.push_back(u);
            for (int v : adj[u])
            {
                if (--indegree[v] == 0)
                    pq.push(v);
            }
        }

        if (order.size() != numNodes)
        {
            cout << "IMPOSSIBLE" << "\n";
        }
        else
        {
            for (int id : order)
                cout << idToName[id] << "\n";
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
    return 0;
}

'(( ))' = 2. '( ) ( )' = 1." This implies we are looking for the maximum nesting depth, not just the count of pairs. Also, be careful about invalid signals (unbalanced brackets).

The problem asks for the maximum nesting depth of a valid parenthesis string.

Initialize currDepth = 0 and maxDepth = 0.

Iterate through the string:

If (, increment currDepth. Update maxDepth = max(maxDepth, currDepth).

If ), decrement currDepth.

If currDepth ever drops below 0 (e.g., )(), the string is invalid immediately.

If currDepth is not 0 at the end (e.g., (()), the string is invalid.

If invalid, print -1. Otherwise, print maxDepth.

Time Complexity: $$$O(N)$$$ Space Complexity: $$$O(1)$$$

#include <bits/stdc++.h>
// Coded by Mr.Quantum (Darshan Patel)
using namespace std;

void solve()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;

        int currDepth = 0;
        int maxDepth = 0;
        bool valid = true;

        for (char ch : s)
        {
            if (ch == '(')
            {
                currDepth++;
                maxDepth = max(maxDepth, currDepth);
            }
            else
            {
                currDepth--;
                if (currDepth < 0)
                {
                    valid = false;
                    break;
                }
            }
        }
        if (currDepth != 0)
            valid = false;

        if (valid)
            cout << maxDepth << "\n";
        else
            cout << -1 << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
    return 0;
}

Intel: "Update Log: '1.2' is OLDER than '1.10'." This implies standard string comparison is incorrect because "2" > "1". You must parse the version numbers as distinct integer segments.

IMP 1: Lexicographical vs. Version Sort

Comparing version strings lexicographically (like words in a dictionary) fails.

Lexicographically: "1.10" < "1.2" (because '1' comes before '2').

Version Logic: 1.10 > 1.2 (because the integer 10 is greater than 2).

IMP 2: Don;t use stoi() function of c++, as it will cause Runtime Error. As segment like 1.999999999999999999 will overflow standard integer type.

Leading Zeros Since segments are parsed as integers, leading zeros do not affect the value.

01, 0001, and 1 are all mathematically equal.

Therefore, version 1.0001 is considered EQUAL to 1.1 regarding that segment.

Similarly, 1.0001 and 1.00001 are equal.

Solution

Split the version string by the dot . delimiter into chunks.

Pad the shorter version with zeros (e.g., 1.0 vs 1.0.1 becomes 1.0.0 vs 1.0.1).

Compare chunks from left to right as Integers (or numerical strings to avoid overflow).

Removing leading zeros allows us to compare using string length and lexicographical order safely for arbitrarily large numbers.

Time Complexity: $$$O(|S|)$$$

#include<bits/stdc++.h>
// Coded by Mr.Quantum (Darshan Patel)
using namespace std;

int compNumStr(string s1, string s2) {
    // remove leading zeros
    while(s1.size() > 1 && s1[0] == '0') s1.erase(s1.begin());
    while(s2.size() > 1 && s2[0] == '0') s2.erase(s2.begin());

    // longer string is automatically larger (e.g., "100" > "99")
    if (s1.length() > s2.length()) return 1;
    if (s2.length() > s1.length()) return 2;

    // if lengths are equal, standard string comparison works (e.g., "54" > "51")
    if (s1 > s2) return 1;
    if (s2 > s1) return 2;
    return 0;
}

void solve(){
    int t; cin >> t;
    while(t--){
        string v1, v2;
        cin >> v1 >> v2;

        // store chunks as strings, not ints
        vector<string> ver1, ver2;
        
        int i = 0;
        while(i < v1.size()){
            string temp = "";
            while(i < v1.size() && v1[i] != '.'){
                temp += v1[i];
                i++;
            }
            ver1.push_back(temp);
            i++;
        }
        
        i = 0;
        while(i < v2.size()){
            string temp = "";
            while(i < v2.size() && v2[i] != '.'){
                temp += v2[i];
                i++;
            }
            ver2.push_back(temp);
            i++;
        }

        int n1 = ver1.size();
        int n2 = ver2.size();
        int n = max(n1, n2);

        // pad with string "0"
        while(ver1.size() < n) ver1.push_back("0");
        while(ver2.size() < n) ver2.push_back("0");

        int flag = -1;
        for(int k = 0; k < n; k++){
            // use custom comparator instead of direct >, <
            int res = compNumStr(ver1[k], ver2[k]);
            if(res == 1){
                flag = 1;
                break;
            }
            else if(res == 2){
                flag = 2;
                break;
            }
        }

        if(flag == -1) cout << "EQUAL" << "\n";
        else if(flag == 1) cout << v1 << "\n";
        else cout << v2 << "\n";
    }
}

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

The three inputs $$$a, b, c$$$ can be arranged into a $$$2 \times 2$$$ symmetric matrix. The problem asks for a fundamental property of this matrix related to its spectrum.

This reverse coding problem presents inputs of the form: $$$a, b, c$$$. These values are interpreted as components of a $$$2 \times 2$$$ real symmetric matrix:

The task is to compute the maximum eigenvalue of this matrix. The output produced by the hidden program matches exactly with the closed-form expression for the largest eigenvalue of a $$$2 \times 2$$$ symmetric matrix.

Maths

The eigenvalues $$$\lambda$$$ are obtained by solving the characteristic equation:

Explicitly:

Expanding the determinant gives:

This leads to the quadratic equation:

Using the quadratic formula, the eigenvalues are:

Simplifying the term under the square root: $$$(a+c)^2 - 4ac + 4b^2 = a^2 + 2ac + c^2 - 4ac + 4b^2 = a^2 - 2ac + c^2 + 4b^2 = (a-c)^2 + 4b^2$$$

Thus, the eigenvalues are:

Since we want the maximum eigenvalue, we take the positive root.

Final Algorithm Given inputs $$$a, b, c$$$:

Compute the trace average: $$$t_1 = (a + c)$$$.

Compute the discriminant part: $$$t_2 = \sqrt{(a - c)^2 + 4b^2}$$$.

The result is $$$\lambda_{max} = \frac{t_1 + t_2}{2}$$$.

The algorithm runs in constant time $$$O(1)$$$.

#include<bits/stdc++.h>
#include<chrono>
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define T true
#define F false
#define vl vector<ll>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define max3(a,b,c) ((a>b)?((a>c)?a:c):((b>c)?b:c))
#define min3(a,b,c) ((a<b)?((a<c)?a:c):((b<c)?b:c))
#define all(a) (a).begin(),(a).end()

#define FOR(a, c) for (int(a) = 0; (a) < (c); (a)++)
#define FORL(a, b, c) for (int(a) = (b); (a) <= (c); (a)++)
#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); (a)--)

const long long M=1e9+7;
const long long P=998244353;
using namespace std;
using namespace chrono;
//=============================================Useful functions==========================================
bool isPrime(ll n){
    if(n==0 || n==1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}
//Primes upto n
vector<bool> sieve(int n){
    vector<bool> prime(n+1,true);
    prime[0]=prime[1]=false;
    for(int i=2;i*i<=n;i++){
        if(prime[i]){
            for(int j=i*i;j<=n;j+=i) prime[j]=false;
        }
    }
    return prime;
}
ll modExp(ll a,ll b,ll m){
    if(b==0) return 1;
    ll half=modExp(a,b/2,m)%m;
    if(b%2!=0) return (((half%m)*(half%m))%m*(a%m))%m;
    else return ((half%m)*(half%m))%m;
}
ll xorUpto(ll n){
    if(n%4==0) return n;
    else if(n%4==1) return 1;
    else if(n%4==2) return n+1;
    else return 0;
}
//=======================================================================================================






//=============================================TJ CODE START==========================================
void solve(){
    ld a,b,c;
    cin>>a>>b>>c;
    ld maxEig=((a+c)+sqrt((a-c)*(a-c)+4*b*b))/2.0;
    cout<<fixed<<setprecision(3)<<maxEig<<endl;
}
//=============================================TJ CODE END==========================================






int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    auto start = high_resolution_clock::now();
    int t=1;
    cin>>t;
    while(t--) solve();
    auto end = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cerr<< duration.count()*1e-6<< endl; //s
    return 0;
}

Look closely at the factors generating the sequence. One part grows linearly (AP), and another grows exponentially (GP).

Problem Overview We are given a hidden infinite strictly increasing sequence Sequence[]. For each query $$$(x, y)$$$, we must compute: $$$(\text{Sequence}[y] - \text{Sequence}[x]) \pmod{10^9 + 7}$$$.

Observation from Code Analyzing the precomputation logic:

$$$a$$$ starts from 1 and increases by 2 each step $$$\to$$$ Arithmetic Progression (AP): $$$1, 3, 5, \dots$$$

$$$b$$$ starts from 1 and is multiplied by 3 each step $$$\to$$$ Geometric Progression (GP): $$$1, 3, 9, \dots$$$

$$$\text{Sequence}[i] = a \times b$$$

Deriving Formula At index $$$i$$$:

$$$a_i = 1 + 2(i-1) = 2i - 1$$$

$$$b_i = 3^{i-1}$$$

So,

This sequence is an AGP (Arithmetic-Geometric Progression), where each term is the product of an AP term and a GP term.

Queries Since the sequence is fixed and strictly increasing, we precompute $$$\text{Sequence}[i]$$$ for all $$$i$$$ up to 100,000. Each query is then answered in $$$O(1)$$$ time using: $$$(\text{Sequence}[y] - \text{Sequence}[x] + \text{MOD}) \pmod{\text{MOD}}$$$

Complexity Analysis

Precomputation Time: $$$O(N)$$$

Per Query Time: $$$O(1)$$$

Space Complexity: $$$O(N)$$$

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

using ll  = long long;
ll mod=1e9+7;
void solve(){
    vector<ll>seq(100005);
     ll a=1,b=1;
    for(int i=1;i<=100000;i++){
        seq[i]=(a*b)%mod;
        a+=2;
        b=(3*b)%mod;
    }
    ll n;
    cin>>n;
    while(n--){
        int x,y;
        cin>>x>>y;
        cout<<(seq[y]-seq[x]+mod)%mod<<endl;
    }
    
    // cout<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1;
    // cin>>t;
    while (t--) solve();
    return 0;
}

"Network fragmentation" implies disconnected parts of a graph. We need to count how many independent sets of servers exist.

The problem asks for the number of Connected Components in an undirected graph where servers are nodes and cables are edges.

Best Approach (Disjoint Set Union — DSU) This problem can be solved efficiently using DSU (Union-Find) or Graph Traversal (DFS/BFS). The DSU approach is elegant!

Initialize: Start with $$$N$$$ isolated servers. Each server is its own component. Set components = N.

Process Edges: For every connection $$$(u, v)$$$:

Find the representative roots of $$$u$$$ and $$$v$$$.

If they are in different sets (root_u != root_v), unite them.

Whenever a union occurs, two components merge into one, so we decrement the components counter by 1.

After processing all edges, print the remaining components count.

Time Complexity: $$$O(M \cdot \alpha(N))$$$, where $$$\alpha$$$ is the Inverse Ackermann function (nearly constant). Space Complexity: $$$O(N)$$$

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

class DSU
{
public:
    vector<int> parent, sz;
    int components;

    DSU(int n)
    {
        parent.resize(n + 1);
        sz.resize(n + 1, 1);
        components = n;
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }

    int find(int i)
    {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    bool unite(int i, int j)
    {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j)
        {
            if (sz[root_i] < sz[root_j])
                swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            components--;
            return true;
        }
        return false;
    }
};

void solve()
{
    int t;
    cin >> t;
    while (t--)
    {

        int n, m;
        cin >> n >> m;
        DSU dsu(n);
        while (m--)
        {
            int u, v;
            cin >> u >> v;
            dsu.unite(u, v);
        }
        cout << dsu.components << "\n";
    }
}

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

    solve();
    return 0;
}

This is a reverse-coding problem. The output structure (3 lines of 8 numbers) is a major clue. Think about numerical bases.

Key Observations

For every input X, exactly 24 integers are printed.

The output is arranged in 3 lines, each containing 8 integers.

Each printed value is an integer taken modulo $$$10^9 + 7$$$.

Hidden Pattern

Let $$$rev(X)$$$ denote the digit-reverse of $$$X$$$ in base 10. Using $$$X$$$ and $$$rev(X)$$$, three independent values are formed:

$$$X + rev(X)$$$

$$$|X - rev(X)|$$$

Concatenation of $$$X$$$ and $$$rev(X)$$$

Each of these values is then represented in bases from 10 down to 3. The digits of each base representation are treated as a decimal number and reduced modulo $$$10^9 + 7$$$.

Sample Walkthrough (Input: 1126) Let $$$X = 1126$$$. Its reverse is $$$rev(X) = 6211$$$.

First Line (Addition): Compute $$$Y = 1126 + 6211 = 7337$$$. Now write 7337 in bases 10, 9, 8, 7, 6, 5, 4, and 3. Each representation is treated as a decimal number and printed. This produces the first row of 8 outputs.

Second Line (Absolute Difference): Compute $$$Y = |1126 - 6211| = 5085$$$ and repeat the same base conversions.

Third Line (Concatenation): Form $$$Y = concatenate(1126, 6211) = 11266211$$$ and again print its representations in bases 10 down to 3.

Complexity All operations involve digit manipulation and a constant number of base conversions. Thus, the solution runs efficiently for all valid inputs.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

long long MOD = 1000000007;

long long convert(long long n, int base) {
    if (n == 0) return 0;
    long long res = 0;
    long long multiplier = 1;
    while (n > 0) {
        long long digit = n % base;
        res = (res + (digit * multiplier) % MOD) % MOD;
        multiplier = (multiplier * 10) % MOD;
        n /= base;
    }
    return res;
}

int main() {
    string s;
    if (!(cin >> s)) return 0;

    string r = s;
    reverse(r.begin(), r.end());

    long long x_val = stoll(s);
    long long r_val = stoll(r);

    long long v1 = x_val + r_val;
    long long v2 = abs(x_val - r_val);
    long long v3 = stoll(s + r);

    vector<long long> targets = {v1, v2, v3};

    for (int i = 0; i < 3; i++) {
        for (int b = 10; b >= 3; b--) {
            cout << convert(targets[i], b) << (b == 3 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}