Codeforces Round #925 (Div. 3) Разбор

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

1931A - Восстановление маленькой строки

Идея: myav Разработка: myav

Разбор

Решение

#include<bits/stdc++.h>
using namespace std;
 
 
void solve(){
    int n, sz = 26;
    cin >> n;
    string mins = "zzz", cur;
    for(int i = 0; i < sz; i++){
        for(int j = 0; j < sz; j++){
            for(int k = 0; k < sz; k++){
                if(i + j + k + 3 == n){
                    cur += char(i + 'a');
                    cur += char(j + 'a');
                    cur += char(k + 'a');
                    mins = min(cur, mins);
                }
            }
        }
    }
    cout << mins << "\n";
 
}
int main(){
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

1931B - Сделай равными

Идея: MikeMirzayanov Разработка: Vladosiya

Разбор

Решение

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    k = sum(a) // n
    for i in range(n - 1):
        if a[i] < k:
            print('NO')
            return
        a[i + 1] += a[i] - k
        a[i] = k
    print('YES')
    
    
for _ in range(int(input())):
    solve()

1931C - Снова сделай равными

Идея: ibraevdmitriy Разработка: ibraevdmitriy

Разбор

Решение

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    i1 = 0
    i2 = 0
    while i1 < n and a[i1] == a[0]:
        i1 += 1
    while i2 < n and a[n - i2 - 1] == a[n - 1]:
        i2 += 1
    res = n
    if a[0] == a[n - 1]:
        res -= i1
        res -= i2
    else:
        res -= max(i1, i2)
    print(max(0, res))
 
 
t = int(input())
 
 
for i in range(t):
    solve()

1931D - Делимые пары

Идея: MikeMirzayanov Разработка: Vladosiya

Разбор

Решение

def solve():
    n, x, y = map(int, input().split())
    a = [int(x) for x in input().split()]
    cnt = dict()
    ans = 0
    for e in a:
        xx, yy = e % x, e % y
        ans += cnt.get(((x - xx) % x, yy), 0)
        cnt[(xx, yy)] = cnt.get((xx, yy), 0) + 1
    print(ans)
    
    
for _ in range(int(input())):
    solve()

1931E - Аня и подарок на День святого Валентина

Идея: Gornak40 Разработка: Gornak40

Разбор

Решение

#include <bits/stdc++.h>
 
#define all(arr) arr.begin(), arr.end()
 
using namespace std;
 
const int MAXN = 200200;
 
int n, m;
string arr[MAXN];
int len[MAXN], zrr[MAXN];
 
void build() {
    memset(zrr, 0, sizeof(*zrr) * n);
    for (int i = 0; i < n; ++i) {
        len[i] = arr[i].size();
        for (auto it = arr[i].rbegin(); it != arr[i].rend() && *it == '0'; ++it) {
            ++zrr[i];
        }
    }
}
 
string solve() {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += len[i] - zrr[i];
    }
    sort(zrr, zrr + n);
    reverse(zrr, zrr + n);
    for (int i = 0; i < n; ++i) {
        if (i & 1) ans += zrr[i];
    }
    return (ans - 1 >= m ? "Sasha" : "Anna");
}
 
int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
            cin >> arr[i];
        build();
        cout << solve() << '\n';
    }
}

1931F - Скриншоты чата

Идея: ibraevdmitriy Разработка: ibraevdmitriy

Разбор

Решение

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
int timer = 0;
 
void dfs(int v, vector<vector<int>> &g, vector<bool> &vis, vector<int> &tout) {
    vis[v] = true;
    for (int u: g[v]) {
        if (!vis[u]) {
            dfs(u, g, vis, tout);
        }
    }
    tout[v] = timer++;
}
 
void solve() {
    timer = 0;
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(k, vector<int>(n));
    vector<int> authors(k);
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
            a[i][j]--;
        }
        authors[i] = a[i][0];
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < k; ++i) {
        for (int j = 1; j + 1 < n; ++j) {
            int i1 = a[i][j], i2 = a[i][j + 1];
            g[i1].push_back(i2);
        }
    }
    vector<int> tout(n, -1);
    vector<bool> vis(n);
    for (int i = 0; i < n; ++i) {
        if (tout[i] == -1) {
            dfs(i, g, vis, tout);
        }
    }
    for (int i = 0; i < k; ++i) {
        for (int j = 1; j + 1 < n; ++j) {
            int i1 = a[i][j], i2 = a[i][j + 1];
            if (tout[i1] < tout[i2]) {
                cout << "NO";
                return;
            }
        }
    }
    cout << "YES";
}
 
