k1r1t0's blog

TheForces Round #25 Editorial
By k1r1t0, history, 6 months ago, In English

Thank you for participating in #25!

104743A - Make All Elements 0 by Yugandhar_Master:

Editorial
Solution

104743B - Array Construction by wuhudsm:

Editorial
Solution

104743C - Prefix MEX Problem by pavlekn:

Editorial
Solution

104743D1 - Prefix XOR Problem(Easy Version) and 104743D2 - Prefix XOR Problem(Hard Version) by pavlekn:

Editorial (Easy Version)
Editorial (Hard Version)
Solution (Easy Version)
Solution (Easy Version)

104743E - Range Modulo Queries by Ashutosh.Singh:

Editorial
Solution

104743F - Yet Another Tree Problem by aryanc403:

Editorial
Solution
  • Vote: I like it
  • +39
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Very interesting contest <3

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial for A: How in all other cases answer is 2?

→ Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problems. Time Limit is too tight for python on E. Range Modulo Queries.

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Easy Solution for the Easy Version of D.

Solution
Implementation
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is passing hard version also

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I had made this test case during the contest :

      1
3
111
111

      If algorithm is run on this one, it will give 4 operations.

      Maybe the test cases (all of them) are generated using random, so all 1's is a rare case.

      → Reply
»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

my code is giving MLE

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
#include <string>
using namespace __gnu_pbds;
using namespace std;

#define ll long long int
#define lld long double
#define all(vec) vec.begin(), vec.end()
#define endl "\n"
#define pb push_back
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define ff first
#define ss second
#define flush cout << flush;
#define endl "\n"
// #define N 1e5 + 1
#define PI  3.141592653589793238462643383279
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

typedef tree<char, null_type, less_equal<char>, rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;
// find_by_order :- returns iterator to kth element starting from 0
// order_of_key:- elements less than current element

template <typename T>istream &operator>>(istream &in, vector<T> &a) {for (auto &x : a)in >> x; return in;};
template <typename T>ostream &operator<<(ostream &out, vector<T> &a) {for (auto &x : a)out << x << ' '; return out;};

template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &x) { return out << x.ff << ' ' << x.ss; }
template <typename T1, typename T2>istream &operator>>(istream &in, pair<T1, T2> &x) { return in >> x.ff >> x.ss; }

const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const ll NODE = 1e5 + 10;
const ll INF = 1e18;
const ll N = 1e6 + 5;
const ll NN = 1e18 + 1;
const ll MAX = 301;

ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}

