#	User	Rating
1	Benq	3783
2	jiangly	3666
3	tourist	3611
4	Um_nik	3536
5	inaFSTream	3477
6	fantasy	3468
7	maroonrk	3464
8	QAQAutoMaton	3428
9	ecnerwala	3427
10	Ormlis	3396

#	User	Contrib.
1	Um_nik	185
2	adamant	178
3	awoo	177
4	nor	169
5	maroonrk	165
6	-is-this-fft-	164
7	antontrygubO_o	153
8	ko_osaga	151
9	dario2994	150
10	SecondThread	149

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back



void solve() {
    int m; cin >> m;
    string t = to_string(m);
    string s = "1";
    for (int i = 1; i < sz(t); i++) {
        s += '0';
    }
    int k = stoi(s);
    cout << m - k << '\n';
}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1702B - Polycarp Writes a String from Memory

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back



void solve() {
    string s; cin >> s;
    set<char> v;
    int ans = 0;
    for (int i = 0; i < sz(s); i++) {
        v.insert(s[i]);
        if (sz(v) > 3) {
            ans++;
            v.clear();
            v.insert(s[i]);
        }
    }
    if (!v.empty()) ans++;
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1702C - Train and Queries

Idea: MikeMirzayanov

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)


void solve(){
    int n, k;
    cin >> n >> k;
    map<int, pair<int, int>>m;
    forn(i, n){
        int u;
        cin >> u;
        if(!m.count(u)) {
            m[u].first = i;
            m[u].second = i;
        }
        else m[u].second = i;
    }
    forn(i, k){
        int a, b;
        cin >> a >> b;
        if(!m.count(a) or !m.count(b) or m[a].first > m[b].second) {
            cout << "NO\n"; //equals = 0 = wrong
        }
        else cout << "YES\n";
    }
}

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

1702D - Not a Cheap String

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        string s;
        cin >> s;
        int p;
        cin >> p;
        string w(s);
        sort(w.rbegin(), w.rend());
        int cost = 0;
        forn(i, s.length())
            cost += s[i] - 'a' + 1;
        map<char,int> del;
        forn(i, w.length())
            if (cost > p) {
                del[w[i]]++;
                cost -= w[i] - 'a' + 1;
            }
        forn(i, s.length()) {
            if (del[s[i]] > 0) {
                del[s[i]]--;
                continue;
            }
            cout << s[i];
        }
        cout << endl;
    }
}

1702E - Split Into Two Sets

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define forn(i, n) for (int i = 0; i < int(n); i++)

map<int, vector<int>> m;
vector<bool> used;

int go(int v) {
    used[v] = true;
    for (auto now : m[v]) {
        if (!used[now]) {
            return go(now) + 1;
        }
    }
    return 1;
}

void solve() {

    int n, x, y;
    cin >> n;

    m.clear();
    used.clear();
    used.resize(n + 1, false);

    bool fault = false;
    forn(i, n) {
        cin >> x >> y;
        m[x].push_back(y);
        m[y].push_back(x);
        if (x == y || m[x].size() > 2 || m[y].size() > 2) fault = true;
    }

    if (fault) {
        cout << "NO\n";
        return;
    }

    forn(i, n) {
        if (!used[i + 1]) {
            if (go(i + 1) % 2) {
                cout << "NO\n";
                return;
            }
        }
    }

    cout << "YES\n";
}
int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        solve();
    }
}

1702F - Equate Multisets

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back

const int INF = 1e9;