int main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
        cout << "\n";
    }
}

1931G - Одномерный пазл

Идея: ibraevdmitriy Разработка: ibraevdmitriy

Разбор

Решение


#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
const int mod = 998244353;
 
ll pow_mod(ll x, ll p) {
    if (p == 0) {
        return 1;
    }
    if (p % 2 == 0) {
        ll y = pow_mod(x, p / 2);
        return (y * y) % mod;
    }
    return (x * pow_mod(x, p - 1)) % mod;
}
 
ll inv(ll x) {
    return pow_mod(x, mod - 2);
}
 
vector<ll> fact = {1};
 
ll cnk(ll n, ll k) {
    ll res = fact[n];
    res = (res * inv(fact[k])) % mod;
    res = (res * inv(fact[n - k])) % mod;
    return res;
}
 
ll calc(int n1, int n2, int n3, int n4) {
    return (cnk(n1 + n3 - 1, n3) * cnk(n2 + n4 - 1, n4)) % mod;
}
 
void solve() {
    int n1, n2, n3, n4;
    cin >> n1 >> n2 >> n3 >> n4;
    if (n1 + n2 == 0) {
        cout << (n3 == 0 || n4 == 0 ? 1 : 0) << '\n';
        return;
    }
    if (abs(n1 - n2) > 1) {
        cout << "0\n";
        return;
    }
    ll res = 0;
    if (n1 <= n2) {
        res += calc(n1 + 1, n2, n3, n4);
    }
    if (n2 <= n1) {
        res += calc(n1, n2 + 1, n3, n4);
    }
    cout << res % mod << '\n';
}
 
int main() {
    for (ll i = 1; i <= 4e6; ++i) {
        fact.push_back((fact.back() * i) % mod);
    }
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
}

sort(trailnums.begin(), trailnums.end(), [&](pair<long long int, long long int> a, pair<long long int, long long int> b) { return to_string(a.first).length() < to_string(b.first).length(); });

#include <bits/stdc++.h> using namespace std; typedef long long ll; void solve(){ int n,x,y; cin >> n >> x >> y; vector<int> a(n); for(int i=0; i<n; i++){ cin >> a[i]; } vector<int> mod_x = a; vector<int> mod_y = a; for(int i=0; i<n; i++){ mod_x[i] %= x; mod_y[i] %= y; } for(int i=0; i<mod_x.size(); i++){ if(mod_x[i]>(x/2)) mod_x[i] = mod_x[i]-x; //if(temp[i]==(x/2)&&(x%2==0)) ct++; } unordered_map<int,vector<int>> m; ll ans = 0; for(int i=0; i<n; i++){ m[mod_y[i]].push_back(mod_x[i]); } for(auto it: m){ vector<int> temp = it.second; ll ct1 = 0; ll ct2 =0; for(int i=0; i<temp.size(); i++){ if(temp[i]==0) ct2++; if(temp[i]==(x/2)&&(x%2==0)) ct1++; } unordered_map<int, pair<int,int>> m1; for(int i=0; i<temp.size(); i++){ if(temp[i]>0) m1[temp[i]].first++; else m1[abs(temp[i])].second++; } for(auto i: m1){ ans += (i.second.first)*(i.second.second); } if(ct1>0) ans += (ct1*(ct1-1))/2 ; if(ct2>0) ans += (ct2*(ct2-1))/2 ; } cout << ans << endl; } int main() { // your code goes here int t; cin >> t; while(t--) solve(); }

Комментарии (70)

Показать архивные | Написать комментарий?

Wasif_Shahzad

2 года назад, скрыть # |

Can anyone explain why for Problem. F this submission gets TLE.

246345877

and this submission gets accepted?

246347175

I don't feel like there's any difference in logic, just the way of implementation is different.

→ Ответить

VitaliiV

2 года назад, скрыть # ^ |

← Rev. 8 →

In the second submission there is an optimization of the DFS function: do not run a search if the vertex has already been visited

My submissions:

246247300

246250491

You can see the difference more clearly here

