🧩 Codeforces Round 1017 (Div. 4)

# Info & Summary

• Date: 2025-04-13
• Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ✅ / F ❌ / G ❌ / H ❌
• Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	Bitwise operation	Bitmask/Bitwise	🔥⭐
F	Constructive	Constructive/Math	🌀⭐🧠
G	Implementation	Implementation/Math	🌀⚠️
H	Number theory/Math	Number theory/Math/Binary search	🌀⚠️

Details

Emoji	Label	Meaning
⭐	Important	Problem is strategically useful or has reusable patterns
🔥	Must master	Classic problem or technique that appears often and is worth mastering
⚠️	Reattempt	You attempted but failed; worth reviewing and solving again
🧠	New to me	Introduced a new idea, technique, or pattern you hadn’t seen before
🛠️	Template	You built or improved a code template from solving this problem
🌀	Too hard now	Beyond current ability to understand/solve; revisit after more practice

---

📌 A - Trippi Troppi

1017A

This can be solved by printing the zero-th index of each string in sequence

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    string a, b, c;
    cin >> a >> b >> c;

    cout << a[0] << b[0] << c[0] << endl;
}

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

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

    return 0;
}

📌 B - Bobritto Bandito

1017B

Tips

The problem reduces to find $l'$ and $r'$ such that $r' - l' = m$ and $l \le l' \le 0 \le r' \le r$

• If $m \le r$, we can choose $l' = 0$ and $r' = m$
• If $m > r$, we can choose $l' = r - m$ and $r' = r$

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, m, l, r;
    cin >> n >> m >> l >> r;

    if (m <= -l)
    {
        cout << -m << " " << 0 << endl;
    }
    else
    {
        cout << l << " " << r - (n - m) << endl;
    }
}

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

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

    return 0;
}

📌 C - Brr Brrr Patapim

1017C

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<int> nums(2 * n, -1);
    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int num;
            cin >> num;

            s.insert(num);
            nums[i + j - 1] = num;
        }
    }

    for (int i = 1; i <= 2 * n; i++)
    {
        if (s.find(i) == s.end())
        {
            nums[0] = i;
            break;
        }
    }

    for (int i = 0; i < 2 * n; i++)
    {
        cout << nums[i] << " \n"[i == 2 * n - 1];
    }
}

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

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

    return 0;
}

Tips

Each velue from $1$ to $2n$ must appear exactly once in $p$, thus, we can simply find the value which has not appeared yet, and choose that as $p_1$

• $2 \cdot n \cdot (2 \cdot n + 1) / 2$: the total value of $p$ if $1$ and $2n$ appear exactly once
• $accumulate(p.begin() + 1, p.end(), 0)$: the current sun of $p$

// Better version
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<int> p(2 * n, -1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int num;
            cin >> num;

            p[i + j - 1] = num;
        }
    }

    p[0] = 2 * n * (2 * n + 1) / 2 - accumulate(p.begin() + 1, p.end(), 0);

    for (int i = 0; i < 2 * n; i++)
    {
        cout << p[i] << " \n"[i == 2 * n - 1];
    }
}

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

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

    return 0;
}

📌 D - Tung Tung Sahur

1017D

First, suppose that there is only $L$ in both $s_1$ and $s_2$. Then it is clear that the answer is yes if and only if:

$$|s_1| \le |s_2| \le 2|s_1|$$

My code

#include <bits/stdc++.h>

using namespace std;

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

    p += ".";
    s += ".";

    // cout << p << " " << s << endl;

    int l1 = 0, l2 = 0;
    int r1 = 0, r2 = 0;

    while (r1 < p.size() && r2 < s.size())
    {
        while (r1 < p.size() && p[r1] == p[l1])
        {
            r1++;
        }
        while (r2 < s.size() && s[r2] == s[l2])
        {
            r2++;
        }
        if (r1 >= p.size())
        {
            r1--;
        }
        if (r2 >= s.size())
        {
            r2--;
        }

        // cout << l1 << " " << r1 << endl;
        // cout << l2 << " " << r2 << endl;

        if (p[l1] != s[l2])
        {
            cout << "NO" << endl;
            return;
        }

        if (2 * (r1 - l1) < (r2 - l2))
        {
            cout << "NO" << endl;
            return;
        }

        if ((r1 - l1) > (r2 - l2))
        {
            cout << "NO" << endl;
            return;
        }

        l1 = r1;
        l2 = r2;

        r1 = l1 + 1;
        r2 = l2 + 1;
    }

    // cout << l1 << " " << l2 << endl;

    if (l1 < p.size() - 1 || l2 < s.size() - 1)
    {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
}

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

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

    return 0;
}

