Разбор Educational Codeforces Round 83

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

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Разбор

Решение (vovuh)

for i in range(int(input())):
    n, m = map(int, input().split())
    print('YES' if n % m == 0 else 'NO')

1312B - Bogosort

Идея: Roms

Разбор

Решение (Roms)

for t in range(int(input())):
    n = input()
    print(*sorted(map(int, input().split()))[::-1])

1312C - Adding Powers

Идея: adedalic

Разбор

Решение 1 (adedalic)

fun main() {
    val T = readLine()!!.toInt()
    testCases@for (tc in 1..T) {
        val (_, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { it.toLong() }.toLongArray()

        var maxPower = 1L
        while (maxPower < 1e16.toLong())
            maxPower *= k

        while (maxPower > 0) {
            val positions = a.withIndex().filter { it.value >= maxPower }.map { it.index }
            if (positions.isNotEmpty()) {
                if (positions.size > 1) {
                    println("NO")
                    continue@testCases
                }
                a[positions[0]] -= maxPower
            }
            maxPower /= k
        }
        if (a.max()!! > 0L) {
            println("NO")
            continue@testCases
        }
        println("YES")
    }
}

Решение 2 (adedalic)

fun getMask(a: Long, k: Long): Long? {
    var (tmp, res) = listOf(a, 0L)
    var cnt = 0
    while (tmp > 0) {
        if (tmp % k > 1)
            return null
        res = res or ((tmp % k) shl cnt)
        tmp /= k
        cnt++
    }
    return res
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { getMask(it.toLong(), k) }
        val b = a.filterNotNull()
        if (b.size < n) {
            println("NO")
            continue
        } else {
            val res = b.reduce { acc, l -> if (acc < 0 || (acc and l) > 0) -1 else acc or l }
            println(if (res < 0) "NO" else "YES")
        }
    }
}

1312D - Count the Arrays

Идея: BledDest

Разбор

Решение (BledDest)

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int MOD = 998244353;

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

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

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int fact[N];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