are you talking about the external dfs optimization from main function or internal dfs optimization?

I mean the lines

le(i, 1, n){
			if(!vis[i]){
				if(dfs(i)){
					cout << "NO" << endl;
					flg = 1;
					break;
				}
			}
		}

	for(auto c: graph[v]){
		if(dfs(c)){
			return true;
		}
	}

le(i, 1, n){ if(!vis[i]){ if(dfs(i)){ cout << "NO" << endl; flg = 1; break; } } } I'm talking about this

How can this be the issue? can I get explanation? Won't the if(!vis[i]) take care of it?

← Rev. 4 →

DELETED

robostac

In the TLE submission your first loop (to clear graph / vis / dfsStack) will run 10000(t) * 200005(NxM) operations. The accepted one only clears the memory needed for each test case.

gubidubi

In the second submission the graph is a array of sets, so when you insert a repeated edge it doesn't get duplicated. In the first submission you are duplicating a lot of edges (because you are pushing them in a vector), and going through all of them during the dfs.

I'm wrong, this still would not cause TLE (the total amount of edges over all tests is less than 2*10⁵), robostac gave the right answer.

jkulanko

A different way to do F:

Each element (after the 0th element in the kth list) can only be it's current position or its current position+1
Store both possibilities in a vector
Remove possibilities for elements when they're no longer possible (i.e. the current element's position in the kth list conflicts with the elements position in a previous list)
The answer is no if an element has no possibilities, or if its only possibility conflicts with another elements only possibility
Otherwise the answer is yes

Code: https://mirror.codeforces.com/contest/1931/submission/246250979

How was my solution hacked? https://mirror.codeforces.com/contest/1931/submission/246212609

I see it was probably due to collisions in the map but does that mean I need a better hashing function for pairs? If so can someone suggest one?

https://mirror.codeforces.com/blog/entry/62393

The other option is you can almost always use set / map in c++ as any attempt to use unordered with a custom hash will often have enough constant overhead to be about the same overall time.

martin0327

Using hash map in this problem is a bad idea. Still, you may want to read the following:

and_t

← Rev. 3 →

can somebody help me understand why this solution got TLE Problem D

lucasap

I think it is because of s.count( {cx,cy} ), that is not O(1) but O(count_of({cx,cy}) + log(N)), so worst case in an array with all ones and x=2, you get O(N^2) time complexity. I think in C++ you should be going for a unordered_map<pair<int,int>, int> in which the values are the count so you can do the addition in O(1).

Jx07

21 месяц назад, скрыть # ^ |

hey i am facing the same problem getting tle in my code idk how ? Can you help me 269843884

namasteforcesfromyogesh

2 месяца назад, скрыть # ^ |

if( cx==a[i]%x and cy==a[i]%y )ans--;

Hey bro, two distinct no's can yield same {cx,cy}, won't the above line remove the that aswell including the selfpairs?

polsage

Hey, I have submitted a java code for problem C but it gave me error on test case 3 whereas when i submitted the exact same code in c++ it passed all test cases why

java link: https://mirror.codeforces.com/contest/1931/submission/246230264

c++ link: https://mirror.codeforces.com/contest/1931/submission/246276255

WORTH

Don't use $$$==$$$ for comparing Integer

Read this.)

ooooh my god thank you

your dp shows my pain

matislu

In G we don't need to calculate factorials to $$$4 \times 10^6$$$ since the biggest factorial we need in combinations is actually $$$2 * max(c_{i}) \leq 2 \times 10^6$$$

iu_vk_linh

i think something wrong in solution code of problem A ._.

Forestmy17

Thanks for good Round. Good F

zc2707

Why D's solution is correct? It uses a hash table (dict), so is it possible to hack this hash table?

0x3F

Video explanation of Problem G (Chinese)

FTS_Problem_C

Nice problems , had fun solving them

I really hope more rounds like this exist

DR_Zain

why the code of problem A uses the string cur outside loop so I think this isn't true; please anyone can review it?

m_nature

It's correct because the first triples that it finds is guaranteed to be the minimum, so everything after that affecting the cur variable doesn't matter

(That also means it doesn't need to continue the loop to find the minimum here and can return immediately when it finds the first triples)

But I agree that appending to the cur variable after that is definitely unnecessary and the logic is also wrong IF the minimum is not the first triples lol)

second_saturday