// Better version
#include <bits/stdc++.h>

using namespace std;

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

    int i = 0;
    for (int l = 0, r = 0; l < p.size(); l = r)
    {
        while (r < p.size() && p[l] == p[r])
        {
            r++;
        }
        if (i == s.size() || s[i] != p[l])
        {
            cout << "NO\n";
            return;
        }

        int j = i;
        while (j < s.size() && s[i] == s[j])
        {
            j++;
        }

        if (j - i < r - l || j - i > 2 * (r - l))
        {
            cout << "NO\n";
            return;
        }

        i = j;
    }

    if (i == s.size())
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}

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

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

    return 0;
}

Tips

We can also partition $s_1$ into blocks(where we define a block to be a maximal group of contiguous identical characters)

Then the answer is YES if and only if $s_2$ is the concatenation of extensions of block in $s_1$

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    string a, b;
    cin >> a >> b;

    int n = a.size(), m = b.size();

    if (m < n || m > 2 * n || a[0] != b[0])
    {
        cout << "NO\n";
        return;
    }

    auto calc = [&](string s)
    {
        vector<int> group;
        int cnt = 1;
        for (int i = 1; i < s.size(); i++)
        {
            if (s[i] != s[i - 1])
            {
                group.push_back(cnt);
                cnt = 1;
            }
            else
            {
                cnt++;
            }
        }
        group.push_back(cnt);

        return group;
    };

    auto aa = calc(a);
    auto bb = calc(b);

    if (aa.size() != bb.size())
    {
        cout << "NO\n";
        return;
    }

    n = aa.size();
    for (int i = 0; i < n; i++)
    {
        if (aa[i] > bb[i] || aa[i] * 2 < bb[i])
        {
            cout << "NO\n";
            return;
        }
    }

    cout << "YES\n";
}

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

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

    return 0;
}

📌 E - Boneca Ambalabu

1017E

Tips

Consider each bit independently:

• For $0 \le i < 30$, let $cnt_i$ denote the number of elements of $a$ which have the $i$-th bit set(where bits are indexed from the least significant bit being the $0$-th bit)

Now, suppose we choose a particular $k$, then we can find the sum $(a_k \oplus a_1) + (a_k \oplus a_2) + ... + (a_k \oplus a_n)$ as follows:

• For a given bit position $i$, the number of elements $a_j$ such that $a_k \oplus a_j$ has the $i$-th bit set will be
  • $cnt_i$: if the $i$-th bit of $a_k$ is not set, so we can add $cnt_i \cdot 2^i$ to the answer
  • $n - cnt_i$: if the $i$-th bit of $a_k$ is set, so we can add $(n - cnt_i) \cdot 2^i$ to the answer

// My version
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<int> cnt(31, 0);
    vector<long long> nums(n);
    for (int i = 0; i < n; i++)
    {
        long long num;
        cin >> num;

        nums[i] = num;

        int idx = 0;
        while (num > 0)
        {
            cnt[idx] += num % 2;
            idx++;
            num /= 2;
        }
    }

    // for (int i = 0; i < 31; i++)
    // {
    //     cout << cnt[i] << " \n"[i == 30];
    // }

    long long ans = 0;

    for (int i = 0; i < n; i++)
    {
        vector<int> a(31, 0);

        int idx = 0;
        while (nums[i] > 0)
        {
            a[idx] += nums[i] % 2;
            idx++;
            nums[i] /= 2;
        }

        long long temp = 0;
        for (int j = 0; j < 31; j++)
        {
            if (a[j] == 1)
            {
                temp += (n - cnt[j]) * 1ll * pow(2, j);
            }
            else
            {
                temp += cnt[j] * 1ll * pow(2, j);
            }
        }

        if (temp > ans)
        {
            ans = temp;
        }
    }

    cout << ans << endl;
}

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

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

    return 0;
}

How to calculate $cnt_i$ quickly