int C(int n, int k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

int main() 
{
    precalc();
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if(n > 2)
        ans = mul(C(m, n - 1), mul(n - 2, binpow(2, n - 3)));
    cout << ans << endl;
}

1312E - Array Shrinking

Идея: MikeMirzayanov

Разбор

Решение (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    out << "[";
    fore(i, 0, sz(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

const int N = 555;
int n, a[N];

inline bool read() {
    if(!(cin >> n))
        return false;
    fore(i, 0, n)
        cin >> a[i];
    return true;
}

int dp[N][N];

int calcDP(int l, int r) {
    assert(l < r);
    if(l + 1 == r)
        return dp[l][r] = a[l];
    if(dp[l][r] != 0)
        return dp[l][r];
    
    dp[l][r] = -1;
    fore(mid, l + 1, r) {
        int lf = calcDP(l, mid);
        int rg = calcDP(mid, r);
        if(lf > 0 && lf == rg)
            return dp[l][r] = lf + 1;
    }
    return dp[l][r];
}

int dp2[N];

inline void solve() {
    fore(i, 0, N)
        dp2[i] = INF;
    
    dp2[0] = 0;
    fore(i, 0, n) {
        fore(j, i + 1, n + 1) {
            if(calcDP(i, j) > 0)
                dp2[j] = min(dp2[j], dp2[i] + 1);
        }
    }
    cout << dp2[n] << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

1312F - Attack on Red Kingdom

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;
const int K = 5;

int x, y, z, n;
long long a[N];

typedef vector<vector<int> > state;
map<state, int> d;
int cnt;
int p;
vector<vector<int> > state_log;

int mex(const vector<int>& a)
{
    for(int i = 0; i < a.size(); i++)
    {
        bool f = false;
        for(auto x : a)
            if(x == i)
                f = true;
        if(!f)
            return i;
    }
    return a.size();
}

state go(state s)
{
    int f1 = mex({s[0][K - x], s[1][K - y], s[2][K - z]});
    int f2 = mex({s[0][K - x], s[2][K - z]});
    int f3 = mex({s[0][K - x], s[1][K - y]});
    state nw = s;
    nw[0].push_back(f1);
    nw[1].push_back(f2);
    nw[2].push_back(f3);
    for(int i = 0; i < 3; i++)
        nw[i].erase(nw[i].begin());
    return nw;
}

void precalc()
{
    d.clear();
    state cur(3, vector<int>(K, 0));
    cnt = 0;
    state_log.clear();
    while(!d.count(cur))
    {
        d[cur] = cnt;
        state_log.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
        cur = go(cur);
        cnt++;
    }                   
    p = cnt - d[cur];
}

int get_grundy(long long x, int t)
{
    if(x < cnt)
        return state_log[x][t];
    else
    {
        int pp = cnt - p;
        x -= pp;
        return state_log[pp + (x % p)][t];
    }
}

void read()
{
    scanf("%d %d %d %d", &n, &x, &y, &z);
    for(int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
}                    

int check(int x, int y)
{
    return x == y ? 1 : 0;
}

void solve()
{
    precalc();
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans ^= get_grundy(a[i], 0);
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        ans ^= get_grundy(a[i], 0);
        res += check(ans, get_grundy(max(0ll, a[i] - x), 0));
        res += check(ans, get_grundy(max(0ll, a[i] - y), 1));
        res += check(ans, get_grundy(max(0ll, a[i] - z), 2));
        ans ^= get_grundy(a[i], 0);
    }
    printf("%d\n", res);
}

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

1312G - Autocompletion

Идея: adedalic и BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;

map<char, int> nxt[N];
bool term[N];
int n, k;
char buf[3];
int dp[N];
int dict[N];

int T[4 * N];
int f[4 * N];

void build(int v, int l, int r)
{
    T[v] = int(1e9);
    if(l != r - 1)
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
    }
}

int getVal(int v)
{
    return T[v] + f[v];
}

void push(int v, int l, int r)
{
    T[v] += f[v];
    if(l != r - 1)
    {
        f[v * 2 + 1] += f[v];
        f[v * 2 + 2] += f[v];
    }
    f[v] = 0;
}

void upd(int v, int l, int r)
{
    if(l != r - 1)
    {
        T[v] = min(getVal(v * 2 + 1), getVal(v * 2 + 2));
    }
}

int get(int v, int l, int r, int L, int R)
{
    if(L >= R)
        return int(1e9);
    if(l == L && r == R)
        return getVal(v);
    push(v, l, r);
    int m = (l + r) / 2;
    int ans = min(get(v * 2 + 1, l, m, L, min(m, R)), get(v * 2 + 2, m, r, max(L, m), R));
    upd(v, l, r);
    return ans;
}

void add(int v, int l, int r, int L, int R, int val)
{
    if(L >= R)
        return;
    if(l == L && r == R)
    {
        f[v] += val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    add(v * 2 + 1, l, m, L, min(m, R), val);
    add(v * 2 + 2, m, r, max(L, m), R, val);
    upd(v, l, r);
}

void setVal(int v, int l, int r, int pos, int val)
{
    if(l == r - 1)
    {
        f[v] = 0;
        T[v] = val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    if(pos < m)
        setVal(v * 2 + 1, l, m, pos, val);
    else
        setVal(v * 2 + 2, m, r, pos, val);
    upd(v, l, r);
}

void dfs(int v, int d, int last)
{
    dp[v] = last + 1;
    if(term[v])
        dp[v] = min(dp[v], get(0, 0, n + 1, 0, d));
    setVal(0, 0, n + 1, d, dp[v] + 1);
    if(term[v])
        add(0, 0, n + 1, 0, d + 1, 1);
    for(auto x : nxt[v])
        dfs(x.second, d + 1, dp[v]);
    setVal(0, 0, n + 1, d, int(1e9));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int p;
        scanf("%d %s", &p, buf);
        char c = buf[0];
        nxt[p][c] = i + 1;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d", &dict[i]);
        term[dict[i]] = true;
    }

    build(0, 0, n + 1);
    dfs(0, 0, -1);
    for(int i = 0; i < k; i++)
        printf("%d ", dp[dict[i]]);
    puts("");
}

for len in [1, size of array]: if [1, len] can be reduced to one element: dp[len] = 1 else: for i in [2, len): if ([i, len] can be reduced to one) and dp[i - 1] + 1 < dp[len]: dp[len] = dp[i - 1] + 1

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

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

ezdp

5 лет назад, # |

-38

fast editorial, thanks!

→ Ответить

Ormlis

+12

In G we can maintain value "the shortest distance to the smallest line in the lexicographic order from the current prefix" in dfs. To update it just check the distance from the current vertex + 1. And to pass it to the next vertex, we need to add to the value the number of vertices from the S that we went through in other sons. It is O(n). Code.

yplusplusplus

5 лет назад, # ^ |

← Rev. 2 →

I solved G by the same way. And This is my code.

Clever_Jimmy

Could you plz explain your idea more clearly?

thx :P

pootis

Main challenge is speeding up computation of f(u) = min d(v) + rank of u in subtree rooted at v, over all ancestors v of node u. Suppose we have this computed for node u, and wish to update computation for children c of u. The difference is exactly the size of sibling subtrees that come before c. This difference affects subtrees of each ancestor equally, so after adding that to existing f(u), we only need to consider the additional case for a subtree beginning at c so you get something like f(c) = min(f(u)+siblings, d(c)).

Another Example (sorry for all the junk — just look for the dfs method which is 8 LOC)

rivalq

another way to find rank(u) in subtree rooted at v is tin(u)-tin(v)+(isgood(v)) (we increment time only when we encounter a good string)

Ugnwd

can anyone explain in problem D why we are multiplying by 2^(n — 3) ?

tiojuan

Each element will appear either before the maximum number, or after it. Therefore each of the N-3 numbers (that aren't the maximum and the number we have to repeat) has two options, so we have to mulitiply by 2, N-3 times.

Codebuddy1903

Since there are n elements we are to choose (n-1) elements and one element will be copy of one of n-1 elements choosen by us. Now we can not make copy of max element as it violates the condition so we are left with n-2 elements so we can choose one of them.Let x be the position of max element so the element which has duplicate must be persent on either side because if it will be persent on single side the sequence can not be strictly increasing or decreasing so we have max element at x and two same elements so now we are left with n-3 elements since there are two choices for every element to either go on right hand side of max element or LHS of that max element . so 2^(n-3) factor is involved. why is it so? Since we can arrange a array in strictly increasing order if we dont have duplicates. Hope it was clarified

Hamim99

we assume one element as left or right side of max .Isn't it possible that element become max for another combination?So why not we use 3^n-3?As there can be three position?

cuber_coder

Notice that we have chosen the current set of (n-1) elements already and are then placing the elements in the desired order.

Hence for the current set of elements, only one will be the peak element. For another set, it might be so that an element currently on the left/right becomes the peak, but for that the initial (n-1) elements chosen will be different. Hence the factor of 3 doesn't appear here.

great explanation .Thanks!

We have already selected elements now how can our combo differ?

sabj

int mul(int x, int y) { return (x * 1ll * y) % MOD; } For what we use this func, why we cant make x-long long, and y-long long, and multiply them?

dmkz

← Rev. 4 →

+13

Of course, we can, there is no difference: long long 1.08 s and int 1.08s for calculation of $$$2^{28}!$$$. Only one think that you should do is declare mod as constant. If no const — long long 3.33s. It is because division by a constant can be calculated without integer division.

decoder__

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

Hey Bro can you elaborate this further It is because division by a constant can be calculated without integer division

Book: Hacker's Delight, 2nd Edition, Chapter 10: Integer Division By Constants. Main idea in few words: change $$$\dfrac{x}{y}$$$ by multiplication $$$x \cdot y^{-1}$$$, where $$$y$$$ is constant.

Can anyone please explain E problem it would be great help. Thanks in advance :)

svince

+34

I'll try to go along the lines of the solution:

Let $$$dp[i][j]$$$ be the value of the single remaining element, when subarray $$$[i:j]$$$ is reduced using the given operation. If there is no way to reduce this subarray into a single element, $$$dp[i][j]$$$ will be $$$-1$$$.

How do you compute $$$dp[i][j]$$$? Consider index $$$k$$$, such that $$$i \le k \lt j$$$. We divide subarray $$$[i:j]$$$ into two halves: $$$[i:k]$$$ and $$$[k+1:j]$$$.

Base case: when subarray is of size 1 $$$(i=j)$$$, answer will obviously be the number in that subarray. Now for any $$$k$$$, if $$$dp[i][k] = dp[k+1][j]$$$, i.e. we can divide subarray into two halves such that both halves are reduced to the same number, we can combine the two numbers, hence $$$dp[i][j] = dp[i][k] + 1$$$.

This is one half of the solution. We now compute the minimum number of partitions that can be reduced to size 1.

Let $$$dp2[i]$$$ : minimum number of partitions required for array $$$[1:i]$$$. We compute this in this way: Take index $$$k$$$, $$$1 \le k \le i$$$. If $$$[k:i]$$$ can be reduced to a single element, i.e. $$$dp[k][i] \ne -1$$$, then we can find optimal partitioning of subarray $$$[1:k-1]$$$ and just add one to the answer. Formally, $$$dp2[i] = min(dp2[i], dp2[k] + 1)$$$, for all $$$k$$$ such that $$$dp[k][i] \ne -1$$$.

The required answer is $$$dp[n]$$$. Here's my solution for reference: 72913085. Hope this helped.

kartik8800

+19

Can you explain why will dp[i][j] reduce to a single unique value?

I do feel it's intuitive but still why is it impossible for having two different ways of combining elements of a subarray and reaching two different final merged values?

cheissmart

consider sequence $$$ 2^{a_1}, 2^{a_2}, ..., 2^{a_n} $$$ combining two adjacent equal values $$$ a_i = a_{i+1} $$$ is equivalent to merging two values in to one value $$$ 2^{a'} = 2^{a_i} + 2^{a_{i+1}} = 2 ^ {a_i + 1} $$$. So if [l, r] can be reduced to a single value, it must be unique.

+25

This proof is from tmwilliamlin168 explanation

rupav

How come converting into a sum helped to prove uniqueness?

AjaySabarish

I think he means that, the "merging" operation is akin to adding 2 similar powers of 2, sum of a few powers of 2,if reduced to a single power of 2, then that term should be unique

-16

We can prove that a subarray $$$[i:j]$$$ can be divided in atmost one way, i.e. there can be only one such $$$k$$$, for which $$$dp[i][k] = dp[k+1][j]$$$.

For this, we define a fully reducible subarray as a subarray which can be reduced to a single element. We claim two things: removal of elements from a fully reducible subarray will only reduce the value of the remaining element, provided the remaining subarray is a fully reducible subarray. Similarly, addition of elements will only increase the value of the remaining element (you can try this out).

Hence, if $$$dp[i][k] = dp[k+1][j]$$$, there is no possible way to transfer elements from subarray $$$[i:k]$$$ to $$$[k+1:j]$$$, or vice versa, such that $$$dp[i][k'] = dp[k'+1][j]$$$, for another $$$k'$$$.

sirjan13

+10

We can also prove by contradiction,

Lets say there are two values of K, i.e K1 and K2, such that dp(i, K1) = dp(K1 + 1,j) = X and dp(i, K2) = dp(K2 + 1, j) = Y.

Lets assume K1 < K2,

If that is the case then according to the dp definition, the subarray (i, K1) reduced to the number X, and the subarray (K1 + 1, j) also reduced to X whereas the subarrays (i, K2) and (K2 + 1, j) reduced to Y,

Since K1 < K2, the subarray (i, K1) is a prefix of (i, K2) thus X < Y. And (K2 + 1, j) is a suffix of (K1 + 1, j) which suggests that X > Y.

This leads to a contradiction.

Amazing, thanks a lot :)

SLIMSHADYNICK

Thanks a lot!

lemme_sleeeep

Thanks a lot :)

anshumankr001

This explanation was better than the one in editorial. Thanks a lot!

rahuliitkgp

Thanks a lot to all in this thread This explanation is much better than that of editorial

voventa

+24

in problem F, why are five lines enough to determine all the other values?

LMB

Let's consider that the number of remaining soldiers is i.Because x,y,z<=5.You only need the answer to[i-5,i-1] to update i.When you know the answer to i,you delete the answer to (i-5),and add the new answer to the end of the vector.In other words,the vector is scrolling. Because the period is at most 36,you can use brute force to find it. I hope this helps. ：）

skushneryuk

Can anyone explain how we get string "ieh" in first example in two seconds? After getting string "i" "ieh" is lexicographically second after "i", so we need at least 3 seconds, isn't it?

iishanto

How to solve problem C using bitmasks. Kindly help me.

nanmenyangde

You can make each number of the array v into a number based on k.If the number only consists of 0 and 1, it must be able to become 0.Then, mark the position of each 1.If the number consists of other numbers or the position of some 1 is already marked, the array won't be able to be filled with 0 and the answer is "NO". After you finish that operation for each number in the array v, the answer will be "YES".This is my solusion.

I am a Chinese and I am sorry that my English is poor. if there is something wrong in my words, please tell me and I will repair it as fast as posiible.

harsh_67

← Rev. 3 →

Can you please explain What is the use of step variable in your code?How we will check if this i power is used or not?

pepelats

Is it posssible to solve G on Java?

ijxjdjd

See my solution, I had to make my recursion iterative in order to bypass stack overflow

Devil

awoo Why the same solutions receive completely different times?:

72925974 4321 ms = 72925981 2885 ms

72927822 1668 ms = 72927856 920 ms

gyan_p_t

Can anyone explain B. Bogo Sort Problem??

FinalBoss_

In this problem it was quite an observation that if we sort the array in descending(or non increasing order to be precise) then A[i]-i can never be equal to A[j]-j for i<j. Because if i<j that implies A[i]>A[j] since we sorted the array in non increasing order.Now we are subtracting larger value by smaller index example array of 5 4 will become 5-1 != 4-2. hope that helps. Here's the link to my solution

2002002

If we sort the array in non-increasing order, then we have

$$$ \begin{equation} i \lt j \end{equation}\tag{1} $$$

$$$ \begin{equation} a_i \ge a_j \end{equation}\tag{2} $$$

Rewrite $$$(1)$$$ to

$$$ \begin{equation} -i \gt -j \end{equation}\tag{3} $$$

and add $$$a_i$$$ to both side

$$$ \begin{equation} a_i - i \gt a_i -j \end{equation}\tag{4} $$$

Add $$$-j$$$ to both side to $$$(2)$$$

$$$ \begin{equation} a_i - j \ge a_j - j \end{equation}\tag{5} $$$

From $$$(4)$$$ and $$$(5)$$$, we have

$$$ \begin{equation} a_i - i \gt a_i - j \ge a_j - j \end{equation}\tag{6} $$$

which means

$$$ \begin{equation} a_i - i \gt a_j - j \end{equation}\tag{7} $$$

$$$ \begin{equation} i - a_i \ne j - a_j \end{equation}\tag{8} $$$

$$$ \begin{equation} j - a_j \ne i - a_i \end{equation}\tag{9} $$$

Therefore, after sorting the array in non-increasing order, for each pair of indexes $$$ i < j $$$ , the condition $$$ j - a_j \ne i - a_i$$$ holds.

Can anyone explain me C please.

Dhruv_Gheewala

convert given numbers into k-base system. now, do addition of k-base numbers without k-base system. now, you can observe that, if there is any bit is >= 2 then it's not possible to make given numbers using power of k. because, you can use k^some power only one time.

sare

great way!

Show_2.5_Need

can u please explain in more details?

if a number is in k-base system, then if number n = 1111 = k^0 + k^1 + k^2 + k^3 , and if n = 2111 = k^0 + k^1 + k^2 + 2*k^3, means we need to add k^3 two times. so we can't make this number.

Adi1169

lets assume we have to check for no. X ,if X is summation of power of k or not then X=k^n+k^m+k^l....,where n>m>l..,so if we take k^n common and divide X by k^n then resulting no. should be divisible by k, X=k^n(1+k^(m-n)+k^(l-n)) X/(k^n)-1=k^(m-n)+k^(l-n)..

code for above explanation

rb_rb

Solution for Problem C is not quit clear can anyone help me out with that??? adedalic

see this comment : https://codeforces.me/blog/entry/74640?#comment-587595

Tem1rbay

Could you tell me what does this return dp[l][r] = a[l] ?

ishank162

I think it first assigns the value of a[I] to dp[l][r] and then returns the value of dp[l][r];:^)

neal

+31

I have an $$$O(n \log n)$$$ solution to problem E: https://codeforces.me/blog/entry/74656

devaar100

Can someone please explain how time complexity of problem E is n^3 ? Thanks.

Figured it out after rethinking the problem. Let's think of the main function for loop and calcDP separately. So calcDP is an N^3 function while our for loop runs in N^2. They are independent entities. So when you call calcDP from inside your N^2 for loop, their complexities don't affect each other.

andylizf

There is another solution to problem D with complexity $$$O(n \log P)$$$.

Welcome to see in https://codeforces.me/blog/entry/74685. For the Chinese version https://andylizf.github.io/2020/03/10/CF1312D-Count-the-Arrays.

Can anyone prove it is equal to the normal solution?

r.zay699

Расшарьте Е пожалуйста. Что значит стандартная префиксная динамика? Если это стандартный алгоритм, киньте ссылку пожалуйста, не могу найти.

adedalic

Там же дальше расписано, что это значит.

Так или иначе, если стоит задача разбиения массива на несколько отрезков, то кажется очевидным попробовать написать динамику от длины префикса $$$dp[len]$$$ — оптимальное разбиение префикса длины $$$len$$$.

Переходы тоже прямолинейны — попытаемся перебрать длину последнего блока. И либо добавляем этот блок к текущему оптимальному разбиению, если делаем переходы вперед, либо отрезаем этот последний блок от текущего префикса, если переходы назад.

-8

Понятно тем, кто уже знает решение, но теперь я кажется понял. Выходит псевдокод будет таким:

MehulJ21

can anyone explain c better plz?

gupta_samarth

The question states that you have an array ( which is initially all zeros ), and you apply some number of operations, say $$$M$$$.

In $$$i$$$th operation ( $$$0 \le i \lt M$$$ ), you can either pass and go to step $$$i+1$$$, or add $$$k^i$$$ to one of the elements of the array.

Notice that, each power of $$$k$$$ is used atmost once, if at all. Thus, we simply convert each number to base $$$k$$$, and see if any power of $$$k$$$ is repeated.

reyad

Another possible solution of 1312E — Array Shrinking. Complexity is O(V * N) where V is limit of a. The solution is here.

kr_abhinav

To solve F, I used the heuristic that the period is equal to $$$smallest+largest$$$ out of $$$x,y,z$$$ It only has 2 exceptions (considering $$$y$$$ and $$$z$$$ equivalent): $$$1,3,4$$$ (period=7) and $$$4,1,2$$$ (period=3).

I have no clue on why this works, wondering if it just somehow worked because of small constraints on the values. Any insights?

Link to my code: 73467272

Love_Triangle

what is the time complexity of D,is it O(m log p) or (n log p)??

I think the time complexity is only O(log p).

Gary2005

For problem G,we don't need any data struct .Simple dfs is enough.

The code is very short:

Code

int n;
char c[1000000+20];
vector<int> each[1000000+20];
int queries[1000000+20],dp[1000000+20];
bool ok[1000000+20];
bool cmp(int A,int B){
	return c[A]<c[B];
}
int cnt=0;
void dfs(int now,int mini,int prev){
	cnt+=ok[now];
	if(!now){
		dp[now]=0;
	}
	else{
		if(ok[now]){
			dp[now]=min(dp[prev]+1,mini+cnt);
		} 
		else{
			dp[now]=dp[prev]+1;
		}
	}
	int save=dp[now]-cnt+ok[now];
	for(auto it:each[now]){
		dfs(it,min(mini,save),now);
	}
}
int main(){
	fastio;
	cin>>n;
	rb(i,1,n){
		int  pi;
		cin>>pi>>c[i];
		each[pi].PB(i);
	}
	int k;
	cin>>k;
	rb(i,1,n){
		sort(ALL(each[i-1]),cmp);
	}
	rb(i,1,k){
		cin>>queries[i];
		ok[queries[i]]=1;
	}
	dfs(0,INF,-1);
	rb(i,1,k){
		cout<<dp[queries[i]]<<" ";
	}
	return 0;
}

beacon_cwk

Though there are many details,it's still much simpler than solutions using data structures.Also,it's very fast.

Harsh_garg

In problemA, if we consider case n = 8 and m = 4 then how can a convex polygon with 4 sides can have a same center.

Thanks, in advance

Number the vertex from 0 to n-1 (7) take 0th and 2nd and 4th and 6th vertex

How do you prove that we can have the vertices of smaller polygon in common with larger polygon?

I don't have a math-heavy perfect proof but you can think in this way.

Lets call polygon of m sides be polygonIn and polygon of n sides be polygonOut. select one side of polygonIn and connect it to the center of polygon the angle will be (2*pi/m) also note that this angle is equal to x*(2*pi/n) (x is some integer) because the end points of a side of polygonIn must be end points of some x continous sides of polygonOut.

Example in case of hexagon and triangle x = 2 because end points of one side of triangle is also end points of 2 continous sides of hexagon.

so we get x*(2*pi/n) = 2*pi/m

x*m = n

n%m = 0

abhinav_jain02

How can we check the period is at most 36 by brute force ?

Is there a theoretical proof for the bound on period ?

Ashish

In problem E, would the single representative of a subarray always be unique (to cache beforehand), would appreciate if someone can give a proof.

I think This is really good .

Got it, thank you

dementorx

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

Can any one help me with my solution (81649940) to Problem E.

my approach :

dp[i][j][0] — min length of which can be obtained from subarray [i,j]

dp[i][j][1]- after reduction of this([i,j]) subarray what is the left most value eg if array is 6 6 3 3 5 then dp[i][j][2] = 7;(from reduced array- 7 4 5)

dp[i][j][2]- after reduction of this subarray what is the right most value eg. if array is 6 6 3 3 5 then dp[i][j][2] = 5;(from reduced array- 7 4 5)

Mohamed_Hesham

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

You may get a good answer then you spoil it in the next iteration by this else

else{
    if(dp[i][j][0]<=dp[i][k][0] + dp[k+1][j][0])continue;
    dp[i][j][0] = dp[i][k][0] + dp[k+1][j][0];
    dp[i][j][1] = dp[i][k][1];
    dp[i][j][2] = dp[k+1][j][2];
}

Just add a condition to the if above to check if the two ranges are of size 1

It can be proven that the merged ranges should be of size one each (after reducing)

Here is my submission 251049164