I still don't understand anything in G, can someone please explain me

han_hyo_joo

← Rev. 2 →

This was my thought process when upsolving G.

The main observation needed is to notice that 1 + 3 = 1 and 2 + 4 = 2, so we can condense all 3 and 4 pieces. However, it is possible to start the sequence with a 3 or 4 piece, so for this reason we can imagine having an "extra" 1 or 2, respectively. Now there are a few cases:

No correct puzzle sequence can have consecutive 1's or 2's, so if $$$ |c_1 - c_2| \gt 1 $$$, the answer is 0.
If $$$ c_1 = c_2 = 0 $$$, the answer is 1 if $$$ c_3 = 0 $$$ and/or $$$ c_4 = 0 $$$ and 0 otherwise. This is true because 3 cannot mesh with 4.
If $$$ c_1 = c_2 $$$ and $$$ c_1, c_2 \gt 0 $$$, either 1 or 2 can be used to start the puzzle sequence, so we can fix the first number and calculate the rest of the sequence. Counting the # of ways to condense $$$ c_3 $$$ 3 pieces into $$$ c_1 + 1 $$$ 1 pieces is the same as counting the # of ways to put $$$ c_3 $$$ indistinguishable balls into $$$ c_1 + 1 $$$ boxes, which is $$$ \binom{c_1 + c_3}{c_1} $$$ (this can be visualized with the stars and bars technique). Note that 1 is added to $$$ c_1 $$$ for that "extra" piece, if we fix 1 to be the first puzzle. As such, the answer is $$$ = \binom{c_1 + c_3 - 1}{c_1 - 1} \cdot \binom{c_2 + c_4}{c_2} + \binom{c_1 + c_3}{c_1} \cdot \binom{c_2 + c_4 - 1}{c_2 - 1} $$$
If $$$ c_1 = c_2 + 1 $$$ or $$$ c_1 + 1 = c_2 $$$, then we are required to fix either 1 or 2 to be the first piece, respectively. Then it's the same exact idea as the previous case

phukaoz

why my solution TLE on system test.
is unordered_map of unordered_map took significantly more time to find than unordered_map that pair as key?

Akshay184

Can some one explain the approach for problem G in detail?

the_hyp0cr1t3

+11

Problem G:

Let the four types be denoted by $$$\color{purple}{b_1}$$$, $$$\color{blue}{b_2}$$$, $$$\color{olive}{b_3}$$$ and $$$\color{teal}{b_4}$$$ respectively.

Lemma 1: Between any two $$$\color{purple}{b_1}$$$, there must be at least one $$$\color{blue}{b_2}$$$. It is easy to see that one cannot fit only $$$\color{olive}{b_3}$$$ and/or $$$\color{teal}{b_4}$$$ between two $$$\color{purple}{b_1}$$$.

Lemma 2: Between any two $$$\color{blue}{b_2}$$$, there must be at least one $$$\color{purple}{b_1}$$$. It is easy to see that one cannot fit only $$$\color{olive}{b_3}$$$ and/or $$$\color{teal}{b_4}$$$ between two $$$\color{blue}{b_2}$$$.

It follows that between any two $$$\color{purple}{b_1}$$$, there must be exactly one $$$\color{blue}{b_2}$$$. Likewise, between any two $$$\color{blue}{b_2}$$$, there must be exactly one $$$\color{purple}{b_1}$$$. In other words, they must follow an alternating pattern $$$\color{purple}{b_1}, \color{blue}{b_2}, \color{purple}{b_1}, \color{blue}{b_2}, \ldots$$$ or $$$\color{blue}{b_2}, \color{purple}{b_1}, \color{blue}{b_2}, \color{purple}{b_1}, \ldots$$$, with possibly some $$$\color{olive}{b_3}$$$ and $$$\color{teal}{b_4}$$$ in between.

Lemma 3: If a block exists to the left of a $$$\color{olive}{b_3}$$$, it must either be another $$$\color{olive}{b_3}$$$ or a $$$\color{purple}{b_1}$$$. If a block exists to the right of a $$$\color{olive}{b_3}$$$, it must either be another $$$\color{olive}{b_3}$$$ or a $$$\color{blue}{b_2}$$$.