for (int j = 0; j < 30; j++)
{
    cnt[j] += a[i] >> j & 1;
}

// Better version
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> cnt(30, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        for (int j = 0; j < 30; j++)
        {
            cnt[j] += a[i] >> j & 1;
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        long long cur = 0;
        for (int j = 0; j < 30; j++)
        {
            cur += (a[i] >> j & 1 ? n - cnt[j] : cnt[j]) * (1ll << j);
        }
        ans = max(ans, cur);
    }

    cout << ans << endl;
}

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

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

    return 0;
}

📌 F - Trulimero Trulicina

1017F

First, we can output the numbers $1, ..., k, 1, ..., k, ...$ in the natural reading order. For example $n = 3$, $m = 4$ and $k = 6$, we would output the following:

1	2	3	4
5	6	1	2
3	4	5	6

Warning

When $m$ is a multiple of $k$, for example, $n = 4$, $m = 6$ and $k = 3$, then we get:

1	2	3	1	2	3
1	2	3	1	2	3
1	2	3	1	2	3
1	2	3	1	2	3

Tips

We can fix this by Cyclically shifting every other row as follows:

1	2	3	1	2	3
2	3	1	2	3	1
3	1	2	3	1	2
1	2	3	1	2	3

Warning

I don't fully understand the code below

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    // The GCD of (n, k) gives us a natural way to divide the rows into groups
    int a = gcd(n, k);
    int b = k / a;

    assert(m % b == 0);

    if (a > 1 && b > 1)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cout << i % a * b + j % b + 1 << " \n"[j == m - 1];
            }
        }
    }
    else if (a == 1)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cout << i % a * b + (i + j) % b + 1 << " \n"[j == m - 1];
            }
        }
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cout << (i + j) % a * b + (i + j) % b + 1 << " \n"[j == m - 1];
            }
        }
    }
}

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

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

    return 0;
}

📌 G - Chimpanzini Bananini

1017G

Tips

Note that reversing an array then pushing an element to the back is similar to simply pushing an element to the front.

Thus, we would to use the deque data structure

To keep track of score, we need to maintain the values:

• the current score
• the score of the array if it were backwards
• the size of the array
• the sum of the array

• Suppose operation 1 is performed, this is equivalent to pop the back element of the array and push it in the front.
  • When you pop the back element of the array, score decreases by $a_n \cdot size$
  • Then when you push it to the front, score increases by $sum$ because $a_n$ is pushed to the first spot and every element form $a_1$ to $a_{n - 1}$ moves forward one spot
  • Notice that rscore changes in the reverse way, when you pop the first element of the array, rscore decreases by $sum$, and when you push it to the back, rscore increases by $a_n \cdot size$
  • size and sum remain unchanged
• Suppose operation 2 is performed. Then we swap score and rscore, and we also want to reverse the array
  • However, it is costly to entirely reverse the deque
  • Instead, we will set a flag to indicate that the array has been reversed. If the flag is set, we simply switch the front and back ends whenever we access or modify the deque while performing operations 1 or 3
• Suppose operation 3 is performed
  • then we see that size increases by 1 and sum increases by k
  • Then score increases by $k \cdot size$
  • ans rscore increases by sum, by identical reasoning to that in operation 1

Tips

We don't actually to maintain rscore, we can obtain it with the expression:

$$rscore = (n + 1)\sum_{i = 1}^{n}(a_i - score)$$

This is because $score + rscore = (n + 1)\sum_{i + 1}^{n}(a_i)$ since $i$-th term is counted $i$ times in score and $n + 1 - i$ times in rscore

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int q;
    cin >> q;

    deque<int> a;

    long long sum = 0;
    long long ans = 0;

    bool rev = false;

    for (int i = 0; i < q; i++)
    {
        int s;
        cin >> s;

        if (s == 1)
        {
            if (!rev)
            {
                int x = a.back();
                ans += sum;
                ans -= (long long)(a.size()) * x;
                a.pop_back();
                a.push_front(x);
            }
            else
            {
                int x = a.front();
                ans -= sum;
                ans += (long long)(a.size()) * x;
                a.pop_front();
                a.push_back(x);
            }
        }
        else if (s == 2)
        {
            rev ^= 1;
        }
        else
        {
            int k;
            cin >> k;

            if (!rev)
            {
                ans += (long long)(a.size()) * k;
                sum += k;
                a.push_back(k);
            }
            else
            {
                ans += sum;
                sum += k;
                a.push_front(k);
            }
        }

        if (!rev)
        {
            cout << ans + sum << endl;
        }
        else
        {
            cout << sum * (long long)(a.size()) - ans << endl;
        }
    }
}

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

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

    return 0;
}