void solve() {
    int n; cin >> n;
    multiset<int> a, b;

    forn(i, n) {
        int x; cin >> x;
        while (x % 2 == 0) {
            x /= 2;
        }
        a.insert(x);
    }

    forn(i, n) {
        int x; cin >> x;
        b.insert(x);
    }
    n = sz(a);

    while (!b.empty()) {
        int x = *b.rbegin();
        // cout << x << endl;
        if (!a.count(x)) {
            if (x == 1) break;
            b.erase(b.find(x));
            b.insert(x / 2);
        } else {
            b.erase(b.find(x));
            a.erase(a.find(x));
        }
    }

    cout << (b.empty() ? "YES" : "NO") << endl;

}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1702G1 - Passable Paths (easy version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long double ld;
typedef long long ll;

using namespace std;

mt19937 rnd(143);

const int inf = 1e15;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;

void depth(int v, int p, vector<vector<int>> &sl, vector<int> &d){
    if(p >= 0) d[v] = d[p] + 1;
    for(int u: sl[v]){
        if(u == p) continue;
        depth(u, v, sl, d);
    }
}

int dfs(int v, int p, vector<vector<int>> &sl, vector<bool> &chosen){
    int res = 0;
    bool lower = false;
    for(int u: sl[v]){
        if(u == p) continue;
        res += dfs(u, v, sl, chosen);
        lower = lower || chosen[u];
    }
    chosen[v] = chosen[v] || lower;
    if(chosen[v] && !lower) res = 1;
    return res;
}

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> sl(n);
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].push_back(--v);
        sl[v].push_back(u);
    }
    vector<int> d(n);
    depth(0, -1, sl, d);
    int q;
    cin >> q;
    for(; q; --q){
        int k;
        cin >> k;
        vector<bool> chosen(n);
        int mx = 0;
        for(int i = 0; i < k; ++i){
            int p;
            cin >> p;
            --p;
            if(d[p] > d[mx]) mx = p;
            chosen[p] = true;
        }
        int leaves = dfs(mx, -1, sl, chosen);
        if(leaves == 1) cout << "YES\n";
        else cout << "NO\n";
    }
}

bool multi = false;

signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (; t; --t) {
        solve();
        //cout << endl;
    }
    return 0;
}

