Разбор Educational Codeforces Round 127

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Разбор

Решение (BledDest)

t = int(input())
for i in range(t):
    s = input()
    ans = True
    n = len(s)
    for j in range(n):
        if (j == 0 or s[j] != s[j - 1]) and (j == n - 1 or s[j] != s[j + 1]):
            ans = False
    print('YES' if ans else 'NO')

1671B - Отрезок последовательных точек

Идея: vovuh

Разбор

Решение (vovuh)

for i in range(int(input())):
    n = int(input())
    x = list(map(int, input().split()))
    print('YES' if x[-1] - x[0] - n + 1 <= 2 else 'NO')

1671C - Dolce Vita

Идея: vovuh и BledDest

Разбор

Решение (adedalic)

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, x) = readLine()!!.split(' ').map { it.toInt() }
        val a = readLine()!!.split(' ').map { it.toInt() }.sorted()

        var sum = a.sumOf { it.toLong() }
        var prevDay = -1L
        var ans = 0L
        for (i in n - 1 downTo 0) {
            val curDay = if (x - sum >= 0) (x - sum) / (i + 1) else -1
            ans += (i + 1) * (curDay - prevDay)
            prevDay = curDay
            sum -= a[i]
        }
        println(ans)
    }
}

1671D - Вставь прогрессию

Идея: vovuh и BledDest

Разбор

Решение (awoo)

#include <bits/stdc++.h>

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

using namespace std;


int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, x;
        scanf("%d%d", &n, &x);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        long long ans = 1e18;
        long long cur = 0;
        forn(i, n - 1){
            cur += abs(a[i] - a[i + 1]);
        }
        forn(_, 2){
            long long mn = abs(a[0] - 1);
            ans = min(ans, cur + abs(a[0] - x) + (x - 1));
            forn(i, n - 1){
                ans = min(ans, cur + mn - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - x));
                ans = min(ans, cur - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - 1) + (x - 1));
                mn = min(mn, 0ll - abs(a[i] - a[i + 1]) + abs(a[i] - 1) + abs(a[i + 1] - 1));
            }
            ans = min(ans, cur + mn + abs(a.back() - x));
            reverse(a.begin(), a.end());
        }
        printf("%lld\n", ans);
    }
    return 0;
}

1671E - Прямой обход

Идея: BledDest

Разбор

Решение (BledDest)

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

mt19937 rnd(42);

const int MOD = 998244353;
const int K = 3;

int add(int x, int y, int mod = MOD)
{
    x += y;
    while(x >= mod) x -= mod;
    while(x < 0) x += mod;
    return x;
}   

int sub(int x, int y, int mod = MOD)
{
    return add(x, -y, mod);
}   

int mul(int x, int y, int mod = MOD)
{
    return (x * 1ll * y) % mod;
}

int binpow(int x, int y, int mod = MOD)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x, mod);
        y /= 2;
        x = mul(x, x, mod);
    }   
    return z;
}

