I will be live with post contest discussion stream here

As an sc3developer, hope my computer doesn't fall into a bottomless pit this round

wow!

Why not "6 or 7 or 67 problems" this time?

Letsss Go...

Good luck to all participants!

Good luck to all participants!

Time to get humbled by c again. -:lol:-

If it's Neapolis we cooked again

How many questions should I aim for in a div 2 contest to reach pupil. In a 2 hour, 3 hour long contest, does the number or timing expected from one change?

Ahh another edu... goodbye purple

Ahh another edu... goodbye purple

Do you guys recommend a unrated guy to join?

.

yay, another contest! lets have fun!!

Hello,

This will be my first CF contest, i hit usaco plat in march and wanted to do this for fun to see how it is in comparison

any tips?

Fight for Master go go go

yes, good luck to all participants!

I hope A and B are easy like old problems, there is no point of making A and B much harder but still solvable by AI

I hope A and B are easy like old problems, there is no point of making A and B harder but still solvable by AI

i need to find the guy with tnt pfp

Thanks for the round! Good luck, everyone!

Good luck!!

Good luck!

I love problem C.

seven submissions for last problem

As a graytist (graytist != ratist btw), nooo I'm getting back to newbies after this round.

3k solves for D is crazy

Can F be solved with persistent treaps?

$$$A, B, C$$$ were kinda standard, as expected for a Educational round. But $$$D$$$ was a good problem!

D is a cool problem, sad that I solved it 3 minutes before the contest ended

.