1702G2 - Passable Paths (hard version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long double ld;
typedef long long ll;

using namespace std;

mt19937 rnd(143);

const int inf = 1e15;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;

int n, sz;
vector<vector<int>> sl, up;
vector<int> d;

void precalc(int v, int p){
    d[v] = d[p] + 1;
    up[v][0] = p;
    for(int i = 1; i <= sz; ++i){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int u: sl[v]){
        if(u == p) continue;
        precalc(u, v);
    }
}

int lca(int u, int v){
    if(d[u] < d[v]){
        swap(u, v);
    }
    for(int cur = sz; cur >= 0; --cur){
        if (d[u] - (1 << cur) >= d[v]) {
            u = up[u][cur];
        }
    }
    for(int cur = sz; cur >= 0; --cur){
        if (up[u][cur] != up[v][cur]) {
            u = up[u][cur];
            v = up[v][cur];
        }
    }
    return u == v ? u : up[u][0];
}

void solve(){
    cin >> n;
    sz = 0;
    while ((1 << sz) < n) sz++;
    d.assign(n, -1);
    up.assign(n, vector<int>(sz + 1));
    sl.assign(n, vector<int>(0));
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].push_back(--v);
        sl[v].push_back(u);
    }
    precalc(0, 0);
    int q;
    cin >> q;
    for(; q; --q){
        int k;
        cin >> k;
        vector<int> p(k);
        for(int &e: p) {
            cin >> e;
            --e;
        }
        sort(all(p), [](int a, int b) {
            return d[a] > d[b];
        });
        vector<bool> used(k);
        for(int i = 0; i < k; ++i){
            if(lca(p[0], p[i]) == p[i]) used[i] = true;
        }
        int f = 0;
        while (f < k && used[f]) f++;
        if(f == k){
            cout << "YES\n";
            continue;
        }
        bool ans = true;
        for(int i = f; i < k; ++i){
            if(lca(p[f], p[i]) == p[i]) used[i] = true;
        }
        for(bool e: used){
            ans &= e;
        }
        ans &= d[lca(p[0], p[f])] <= d[p.back()];
        if(ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

bool multi = false;

signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (; t; --t) {
        solve();
        //cout << endl;
    }
    return 0;
}

Even cycle ends with vertex x of red [ x(Red) -> y(Blue) -> x(Red) ] Odd cycle end with vertex x of blue [ x(Red) -> w(Blue) -> z(Red)-> x(Blue)] so if x(Red) and x(Blue) which is (x,x+n) belongs to same component then odd cycle exists. Hence answer is "NO".

ll n, k; cin >> n >> k; map < ll , ll > first; map < ll , ll > last; for (int i = 1; i <= n; i++) { ll u; cin >> u; if (first[u] == 0) first[u] = i; last[u] = i; } while (k--) { ll a, b; cin >> a >> b; if (first[a] == 0 || first[b] == 0) { cout << "NO\n"; continue; } if (first[a] < last[b]) { cout << "YES\n"; } else { cout << "NO\n"; } }

#include <bits/stdc++.h> typedef long long ll; using namespace std; inline int read() { bool flag = true; char c = getchar(); if (c == '-') flag = false; while(!(c >= '0' && c <= '9')) c = getchar(); int x = 0; while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } if (flag == true) return x; return -x; } bool rem[27]; int main() { int t = read(); while (t--) { string s; cin >> s; int ans = 1, tot = 0; memset(rem, 0, sizeof(rem)); for (int i = 0; i < s.size(); ++i) { if (rem[s[i] - 'a'] == 1) continue; if (tot == 3) { memset(rem, 0, sizeof(rem)); ++ans; tot = 0; } ++tot; rem[s[i] - 'a'] = 1; } printf("%d\n", ans); } return 0; }

def solve(): inp=input() s=set() ans=0 for i in inp: s.add(i) if (len(s) > 3): ans+=1 s.clear() s.add(i) if(len(s)>0): ans+=1 print(ans) t=int(input()) while (t>0): solve() t-=1

#include <bits/stdc++.h> using namespace std; void solve() { string s; cin >> s; --s[0]; cout << stoi(s) << endl; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(nullptr); std::cout.tie(nullptr); int t; cin >> t; while(t--) solve(); }

Comments (81)

Write comment?

Raito_Yagami

11 months ago, # |

← Rev. 2 →

Problem Solved

→ Reply

canonica1

Sorry, can someone explain me, how to solve problem E with DSU and how these formulas works. I only realized that if two elements should be in different sets, the formula will be to unite(x, y + n), unite(y, x + n). And if in one then unite(x,y), unite (x + n, y + n)

freehandle

11 months ago, # ^ |

Uniting dominos sharing the same number and checking if there is a set of odd size would suffice.

epsilon_573

As Editorial said, each number must exist exactly two times, i.e. every node has exactly two edges. Graphical representation of this will be just a set of disjoint cycles. Just use DSU to check if any of the cycles is odd lengthed.

B_Consistent

0...n-1 ==> blue 
n...2n-1 ==> red

In bipartite graph each edge end (edge: x-y) should have different colors so (Blue, Red) or (Red, Blue). so we unite(x,y+n) or(x+n,y) In Bipartite odd cycle doesn't exist. since cycle must start with vertex x and end with vertex x. Lets say cycle starts with vertex x of red or vice versa and start assigning colors alternatively then if it is

why can we add an edge between the two sides of the domino, because they must be in the same component?

Lanceloia

First, if any number appears more than $$$3$$$ times, print NO. For $$$n$$$ dominoes entered, it contains $$$2n$$$ numbers. According to Pigeonhole Principle, every number appears inevitably $$$2$$$ times.

If we think of numbers as vertices (graph theory) and dominoes as edges (graph theory), the graph $$$G$$$ will be constructed by many cycle (graph theory).

Consider two dominoes $$$a=\lbrace 1, 3 \rbrace$$$ and $$$b=\lbrace 1, 4 \rbrace$$$. Because they have a common number $$$1$$$, they must be placed in different sets. Without loss of generality, we can think of $$$a$$$ as the outgoing edge and $$$b$$$ as the incoming edge. It's like we dyed the edges in Red and Blue. two different colors. In a circle (graph theory's circle), bijection from edge to point can be constructed. So we can transform the edge dyeing problem into the vertex dyeing problem.

marvalarva2929

4 months ago, # ^ |

I solved using DSU.

https://codeforces.com/contest/1702/submission/189937922

The reasoning:

If a pair {a, b} exists, then we know that another pair that contains {b, c} must be in a different set. We can visualize this by creating 2n nodes (one node if the ith pair is in the first set, and another node if the ith pair is in the second set). In my code, I used Node "a" to denote that a is in the first set, and Node "a + n" to denote that a is in the second set.

We can create 2 edges per pair. Connect {a, b + n} and {a + n, b} for every pair {a, b}. This is because if we know that "a" is in the first set, then b must be in the second set, and vice-versa.

It's easy to see that a solution only exists if Node a is not connected to Node a + n.

Video Solutions for the complete problemset.