bool prime(int x)
{
    for(int i = 2; i * 1ll * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;    
}   

int get_base()
{
    int x = rnd() % 10000 + 4444;
    while(!prime(x)) x++;
    return x;
}   

int get_modulo()
{
    int x = rnd() % int(1e9) + int(1e8);
    while(!prime(x)) x++;
    return x;
}   

typedef array<int, K> hs;

hs base, modulo;

void generate_hs()
{
    for(int i = 0; i < K; i++)
    {
        base[i] = get_base();
        modulo[i] = get_modulo();
    }
}   

hs operator+(const hs& a, const hs& b)
{
    hs c;
    for(int i = 0; i < K; i++)
    {
        c[i] = add(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs operator-(const hs& a, const hs& b)
{
    hs c;
    for(int i = 0; i < K; i++)
    {
        c[i] = sub(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs operator*(const hs& a, const hs& b)
{
    hs c;
    for(int i = 0; i < K; i++)
    {
        c[i] = mul(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs operator^(const hs& a, const hs& b)
{
    hs c; 
    for(int i = 0; i < K; i++)
    {
        c[i] = binpow(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs char_hash(char c)
{
    hs res;
    for(int i = 0; i < K; i++)
        res[i] = c - 'A' + 1;
    return res;
}

const int N = 18;
const int V = 1 << N;
string s;
char buf[V + 43];
int n;
int ans[V + 43];
hs vertex_hash[V + 43];

bool is_leaf(int x)
{
    return (x * 2 + 1) >= ((1 << n) - 1);
}

void rec(int x)
{
    vertex_hash[x] = char_hash(s[x]);
    ans[x] = 1;
    if(is_leaf(x)) 
    {
        return;
    }
    rec(x * 2 + 1);
    rec(x * 2 + 2);
    vertex_hash[x] = vertex_hash[x] + (base ^ vertex_hash[2 * x + 1]) + (base ^ vertex_hash[2 * x + 2]);
    ans[x] = mul(ans[2 * x + 1], ans[2 * x + 2]);
    if(vertex_hash[2 * x + 1] != vertex_hash[2 * x + 2])
        ans[x] = mul(ans[x], 2);
}
 
int main() 
{
    generate_hs();
    scanf("%d", &n);
    scanf("%s", buf);
    s = buf;
    rec(0);
    cout << ans[0] << endl;
}

1671F - Подсчет перестановок

Идея: BledDest

Разбор

Решение (BledDest)

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

const int K = 13;
const int MOD = 998244353;

int n, k, x;

int cnt[K][K][K];
int dp[K][2 * K][K][K];

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   

int sub(int x, int y)
{
    return add(x, -y);
}   

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        y /= 2;
        x = mul(x, x);
    }   
    return z;
}

void precalc()
{
    cnt[2][1][1] = 1;
    cnt[3][1][2] = 2;
    cnt[3][2][3] = 1;
    cnt[4][1][3] = 3;
    cnt[4][1][4] = 1;
    cnt[4][2][3] = 1;
    cnt[4][2][4] = 4;
    cnt[4][2][5] = 3;
    cnt[4][3][6] = 1;
    cnt[5][1][4] = 4;
    cnt[5][1][5] = 2;
    cnt[5][1][6] = 2;
    cnt[5][2][4] = 4;
    cnt[5][2][5] = 12;
    cnt[5][2][6] = 12;
    cnt[5][2][7] = 9;
    cnt[5][2][8] = 3;
    cnt[5][3][5] = 2;
    cnt[5][3][6] = 4;
    cnt[5][3][7] = 6;
    cnt[5][3][8] = 6;
    cnt[5][3][9] = 4;
    cnt[5][4][10] = 1;
    cnt[6][1][5] = 5;
    cnt[6][1][6] = 3;
    cnt[6][1][7] = 4;
    cnt[6][1][8] = 3;
    cnt[6][1][9] = 1;
    cnt[6][2][5] = 10;
    cnt[6][2][6] = 28;
    cnt[6][2][7] = 35;
    cnt[6][2][8] = 35;
    cnt[6][2][9] = 30;
    cnt[6][2][10] = 17;
    cnt[6][2][11] = 8;
    cnt[6][3][5] = 1;
    cnt[6][3][6] = 13;
    cnt[6][3][7] = 29;
    cnt[6][3][8] = 41;
    cnt[6][3][9] = 44;
    cnt[6][3][10] = 45;
    cnt[6][3][11] = 30;
    cnt[6][4][7] = 1;
    cnt[6][4][8] = 4;
    cnt[6][4][9] = 7;
    cnt[6][4][10] = 7;
    cnt[6][4][11] = 11;
    cnt[7][1][6] = 6;
    cnt[7][1][7] = 4;
    cnt[7][1][8] = 6;
    cnt[7][1][9] = 6;
    cnt[7][1][10] = 6;
    cnt[7][1][11] = 2;
    cnt[7][2][6] = 20;
    cnt[7][2][7] = 55;
    cnt[7][2][8] = 80;
    cnt[7][2][9] = 95;
    cnt[7][2][10] = 101;
    cnt[7][2][11] = 94;
    cnt[7][3][6] = 6;
    cnt[7][3][7] = 50;
    cnt[7][3][8] = 118;
    cnt[7][3][9] = 186;
    cnt[7][3][10] = 230;
    cnt[7][3][11] = 260;
    cnt[7][4][7] = 3;
    cnt[7][4][8] = 18;
    cnt[7][4][9] = 48;
    cnt[7][4][10] = 85;
    cnt[7][4][11] = 113;
    cnt[7][5][10] = 2;
    cnt[7][5][11] = 4;
    cnt[8][1][7] = 7;
    cnt[8][1][8] = 5;
    cnt[8][1][9] = 8;
    cnt[8][1][10] = 9;
    cnt[8][1][11] = 11;
    cnt[8][2][7] = 35;
    cnt[8][2][8] = 96;
    cnt[8][2][9] = 155;
    cnt[8][2][10] = 207;
    cnt[8][2][11] = 250;
    cnt[8][3][7] = 21;
    cnt[8][3][8] = 145;
    cnt[8][3][9] = 358;
    cnt[8][3][10] = 616;
    cnt[8][3][11] = 859;
    cnt[8][4][7] = 1;
    cnt[8][4][8] = 26;
    cnt[8][4][9] = 124;
    cnt[8][4][10] = 313;
    cnt[8][4][11] = 567;
    cnt[8][5][9] = 3;
    cnt[8][5][10] = 16;
    cnt[8][5][11] = 53;
    cnt[9][1][8] = 8;
    cnt[9][1][9] = 6;
    cnt[9][1][10] = 10;
    cnt[9][1][11] = 12;
    cnt[9][2][8] = 56;
    cnt[9][2][9] = 154;
    cnt[9][2][10] = 268;
    cnt[9][2][11] = 389;
    cnt[9][3][8] = 56;
    cnt[9][3][9] = 350;
    cnt[9][3][10] = 898;
    cnt[9][3][11] = 1654;
    cnt[9][4][8] = 8;
    cnt[9][4][9] = 126;
    cnt[9][4][10] = 552;
    cnt[9][4][11] = 1404;
    cnt[9][5][9] = 4;
    cnt[9][5][10] = 48;
    cnt[9][5][11] = 204;
    cnt[9][6][11] = 1;
    cnt[10][1][9] = 9;
    cnt[10][1][10] = 7;
    cnt[10][1][11] = 12;
    cnt[10][2][9] = 84;
    cnt[10][2][10] = 232;
    cnt[10][2][11] = 427;
    cnt[10][3][9] = 126;
    cnt[10][3][10] = 742;
    cnt[10][3][11] = 1967;
    cnt[10][4][9] = 36;
    cnt[10][4][10] = 448;
    cnt[10][4][11] = 1887;
    cnt[10][5][9] = 1;
    cnt[10][5][10] = 43;
    cnt[10][5][11] = 357;
    cnt[10][6][11] = 6;
    cnt[11][1][10] = 10;
    cnt[11][1][11] = 8;
    cnt[11][2][10] = 120;
    cnt[11][2][11] = 333;
    cnt[11][3][10] = 252;
    cnt[11][3][11] = 1428;
    cnt[11][4][10] = 120;
    cnt[11][4][11] = 1302;
    cnt[11][5][10] = 10;
    cnt[11][5][11] = 252;
    cnt[11][6][11] = 5;
    cnt[12][1][11] = 11;
    cnt[12][2][11] = 165;
    cnt[12][3][11] = 462;
    cnt[12][4][11] = 330;
    cnt[12][5][11] = 55;
    cnt[12][6][11] = 1;    
}

int inv[K];

int C(int n, int k)
{
    if(n < 0 || n < k || k < 0) return 0;
    int res = 1;
    for(int i = n; i > n - k; i--)
        res = mul(res, i);
    for(int i = 1; i <= k; i++)
        res = mul(res, inv[i]);
    return res;
}

void prepare()
{
    for(int i = 1; i < K; i++)
        inv[i] = binpow(i, MOD - 2);
    precalc();
    dp[0][0][0][0] = 1;
    for(int i = 0; i < K; i++)
        for(int j = 0; j < 2 * K; j++)
            for(int a = 0; a < K - 2; a++)
                for(int b = 0; b < K - 2; b++)
                {
                    if(dp[i][j][a][b] == 0) continue;
                    for(int add_cnt = 2; add_cnt < K; add_cnt++)
                        for(int add_desc = 1; add_desc <= K - 2; add_desc++)
                            for(int add_inv = 1; add_inv <= K - 2; add_inv++)
                            {
                                if(j + add_cnt >= 2 * K || a + add_desc > K - 2 || b + add_inv > K - 2) continue;
                                int& nw = dp[i + 1][j + add_cnt][a + add_desc][b + add_inv];
                                nw = add(nw, mul(dp[i][j][a][b], cnt[add_cnt][add_desc][add_inv]));    
                            }
                }       
}

void solve() 
{
    scanf("%d %d %d", &n, &k, &x);
    if(k == 0 && x == 0)
    {
        puts("1");
        return;
    }
    int ans = 0;
    for(int i = 1; i < K; i++)
        for(int j = 1; j < 2 * K; j++)
            if(dp[i][j][x][k] != 0)
            {
                ans = add(ans, mul(dp[i][j][x][k], C(n - j + i, i)));        
            }
    printf("%d\n", ans);
}

int main()
{
    prepare();
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
        solve();
}

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

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

LXH-cat

3 года назад, # |

I've known that F needed precalc,but I didn't solve it.qwq

→ Ответить

zghtyarecrenj

3 года назад, # ^ |

In fact, when $$$n > k^2$$$ holds, the answer is a $$$O(k)$$$-degree polynomial. So you can use lagrange interpolation to solve this problem without precalc.

← Rev. 2 →

I see,probably.

Could I see your code to understand further?

You can see A-SOUL_Diana's Code. 154556037

thanks!

joshring

An interesting thing about problem b I found, the difference between the first element and the last element cannot exceed $$$n + 1$$$. as long as the difference is less than or equal to $$$n + 1$$$ the answer is always yes. I'm not the best at proofs, but I think this is because the greatest difference between a series of $$$n$$$ consecutive integers is always $$$n - 1$$$, and our operations can increase the first element by one and decrease the last element by one, thereby shrinking the maximum difference between elements by two at most. So if the maximum difference is greater than $$$n - 1 + 2$$$ then the answer is no. What I can't figure out is why the ones in the middle can always seem to fix themselves if this is true. Still, this solution works in $$$O(1)$$$.

my code

Diamantis

Basically you are describing the same equation as the one in the solution: x[n-1]-x[0]-n+1 <= 2 <=> x[n-1]-x[0] <= n+1

I actually solved this like a dumb person by shifting x[0] to the right or keeping it where it is and checking if everyone of the next elements can be shifted to the proper position according to where x[0] is fixed. So my complexity is O(2n) = O(n). Still works since reading the input is also O(n), but my solution is roughly 3 times slower than necessary.

From my understanding, the solution described by the creator of the problem refers only to how many gaps there are between the first and last elements. If there are 0 gaps we're done, if there's one we can just shift one side and connect it with the other and if there are 2 gaps we shift 2 "chunks" so that everything is connected. On the other hand, if there are 3 or more gaps (which will make the inequality you referred to become false), then if one thinks about it, he will realize that there is no way to shift those 3 or more "chunks" in a way that they can be consecutive.

The O(1) solution blew my mind on how simple it was. This problem caused me to overthink :D

Danzev

How to come up with alternative solution of F?

SassySatyam

← Rev. 4 →

-8

[deleted]

MAKMED1337

It's not that contest

Dawnshard

Can someone explain the hashing solution for E?

variety-jones

+12

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

Can someone send code for precalculation in 1671F - Permutation Counting ?

wsyear

It seems that problem F can be solves with dp, but without precalc. But how to do that?

I was thinking that as well,and had a original idea.

GlenBzc

Can someone help me see where my B problem is going wrong，This caused my crash and lower rate my code

784

This happens because if the answer is NO your code goes to end and doesn't input remaining numbers. So they will be in the next test case and all numeration of the input numbers breaks so your code gots WA. To fix it your need to input ALL numbers even if the answer is NO now.

Thank you very much! ! ！ It was a stupid mistake T_T

I modified it, but it still seems to have a problem code

This happens because your solution can print two NO instead one. You must append the word continue; after the first check in cycle to not run the second check if the first check is already NO. And you will get AC then.

lucaperju

So, I have managed to create a test that hacks the hashes in the model solution for problem E. Now, my curiosity is: when hacking a solution, what does the checker use to find out what the correct answer to that given test is? Since if it would use the model solution, using a test like this, on which the model solution gives a wrong answer, could hack every solution, even the correct ones, and also make the problem impossible to solve if added to the testcases.

BledDest

+22

I've changed the model solution so that it is deterministic now, so the checker will compare the answer to the deterministic solution. Most likely the outcome will be something like "unexpected verdict" on hack since one of presumably correct solutions in Polygon is challenged.

By the way, how do you hack the model solution? I thought this way of hashing subtrees worked well.

What I have done is:

try random trees with n=5 until two give the same first hash (takes about 60k tries on average)
try trees with n=11 constructed as follows: first 6 layers are all 'A', and each of the subtrees under the 7th layer is a random one between the 2 found in step 1, this guarantees that the first hash will still give the same value to all the trees generated like so. And try until two trees give the same second hash (about 60k tries as well).
same as step 2, but this time with n=17, and the subtrees under the 7th layer being a random one out of the 2 found before, until two trees give the same third hash (also around 60k tries)

+10

Do you mean that you've hacked the hashes with seed $$$42$$$? awoo always replaces generator seeds to $$$42$$$ when posting randomized solutions in editorials. You can try uphacking the solution, but most likely it won't work since the random generator seed in the actual solution is not $$$42$$$. Instead, it's time-dependent.

oh, yeah, I have hacked the one with seed 42, it makes sense for the actual solution to be time dependent.

Pranayhalo

Can someone explain why https://codeforces.me/contest/1671/submission/155171162 is failing on test case 5? Cannot find the bug...

NafisAlam

Can someone explain the part of editorial on problem D which says "you can insert 1 somewhere, then insert x somewhere. The rest of insertions will be free." Why will be the rest of the insertions be free?

tyr0Whiz

If you have 1, x somewhere or x, 1 somewhere than you can insert arbitrarily any element between 1 to x in between them for 0 cost , I will discuss 1, x case you can do x, 1 similarly , Now suppose you insert 1<c<x between 1 and x , cost will be (x — c) + (c — 1) = x — 1, so it's free now we know if 2 are adjacent it holds true imagine there are some elements already in between 1 and x

1 C1 C2 x, it won't matter what order C1, C2 are in you can insert 1 < c < x between 1, C1 or C1, C2 or C2, x depending on which range it lies in, it will definitely be between more than one of the 3 ranges So cost of insertion will again be 0

sumitprajapati

2 года назад, # |

In problem E, can anyone explain how are we checking the equality of equivalence classes using just the lexicographically smallest string in preorder?

mostafaabdelaal_03

we can get the best insertion of 1 and x in o(1) by doing  this:

(ans) variable is the sum of the differences of the initial value, and (mn) refers to min element of the initial array and (mx) refer to max element of initial array

if(mn>1) ans+=min(2*(mn-1), min(v[0]-1, v[n-1]-1));
if(mx<x) ans+=min(2*abs(mx-x), min(abs(v[0]-x), abs(v[n-1]-x)));

My Submission

i_pranavmehta

13 месяцев назад, # |

here's the solution to E (without hashing)

edum

2 месяца назад, # |

can somebody please tell what is the problem with my sumission https://codeforces.me/contest/1671/submission/281132373 its passing test case 3 but failing in 4 and i cannot understand why or if somebody can just tell what is test case 4 checking so i can work on that aspect of my code

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