📌 H - La Vaca Saturno Saturnita

1017H

Tips

a[i] must be a divisor of $k$ in order for $k$ to change

Tips

For each divisor $d$ of $k$, $k$ can only change once, because after the first iteration with $a[i] = d$, $k$ is no longer divisible by $d$

Thus, the number of times $k$ changes is bounded by the number of divisors of $k$, denoted by $d(k)$

And $d(k)$ can be found in $O(\sqrt{k})$ time by checking if $a$ divides $k$ for every $a$ form $2$ to $\sqrt{k}$, and if so, $a$ and $\frac{k}{a}$ are both divisors of $k$

We make the following observations:

• the value of $k$ only changes if $a[i]$ is a divisor of $k$
• if there exists $a[i_1] = a[i_2]$ with $l \le i_1 \le i_2 \le r$, then the value of $k$ will not change at $i = i_2$(because after the iteration $i = i_1$, we have that $k$ is no longer divisible by $a[i_2]$)

Now, we would like to find the first time each divisor of $k$ appears in $a[l], ..., a[r]$. This can be done by storing the array $a$ in a map, where each value is mapped to a vector of indices where that values appears. Then for a given divisor of $k$, we can use lower_bound() to find the smallest index at or after $l$ where this divisor appears, and we can check if it is no greater than $r$

Now, we have a list of indices at which $k$ might change:

• suppose that $k$ changes to $k'$ at index $i_1$, and then changes to $k''$ at index $i_2$
• Then we know that we have a value of $k'$ from $i = i_1$ to $i_2 - 1$, so we can add $k' \cdot (i_2 - i_1)$ to ans
• We can do this for all changes

Tips

We can use a vertor(of vectors) instead of a map, since $A = max(a_i) = 10^5$ is reasonably samll

Note that instantiating a vector of this size in every test case is too slow, so we may have to instantiate it globally and clear the vertors that were used after each test case

Tips

Another optimization is to preprocess divisors instead of computing them on the spot. We can compute and store the divisors of all integers $2 \le a_i \le 10^5$ in $O(A\log(A))$ time in a vector of vectors where $divisor[a_i]$ contains all divisors of $a_i$ as follows:

• For all $2 \le i \le A$, we push $i$ into $divisors[j]$ for all multiples of $j$ of $i$

This allow us to remove the $\sqrt{k}$ term in the runtime of each query

#include <bits/stdc++.h>

using namespace std;

constexpr int V = 1e5;
constexpr int inf = 1e9;

int pos[V + 1];
vector<int> factors[V + 1];

void solve()
{
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    vector<int> k(q), r(q);
    vector<vector<int>> qry(n);
    for (int i = 0; i < q; i++)
    {
        int l;
        cin >> k[i] >> l >> r[i];
        l--;

        qry[l].push_back(i);
    }

    vector<long long> ans(q);

    vector<int> nxt(n, inf);
    for (int i = n - 1; i >= 0; i--)
    {
        nxt[i] = pos[a[i]];
        pos[a[i]] = i;
    }

    for (int l = 0; l < n; l++)
    {
        for (auto i : qry[l])
        {
            while (k[i] % a[l] == 0)
            {
                k[i] /= a[l];
            }
            int t = inf;
            for (auto d : factors[k[i]])
            {
                t = min(t, pos[d]);
            }

            if (t >= r[i])
            {
                ans[i] += 1ll * (r[i] - l) * k[i];
            }
            else
            {
                ans[i] += 1ll * (t - l) * k[i];
                assert(t > l);
                qry[t].push_back(i);
            }
        }

        pos[a[l]] = nxt[l];
    }

    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << endl;
    }
}

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

    fill(pos, pos + V + 1, inf);
    for (int i = 2; i <= V; i++)
    {
        for (int j = i; j <= V; j += i)
        {
            factors[j].push_back(i);
        }
    }

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

    return 0;
}