dhaw92

Very helpful thank you!

goku20001

Problem C had anti hash test cases got accepted during contest but TLE after the hacking phase :)

Tizz1e

same problem

white_devil_403

TrendBattles

We can use priority queue to solve problem F yet the implementation is the same.

Yes

amul02

Can someone figure out which test case is giving wa https://codeforces.com/contest/1702/submission/163618387

mr.itmo

-6

Analysis of the third problem: just to start, we need to store the start and end positions of each individual number. And then we compare if the first position of a[j] is less than the last position of b[j] then the answer is YES, otherwise the answer is NO:

himanshu_3198

hey, I did the same but I used unordered_map and it showed tle but when I used map only got AC why?

aadit.ambadkar

unordered_maps are ridiculously slow in C++, and can easily be hacked to TLE. Someone must have hacked an unordered_map solution, and that hack would have made it into the test cases. map on the other hand is kinda fast (sometimes even faster than unordered_map), and will give AC because the log(n) factor doesn't impact the solution much. use map, not unordered_map, or you will be hacked

nk3

Or you can use unordered_map with a custom hash function that uses chrono::steady_clock::now().time_since_epoch().count()

Well typically this is wrapped in a mt19937 rng, but yeah you can.

thanks

savan000

thankx

M-Manas-s

10 months ago, # ^ |

Yeah, initially I too used unordered maps/sets a lot and got unexpected TLEs which is never fun. Although, in some rare cases, we don't have log(n) space. Here is a custom hash that I use when using unordered maps/sets is the only way. Hope this helps.

Custom Hash

struct custom_hash {

   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

Usage

unordered_set<int,custom_hash> _set;
unordered_map<int,int,custom_hash> _map;

quater_nion

the same thing happened with me

tushar_kumar

use of unordered_map in codeforces is an offence.

marvel_coder

← Rev. 7 →

nsharc4

Implemented Q3 as it is in the tutorial. But still getting TLE for Python Soulution. Any improvements?

https://codeforces.com/contest/1702/submission/163751004

ganesh_6

Problem F solved using 3 approaches:

Using Trie: https://codeforces.com/contest/1702/submission/163755742

Using PriorityQueue+Editorial idea: https://codeforces.com/contest/1702/submission/163692721

Storing counts of b prefixes: https://codeforces.com/contest/1702/submission/163692721

Venturo

Please explain your Trie Solution like what is the intuition.

Firstly, The initial is idea is same as editorial(make A and B array elements odd)

Secondly, the trie stores the elements of array B in bitwise fashion starting with the Most significant digit at root to Least significant digit. Here, the Trie node stores pointers to two children 0, 1, parent node and count. The count indicates the number of such bits.

Finally, when you are matching the bitwise pattern of A elements, if you find all the bits of A[i], you decrease the count of them, else the answer is No.

If you can match all the A elements with the trie return Yes

shadow9236

I solved G2 using Heavy-light Decomposition during contest. After finding both ends of the path, we can do a lazy range addition of 1 on the path between them in the HLD. Now every node in the query must have the value 1. Again range add -1 to reset the HLD.

https://codeforces.com/contest/1702/submission/163628298

NTTilted

i used hld too, but i've added 1 to every node in the query and then calculated sum on path so, if it equals to k, the answer is yes, otherwise no

electronaota

Once you find the both ends of the path you actually don't need HLD though. If a node $$$w$$$ lies on the path between $$$u$$$ and $$$v$$$ then $$$dist(u,w)+dist(w,v)=dist(u,v)$$$ so just checking this for every node in each query gonna suffice.

Lamentis

Can someone explain the dfs function of Tutorial of G1? I understand that first we precalculate each node's depth and choose the deepest node as the start point of our dfs as it will be one of the end points of our path, but I can't understand the dfs working.Thanks...

houxiang

The idea like this: Denote the set of selected vertexes as S. And we already get the start point which has deepest depth and denote it as root. And in a DFS from the root, we say a vertex is a leaf if it is selected and none of its children vertexes is selected. If the selected vertexes can build a path, we should have only one leaf if we DFS from the root. So just calculate how many leaves we have. You can check whether this submit is easier to understand: https://codeforces.com/contest/1702/submission/163945410

Maverick_31

← Rev. 4 →

Problem E:

Code

void solve(){
    int n;
    cin >> n;
    unordered_map<int,int>mp1,mp2;
    bool flag = true;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        if(a==b)    flag =false;
        if(flag){
            if(mp1.find(a)==mp1.end() && mp1.find(b)==mp1.end()){
                mp1[a]=0, mp1[b]=0;
            }
            else if(mp2.find(a)==mp2.end() && mp2.find(b)==mp2.end()){
                mp2[a]=0, mp2[b]=0;
            }
            else flag = false;
        }
    }
    if(flag){
        py;
    }
    else    pn;
}