long long binexp(ll a, ll b, ll m)
{
    ll res = 1;
    a %= m;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * 1LL * a) % m;
        }
        a = (a * 1LL * a) % m;
        b >>= 1;
    }
    return res;
}
ll f[1000005];
void fac() {
    f[0] = 1;
    for (ll i = 1; i < 1000005; i++)
        f[i] = (i % (MOD) * f[i - 1] % (MOD)) % (MOD);
}
ll inverse(ll a, ll p) {
    return binexp(a, p - 2, p);
}
ll ncr(ll n, ll r, ll p) {
    if (n == 0)return 0;
    if (n < r)
        return 0;
    if (r == 0)
        return 1;
    return (f[n] * inverse(f[r], p) % p * (inverse(f[n - r], p) % p)) % p;
}
ll Floor(ll a, ll b) {
    ll val = a / b;
    while (val * b > a)
        val--;
    return val;
}
bool subsequence(string main, string target)
{
    stack<char> s;
    for (ll i = 0; i < target.size(); i++)
        s.push(target[i]);

    for (ll i = main.size() - 1; i >= 0; i--)
    {
        if (s.top() == main[i])
            s.pop();
        if (s.empty())
            return true;
    }
    return s.empty();
}
ll binomialCoeff(ll n, ll k)
{
    ll C[k + 1];
    memset(C, 0, sizeof(C));

    C[0] = (ll)1; // nC0 is 1

    for (ll i = 1; i <= n; i++)
    {

        for (ll j = (ll)min(i, k); j > 0; j--)
            C[j] = (C[j] + C[j - 1]) % MOD;
    }
    return C[k] % MOD;
}
ll sumvec(vector<ll>&vec)
{
    ll sum = 0;
    for (ll i = 0; i < vec.size(); i++)
        sum += vec[i];
    return sum;
}
ll kadane(vector<ll> &vec)
{
    ll curr = 0;
    ll mx = LLONG_MIN;
    for (ll i = 0; i < vec.size(); i++)
    {
        curr += vec[i];
        if (curr < 0)
        {
            curr = 0;
        }
        mx = max(mx, curr);
    }
    return mx;
}
ll lis(vector<long long> a) {
    vector<long long> s;
    s.push_back(a[0]);
    ll n = a.size();
    ll len = 1;
    for (ll i = 1; i < n; i++) {
        ll idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();
        ll m = s.size();
        if (m > idx) {
            s[idx] = a[i];
        } else {
            s.push_back(a[i]);
        }
    }
    return s.size();
}
ll pollardRho(ll n) {
    if (n % 2 == 0)
        return 2 ;
    srand (time(NULL)) ;
    ll x, y , g = 1 , a;
    x = rand() % n + 1 ;
    y = x ;
    a = rand() % n + 1 ;
    while (g == 1) {
        x = ((x * x) + a) % n ;
        y = ((y * y) + a) % n ;
        y = ((y * y) + a) % n ;
        g = __gcd(abs(x - y), n) ;
    }
    return g ;
}
//vector<ll>g[N];
vector<ll>p(N);
vector<ll>subtree_sm(N);
vector<ll>time_in(N), time_out(N);
ll dfs_timer = 0;
vector<ll>pref(N);
vector<ll>height(N);
//vector<ll>vis(N);
//vector<ll>lvl(N);
ll ln = 0;
ll v = -1;
vector<ll>to_prime;
class dsu {
public:
    vector<ll>p, rank, size;
    ll n;
    dsu(ll n) {
        this->n = n;
        p.resize(n, 0);
        for (ll i = 0; i < n; i++) {
            p[i] = i;
        }
        rank.resize(n, 0);
        size.resize(n, 1);
    }
    ll findpar(ll n) {
        if (p[n] == n)return n;
        return p[n] = findpar(p[n]);
    }
    void unionset(ll i, ll j) {
        if (findpar(i) != findpar(j)) {
            ll p1 = findpar(i);
            ll p2 = findpar(j);
            if (size[p1] > size[p2]) {
                p[p2] = p1;
                size[p1] += size[p2];
            }
            else {
                p[p1] = p2;
                size[p2] += size[p1];
            }
        }
    }
};
// ll lg[1000005];
void sparse_table(ll vp, vector<ll>&a, vector<ll>&b, vector<vector<pair<ll, ll>>>&dp) {
    ll n = a.size();
    for (ll i = 0; i < n; i++) {
        dp[0][i] = {a[i] - b[i], b[i]};
    }
    for (ll i = 1; i < vp; i++) {
        for (ll j = 0; j + (1ll << i) - 1 < n ; j++) {
            dp[i][j] = {__gcd(dp[i - 1][j].ff, dp[i - 1][j + (1ll << (i - 1))].ff), max(dp[i - 1][j].ss, dp[i - 1][j + (1ll << (i - 1))].ss)};
        }
    }
}
vector<ll>factor[1000005];
void _segfault_()
{
    ll n, q; cin >> n >> q;
    vector<ll>a(n), b(n); cin >> a >> b;
    ll mx = *max_element(all(a));
    ll vp = log2(mx);
    vp++;
    vector<vector<pair<ll, ll>>>dp1(vp, vector<pair<ll, ll>>(n + 1));
    sparse_table( vp, a, b, dp1);
    // sparse_table2(b, dp2);
    while (q--) {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        ll i = log2(y - x + 1);
        ll gc = __gcd(dp1[i][x].ff, dp1[i][y - (1ll << i) + 1].ff);
        ll j = log2(y - x + 1);
        ll mx = max(dp1[j][x].ss, dp1[j][y - (1ll << j) + 1].ss);
        if (gc <= 0) {
            cout << -1 << endl;
            continue;
        }
        ll z = upper_bound(all(factor[gc]), mx) - factor[gc].begin();
        if (z == factor[gc].size()) {
            cout << -1 << endl;
        }
        else {
            cout << factor[gc][z] << endl;
        }
    }
}
int main(int argc, char const * argv[])
{
    // int32_t for returning val 32 bit integer always
    IOS
    clock_t z = clock();
    cout.setf(ios::fixed, ios::floatfield);
    cout.setf(ios::showpoint);
    cout << setprecision(10);
    // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    // fac();
    ll a = 1;
    // for (ll i = 2; i <= 1e6 + 5; i++)
    //     lg[i] = lg[i / 2] + 1;

    for (ll i = 1; i < 1000005; i++) {
        for (ll j = i; j < 1000005; j += i) {
            factor[j].pb(i);
        }
    }
    while (t--)
    {
        // cout << "Case #" << a << ": ";
        _segfault_();
        a++;
    }
    cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
    return 0;
}
→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, could sb give me an example plz?:)

    int n, x, y;
    std::cin >> n >> x >> y;
    if ((n == 1 && x != y)) {
        std::cout << "NO\n";
        return;
    }
    if (x & y != y) {
        std::cout << "NO\n";
    } else {
        int l1 = 0, l2 = 0;
        while (x) {
            l1 += (x & 1);
            x >>= 1;
        }
        while (y) {
            l2 += (y & 1);
            y >>= 1;
        }
        if ((1LL << (l1 - l2)) >= n) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sry I got some simple mistake in my code... when using bitwise operation, I forgot to adding "()" and got unexpected results.

    → Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

For Problem E I tried to submit I'm getting TLE at test-case-7 or test-case-11.

Also i'm using segment tree implementation from atcoder-library. Need help how to get AC?

231010905

Ashutosh.Singh

Update: Got it replaced endl with \n worked.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D Is the given string always consisting by 0 or 1 ?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are given two binary strings so the answer is yes

    → Reply