I look forward to every weekend for atcoder contests

Planned post contest discussion

Update: VOD Twitch YouTube

I am very weak in algorithms. What can I do?

At: https://atcoder.jp/users/da_ke

Good luck!

Downvoted.

The problem D is the shitest problem I have seen.

How to do D?

is E Binary Search + Dp??

Can anyone tell me what was wrong with my solution for Problem B, where the task was to determine whether the sequence is a progression or not? I tried to find all the ratios, store them in a map, and check if there were any other ratios by verifying the size of the map. Why did this solution fail in one test case? It would be very helpful if someone could explain the root cause of the failure

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    double pre, curr;
    map<double, int> ratio;
    cin >> pre;

    for (int i = 0; i < n - 1; i++)
    {
        cin >> curr;
        ratio[pre / curr]++;
        pre = curr;
    }
    ratio.size() == 1 ? cout << "Yes" : cout << "No";
}

Enough of coin-toss problems like D.

At least for me Problem D is related to Stirling numbers. I saw some ways to count partitions using stirling numbers, the next partition always need to have the first unused number in previous partitions. The total number of ways is the sum {n, 1}, {n, 2} ... {n, n}.

I work very slowly on question B, but most of the time I search for 'geometric progress' on Google. I think it should be briefly described in the question

Took a lot of time to solve ABC, solved E just after the contest ended :(

E was a good binary search + DP problem. How to solve D?

Good contest, thanks for the round math957963 sounansya and all testers!

Problems on recursion always look for me like "do the exact implementation, as author did".

Can someone explain solution for F. Cannot understand the editorial

I can't understand 3rd test case of problem D

Test Case — 3 :
6
71 74 45 34 31 60

Result :
84

How ? Explain anyone please!

In problem E, if each food contains all 3 vitamins and the input is like this: Ai1, Ai2, Ai3, Ci (where Aij is Aij units of jth vitamin) Then how do we solve the same problem?

Can someone explain approach for problem D? I didn't understand the editorial.

During the contest, I have a WONDERFUL solution for Problem D (I think the Problem E is harder than Problem D).

Seeing that $$$N$$$ is so small, it's not hard to think of a search implementation, so you can write a simple search: DFS to the $$$x$$$-th point, and then enumerate $$$i\in [1,N]$$$ to indicate that $$$A_x$$$ moved to $$$B_i$$$, when $$$x \gt N$$$ time to calculate the value of XOR, and use the unordered_map statistical answer can be. This has a time complexity of $$$O(N\times N^N)$$$, but in practice, because of the constant problem, only the testcases of $$$N\le 8$$$ can be passed in the time limit of $$$3\text{s}$$$.

Consider pruning (the official solution uses set, I don't know how to do QWQ), first of all, the enumeration range can be adjusted to $$$i\in [1,x]$$$, because the front moves to the back and the back moves to the front are the same, so the time complexity is reduced to $$$O(N\times N!)$$$, and can pass the testcases of $$$N\le 11$$$. Consider to continue optimization, found that when $$$B_j=0$$$ when the $$$A_i$$$ to $$$B_j$$$ operation is meaningless (just changed the position), so the transfer can be special judgment, so that can be used $$$1.5\text{s}$$$ perfect through this problem. The time complexity is $$$O(NB(N))$$$, where $$$B(N)$$$ denotes the Bell Number of $$$N$$$, and the maximum is $$$4213597$$$, which is sufficient to pass the question.

My Code.

#include <bits/stdc++.h>
#define ll long long
#define endl putchar(10)
#define spc putchar(32)
#define R register
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x, endl
#endif

inline ll read()
{
    ll x=0,f=1; char c=getchar();

    while(c<48 || c>57)
    {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>47 && c<58)
    x=(x<<1)+(x<<3)+c-48, c=getchar();
    return x*f;
}

inline void write(ll x)
{
    static ll sta[41]; ll top=0;
    if(x<0) putchar('-'), x=-x;
    do sta[top++]=x%10, x/=10; while(x);
    while(top) putchar(sta[--top]+48);
}

ll n,a[21],p[21],res,ans;
unordered_map<ll,ll> bz;

void dfs(ll x)
{
    if(x>n)
    {
        res=0;
        for(R int i=1; i<=n; ++i) res^=p[i];
        if(!bz[res]) bz[res]=1, ++ans; return;
    }

    for(R int i=1; i<=x; ++i)
    {
        if(!p[i]) continue;
        p[i]+=a[x]; p[x]-=a[x]; dfs(x+1);
        p[i]-=a[x]; p[x]+=a[x];
    }
}

int main()
{
    n=read();
    for(R int i=1; i<=n; ++i)
    a[i]=read(), p[i]=a[i];
    dfs(1); write(ans);
    return 0;
}