Which case is my solution missing??

W4H1

I have followed the similar approach using set and getting W/A

SH1RO_

I got it. In this case, it dosent work. 6 (1 3) (1 4) (2 5) (2 6) (3 6) (4 5) the answer is YES, but it prints NO.

henmant

Thanx a ton dude, u saved my hours of cries!!!

Just out of curiosity how did u find or guessed about the testcase? I was just not able to convince myself that my logic is wrong XD...

Actually, it also confused me hours and I cant find the loical wrong at first. Finally, I casually found we shouldnt classify a pair to setA or setB if the two nums of the pair both didnt appear even once in setA or setB. Sometimes if a pair can both go to setA or setB, you shouldnt randomly put them in one of them. You have to skip and deal with them later. So the sequence to deal with the pairs is important. Which pair you should deal with first is the pair that only appeared once in both set. It will be put into the set that didnt inclued the same num and the classification is definitely not ramdomly. Hope it will help you :) I am not good at English:p

makes complete sense, thanx again ^_^

I used stl set and did the same things as you.W/A on test 2

llc5pg

Your answer is NO.

Now if we swap the order of input to:

Then, now your answer is YES.

Yep:)

tgp07

solved g1 later since I didn't have time to do in the contest. just bashed it with lca 163805347

Same

dio_2

Can somone please explain to me why when using unordered_map I get TLE and when changed to a normal map it just get accepted.

hermes999

Because a hash table should only store unique data, if there is more data that is repeated its complexity is O(n), you can search for it as collisions in hash tables

xsc

← Rev. 3 →

I solved Problem G2 without LCA. https://codeforces.com/contest/1702/submission/164039469

164039469

Edlue

I wanted to mention that F appeared in a recent AtCoder contest: https://atcoder.jp/contests/abc254/tasks/abc254_h

sprudra5001

Hey Edlue Can You help where my approach went wrong in problem F ? My basic idea was to reduce every number in array A and B to their largest odd factors (by dividing them 2 as long as possible) and store the values in two different multisets.
First multiset contains all reduced values of array A.
The second multiset contains all the reduced values present in array B. Then I would simply iterate over the second multiset and for each value in this multiset I will check if there is a matching value in first multiset.
If yes then I will delete that value from first multiset else I will further reduce this element further by 2 and again try to match with first multiset as long as this element is > 0. >br> After iterating over all values of 2nd multiset, if first multiset is empty then my answer is YES, otherwise it is NO.

UPDATE : I figured out the issue, which was due to continue statement in one of my while loops.
My wrong submission here

TheAlgorist

Hello,

In problem E, is it obligatory that the two sets must have equal size. If yes, where is problem statement this is written?

Thank you :)

tezk

There are $$$n$$$ dominos with value from $$$1$$$ to $$$n$$$.

If each number appear exactly twice, both sets must contain all number from $$$1$$$ to $$$n$$$, thus have the size of $$$\frac{n}{2}$$$

Edit : the size is $$$n$$$, not $$$\frac{n}{2}$$$, my bad

Thank you for your answer.

Deeppandya04

Each number from 1 to n appears twice. So, the size of each set is n.

Sigh

My solution to G2 with dfs and range query data structure(BIT for example):

First get the pre-order sequence of the tree, store the time stamp when you enter/exit each node.

For each query, find the node X with max depth, and node Y with min depth.

As described in the solution, X must be one end of the path. Let's enumerate the other end.

We put +1 on the timestamp you enter each node, and range_sum(X,Y) gives us the number of points covered by path X-Y.

Now we enumerate each node Z in the set, skip it if it's on path X-Y(can be determined by timestamp), otherwise see if range_sum(X,Y) + range_sum(Y,Z) = |S| + 1.