Lemma 4: If a block exists to the left of a $$$\color{teal}{b_4}$$$, it must either be another $$$\color{teal}{b_4}$$$ or a $$$\color{blue}{b_2}$$$. If a block exists to the right of a $$$\color{teal}{b_4}$$$, it must either be another $$$\color{teal}{b_4}$$$ or a $$$\color{purple}{b_1}$$$.

Putting everything together, any valid arrangement will be of the form

$$$\{\color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \ldots\}$$$ or
$$$\{\color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \ldots\}$$$

For such an arrangement to exist, it must hold that $$$\mathrm{abs}(c_1 - c_2) \leq 1$$$. Then, the number of valid arrangements is the number of ways to arrange $$$\color{olive}{b_3}$$$ and $$$\color{teal}{b_4}$$$ into the 'slots' between alternating $$$\color{purple}{b_1}$$$ and $$$\color{blue}{b_2}$$$. This can be done using the stars and bars technique.

Submission: 246362383

ShreyHehe

Nicely Explained, Thank You!

i3mr125

what are the prequesites for G . I didn't understand anything, and why am i still green and i hit the 1400 mark

Topic wise, you only need to know the "stars and bars" combinatorics concept. You can read about it here: https://cp-algorithms.com/combinatorics/stars_and_bars.html.

ooh yeah thank you so much , i am not very good at combinatorics so i guess that's why i am not familiar with it. i will definitely look in to it thanks

CodeFlexer

For the problem F, I do understand why existence of topological sort (and therefore absence of cycles) of such graph is necessary condition for existence of the order. However, why is it sufficient? I.e. What is exact proof that absence of cycles guarantee that such order of chat participants exists?

UzuHa_NaruSuke

If there are no cycles in the directed graph that means that you can run the topological sort algorithm on it.

The correct sequence will be the sequence after we topologically sort it as it will be satisfying all the conditions ie all the edges in the graph are not forming a cycle.

Therefore it is enough to no if we can topologically sort the graph or no ie check for any directed cycles.

Ylandolsi

Video Solution for problemD : https://www.youtube.com/watch?v=FPRiSmmyfiE

minion30031

Can someone please figure out what the mistake with my submission is? Any help is appreciated. https://mirror.codeforces.com/contest/1931/submission/246419122

AkiLotus

I think this part is the issue. You are sorting the numbers with trailing zeros by their absolute lengths in increasing order (instead of their numbers of trailing zeros in decreasing order). Seems like test #2 was only of integers from 1 to 10, thus this solution will be automatically be correct for just that case (but not when the integers are higher).

For example: 4000000 should be prioritized more than 711100 since it has 6 trailing zeros (compared to 2 of 711100), but your sorting will make 711100 stand first.

Hi AkiLotus, I also tried that approach before using the number of trailing zeros in decreasing order:

Submission:https://mirror.codeforces.com/contest/1931/submission/246418992

But even that does not seem to work.

Appreciate your effort in looking into my code.

Thanks

I see now. The remtrail function isn't correct either, specifically this part.

    string ans = "";
    for(int i=0;i<n;i++) {
        if(s[i] == '0') break;
        else {
            ans += s[i];
        }
    }

Take a guess of what the output of remtrail(170011000) would be with this code. Correct answer is supposed to be 170011.

Spoiler (open only when you figured out the bug)

nikich340

From tutorial D: Since (ai + aj) mod x = 0, it follows that (ai mod x + aj mod x) mod x = 0. Since (ai − aj) mod y = 0, it follows that ai mod y − aj mod y = 0.

Quite not clear, how it follows, and why it's not (ai mod y − aj mod y) mod y = 0 for 2nd case then.

RedDreams

$$$

0\ \le\ ai\ mod\ y\ \le\ y-1 \newline

0\ \le\ aj\ mod\ y\ \le\ y-1 \newline

-(y-1)\ \le\ (ai\ mod\ y − aj\ mod\ y)\ \le y-1 $$$

So if $$$\ (ai\ mod\ y − aj\ mod\ y)\ mod\ y = 0$$$

Then $$$\ (ai\ mod\ y − aj\ mod\ y) = 0$$$

Solution for D without hash:

We need to count number of pairs equal with respect to $$$(mod\ y)$$$ and sum of which equal to $$$0$$$ with respect to $$$(mod\ x)$$$.

For each $$$a[i]$$$ store pair $$$ \{ a[i] (mod\ y), a[i] (mod\ x) \} $$$. Sort array of pairs.