so close to solve c, wasted a lot of time on b, i dont know why :(

D is a nice DP problem!

Damn, i bugged my solution for C but still, great contest!

First time I saw where we actually do the operation mentioned in the problem (B) and it works, otherwise mostly its some mathematical equation which solves the problem in O(1) or log. C seems out of my way, need to upsolve now, but loved the problems.

got 3 minute late to submit E!

B was a disaster

I thought my solution for D would be fast enough but it TLEs and I'm not sure why :(

My idea is that it doesn't matter in which order you apply the merges, and every merge can be represented by a mask. So for example if a = 12345 and mask = 1101 then we would get 69.

Then I loop over all masks for a and b, which should be small amount, and check if merge(a) == merge(b), and track the longest merge.

I thought I might've been too slow because I was working with strings when merging, but even after changing to working with ints I TLE on test case 10. Is it possible to make my solution work, or is this approach completely wrong? :P thanks for reading

:-(

wasted 1 hour thinking constraint was 1e5 for both the strings in D :((

Just wondering about C, there is any solution for which having a sorted array makes things any easier? My solution works by generalizing contiguos equal numbers as blocks so i really don't use that sorted fact at all, i wonder if i've made things more complicated by not using that fact

The problem F made me get Master!

I felt like the first four questions in this match are too easy. I solved them in 40 minutes. They don't seem like Div.2 level difficulty.

And among them, B is much harder than the other three.

Editorial of D+E

https://codeforces.me/contest/2242/submission/381527708 D. Say after operations the first digit is merged from A[i1:i2], second digit from A[i2:i3], etc. and similarly for B[j1:j2], ... Then if P are the prefix sums of A mod 10, and Q of B mod 10, we want P[i1] = Q[j1], P[i2] = Q[j2], etc. This is simply the longest common subsequence of P and Q, which is a known dp.

https://codeforces.me/contest/2242/submission/381527102 E. Let P = 2**k the highest power of 2 <= R. If we can do y = P, we should and x = max(L, P/2). This is because the ones digits of y are multiples of k+1, which is 1, 2, 3, ... modulo k, which is the same order as x. Therefore we just want the smallest value of x that is one less digit (bit-length).

If we can't, then x and y have the same bit-length. Every 1 in the common prefix of L and R must be on x and y, and the rest of the bits will be zero. To attain this, choose x = (common prefix) + 01111.... and y = (common prefix) + 10000....

Screencast with commentary

Problem B can be solved with the same idea as this problem: https://codeforces.me/problemset/problem/2103/C

Q:D I solved this problem by generating all possible strings using DFS. For every string, I merge one adjacent pair of digits ("i" and "i+1") into (a[i] + a[i+1]) % 10, remove leading zeros, store the new string in a map (to avoid duplicates), and push it into a stack to continue generating all possibilities. I repeat the same process for both input strings and then find the longest common generated string. Is this approach correct? If not, where is the flaw in my logic or implementation?

```cpp void solve() { stack st; string a, b; cin >> a >> b;

st.push(a);
unordered_map<string, int> mpp;
mpp[a] = 1;

while (!st.empty())
{
    string tt = st.top();
    st.pop();

    int n = tt.size();
    for (int i = 0; i < n - 1; i++)
    {
        int val1 = tt[i] - '0';
        int val2 = tt[i + 1] - '0';
        int f = (val1 + val2) % 10;

        string str = tt.substr(0, i);
        str += char(f + '0');
        str += tt.substr(i + 2);

        int pos = str.find_first_not_of('0');
        if (pos == string::npos)
            continue;

        str = str.substr(pos);

        if (!mpp.count(str))
        {
            mpp[str] = 1;
            st.push(str);
        }
    }
}

stack<string> st2;
st2.push(b);
unordered_map<string, int> mpp2;
mpp2[b] = 1;

while (!st2.empty())
{
    string tt = st2.top();
    st2.pop();

    int n = tt.size();
    for (int i = 0; i < n - 1; i++)
    {
        int val1 = tt[i] - '0';
        int val2 = tt[i + 1] - '0';
        int f = (val1 + val2) % 10;

        string str = tt.substr(0, i);
        str += char(f + '0');
        str += tt.substr(i + 2);

        int pos = str.find_first_not_of('0');
        if (pos == string::npos)
            continue;

        str = str.substr(pos);

        if (!mpp2.count(str))
        {
            mpp2[str] = 1;
            st2.push(str);
        }
    }
}

int maxi = INT_MIN;

for (auto &x : mpp2)
{
    string s = x.first;
    if (mpp.count(s))
    {
        maxi = max(maxi, (int)s.size());
    }
}

if (maxi == INT_MIN)
    cout << "-1\n";
else
    cout << maxi << "\n";

} ```

I have a question regarding the last problem.

So it's established by now that when $$$n\leq 100\,000$$$, a quadratic solution exists. My solution was essentially "go right to left, maintain the function $$$x\mapsto$$$ how much we'll have in the end if we start with $$$x$$$, we only need to know its values for $$$x\leq 2n$$$, we'll have to do like 3 memcpys every time". But I couldn't squeeze those memcpy(to, from, cnt * sizeof(int)) (it took about 1.6s on my maxtest in custom invocations). I managed to squeeze this solution by making each function value take 3 bytes instead of 4, so that we memcpy less stuff, but do people maybe know how to memcpy faster? I found some like intrinsics and stuff blog from @sslotin, is it the best known way to memcpy?

Perfect, it is my first time to join it.I feel funny and I enjoy to solve it

plz release the tutorials soon

Amazing round

How can I become a trusted participant?

for those who are ranting about B it was such an easy greedy just get smallest 1st and 2nd part but yeah remember while getting 1st part if you have more 1s then 2 and 3 and the next no. is 3 inlcude it in your set of 1st part(this was the only idea that was to be thought) ~~~~~

include <bits/stdc++.h>

using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; vector inp(n); for(int &x:inp) cin >> x; int cn1=0,cn2=0,cn3=0; int prt1=-1,prt2=-1; for(int i=0;i<n;i++){ if(inp[i]==1) cn1++; else if(inp[i]==2) cn2++; else cn3++; if(cn1>cn2+cn3 && i<n-1){ if(inp[i+1]==3){ prt1=i+1; break; }} if(cn1>=cn2+cn3 && cn1>0){ prt1=i; break; }} cn1=0; cn2=0; cn3=0; for(int i=prt1+1;i<n;i++){ if(inp[i]==1) cn1++; else if(inp[i]==2) cn2++; else cn3++; if(cn1+cn2>=cn3 && (cn1>0 || cn2>0)){ prt2=i; break; } } if(prt1>=0 && prt2>=0 && prt2<n-1) cout << "YES" << '\n'; else cout << "NO" << '\n'; }} ~~~~~

Problem C was interesting. Couldn't solve D, E or F, though. This CF website looks awesome though, just tried it a few days ago

Another FST T_T, why me (:)|( ಥ_ಥ

When will the editorial get posted? My solution got TLE for $$$F$$$ and I'm so interested to see and read the solution for it...

I am new to this, But this contest was rated right...?

about how long does it take for Ratings to come out?