Another_Alt_123

What is |S| at the end? Please tell.

Voga

In problem F, why do we have to take the largest number from array b? The solutions works even if we take random number from b.

Qualified

I would assume that it would be easier to just start from the largest number. Do you have a proof as to why it would still work even if we just take a random number from b?

I think you start with a larger number, because in the worst case that you divide it, you could still use it for smaller numbers. That's much more efficient than taking smaller numbers, because you don't know if you'll be able to use them again.

tgp07 Can You help where my approach went wrong in problem F ? My basic idea was to reduce every number in array A and B to their largest odd factors (by dividing them 2 as long as possible) and store the values in two different multisets.
First multiset contains all reduced values of array A.
The second multiset contains all the reduced values present in array B. Then I would simply iterate over the second multiset and for each value in this multiset I will check if there is a matching value in first multiset.
If yes then I will delete that value from first multiset else I will further reduce this element further by 2 and again try to match with first multiset as long as this element is > 0. >br> After iterating over all values of 2nd multiset, if first multiset is empty then my answer is YES, otherwise it is NO.

UPDATE : I figured out the issue, which was due to continue statement in one of my while loops.
The wrong submission here

Nice

Nxxlt

Can u explain why Graph solution for Problem E works?

parmarsupermacy

10 months ago, # |

Can anyone provide me better and easy solution for the 1702B. Thank You...

zhaoxi_zheng

Hello sir.

This is muy solution to 1702B.

We can travel though the hole string, and use $$$ans$$$ to add up the sum of the days, and use $$$tot$$$ to add up how many letters Polycarp has remembered today.

Another array $$$rem_x$$$ is used to mark if the letter is remebered.

When $$$tot == 3$$$, this means he should use at least one more day, so we can ++ans.

When a new letter is remembered today, he don't have to remember it again, otherwise, ++tot.

Note that: please remember to clear $$$rem$$$ when '++ans'.

My code:

-10

In the editorial of problem G why are we doing return go(now) + 1; ?

HNOONa

problem E,

after checking that no node with degree >= 3

there can be no paths in the graph, only cycles, correct?

apjcoder123

Can someone please explain the reason why it is written in the editorial of problem E that each set will consist of n numbers ?

here is proof by contradiction suppose 2 sets A, B form a valid partition && set A has < n numbers

then we at least have an extra pair of numbers that is in set B (an edge) && also the rest of the numbers that are not in A go in B, so we have set A has <= n-2 numbers && set B has >= n+2 numbers

but note that we have at most n distinct numbers, so by pigeon hole principle, with n + 2 numbers in set B, we are guaranteed a duplicate, hence this isn't a valid partition, so what we assumed at first is wrong

so each set must have exactly n numbers

Okay thanks got it.

In problem E, can we consider a Domino as a node and and if two Dominoes have same integer then we can make an edge between them.

samir2201

include <bits/stdc++.h>

using namespace std;

int main() { //900000000 int t; cin >> t; while (t--) { long long int a; cin >> a; int x = 0; while (a > pow(10, x+1)) { x++; } cout << a — pow(10, x) << endl; }

return 0;

}

Why is this code not working for 999999999 only else its working fine

Opyop

Average round

a-ma-n

9 months ago, # |

python solution for problem B

saketkumarsingh

5 months ago, # |

can someone tell at which test case my code for E fails 186018543

mridulpandeycr7

4 months ago, # |

In problem F,once we make each element odd in multiset a, then I think it is not necessary to start with largest element in multiset b, we can start with smallest element too since we use only second operation in multiset b.

Cason_chen

3 months ago, # |

196340494 For G2 I first find the start point and the end point, and then search the point set with both in the collection to determine whether the distance is greater than the distance from the start point to the end point. Why is it timeout?

Vologhat

Hello, guys. I'm the beginner on codeforces and it's my first post. So, I want to propose my own solution for problem A:

As stated in the answer by Mike Mirzayanov, in order to get the difference between the number m and the nearest round number < m, we need to compose that round number. So, this is a good idea, but I found another way. So, after subtraction, d differs from m by the first digit. So we can read the input data as a string and decrement the index of the first character by one. And if the first character was '1', then the string-to-number builtins will ignore insignificant zero.

Vladosiya's blog

include <bits/stdc++.h>