Now pairs can be divided into continuous blocks of numbers equal with respect to $$$(mod\ y)$$$. And inside each block elements are sorted by their $$$(mod\ x)$$$.

So inside each block we can count number of pairs which add up to $$$0$$$ with respect to $$$(mod\ x)$$$ using 2 pointers in $$$O(n)$$$.

Complexity of solution $$$O(n * log(n))$$$. (Because of sorting)

My submission 246421822

YashVashisht

11 месяцев назад, скрыть # ^ |

Good using Chatgpt, I asked chatgpt for the same and got the same code, no changes in conditions!!

I don't get what you are trying to say. You asked chat gpt for the same algo and it gave you same code as mine?

LNight121

In Problem D,when i use unordered_map,i got TLE on test 30.But if use map,this test only need 70ms.Is this intentional design by the author？

The unordered map uses a certain hashing algorithm and the author has put in testcases that cause collisions to it.

You can read this for more information.

So answering your question, yes it is intentional design by the author as the testcases are set in such a way.

Jagnath_Reddy

why tle? D link

saisumanchitturi

int arr [][]= new int [ x ][ y ];

Constraints: $$$1 \le x, y \le 10^9$$$

You can't just create such a big matrix.

parag776

in G, why do we need this condition? It is guaranteed that the sum of ci for all test cases does not exceed 4⋅1000000.

not_a_failure

Getting RUNTIME_ERROR (Exit code is -1073741819) on large inputs for this solution https://mirror.codeforces.com/contest/1931/submission/246676323 for Problem E. Does anyone know what am I doing wrong here?

1xx55

I tested your code and I think error occured when you sort vector b.

This is an AC submission based on your code. 247704863

I don't know what wrong on your code too (maybe Segment fault?).You can make some further study.

Mr.Hakimov

thanks for the problem E! really enjoyed solving it :)

Jerry_H

Can G use dp?

Isaac_Newton__

In E can somebody explain why have we used ans -1 instead of ans.

ans : the amount of digits that we have in final number.

but how many digits does $$$10^m$$$ have ? It's $$$m+1$$$.

So we need to check if ans >= m+1 ,ans it's the same as ans-1 >= m.

jafirislam10

1931C can anyone tell me there is i>=1 that means first index of the array is not changeable in order to make the whole array equal . all the other elements of array needs to be equal as first index isn't it ?

select three integers i, j, x(1≤i≤j≤n)

I think array index range from 1 to n , not 0 to n-1 , and it's ok. first element's index is 1.

IAWNMW

19 месяцев назад, скрыть # |

Whenever i will be asked for quality,i would reply 1931F

TheArcticWolf

18 месяцев назад, скрыть # |

Another approach for F

For every pair of screenshot with the 1st screenshot, iterate through elements of both the screenshots , except the first one and try to form the parent pattern from which it could have been made for these two users. If finally you could get a pattern n-1 times, you can say it is possible else not.

Only 3 cases would arise while iterating , either

a[i] equals b[i] ,
a[i] or/and b[i] equal to the beginning of screenshot i.e the user itself ,
a[i] and b[i] being different and unequal to starting user.

Ofc , a is always the first row and b would change as the consecutive rows after that.

Have a look at my submission: 286579692

harshalg051007

9 месяцев назад, скрыть # |

Why is My submission wrong??

sathyamk

4 месяца назад, скрыть # |

I guess problem E can be solved using simple observation and little greedy thinking like if we think in an Anna way where she will try to reduce the sum of length a[i] and Sasha will try to do opposite where she will try to minimize the Anna's work. I can explain that with an example...

4 10 1 2007 800 1580

so total digit is 11 => len(2007) = 4 Now, first move anna will make where she will try to maximize the reduction of digit so 800 => 008 => 8 Anna : 1 2007 8 1580 now total digit is 11-2 = 9 Sasha : 1 8 15802007 after this Anna cannot reduce the digit so Sasha will concatenate a[i] and a[j]

so Anna will win because total digit = 9 which is not > m

you can try other example too

355043878

Aritro_

2 месяца назад, скрыть # |

Problem F can be solved with implementation: [submission:https://mirror.codeforces.com/contest/1931/submission/323661770] don't know why I didn't have the idea of topological sort tho

Блог пользователя Vladosiya