Fast Editorial♥

Can anyone tell me what's wrong with my solution for problem D? 267065372. It's a simple brute force solution but I still got WA on test case 2.

why does my submission give TLE on test 3 , for problem B

https://codeforces.me/contest/1986/submission/267087342

I wondering for G, the constraint on n of hard version differ from the the easy very with only 5 as muplicatif factor. As in the editorial the complexity of hard is nlogn what's the expected complexity of the easy version?

The problem setter is very clever i mean look at the constraints(n=20) of problem D which forces you to think a some bruteforce or some DP approach so no one will go to the logical part of that which is easy at all.

Detailed Video Editorial English

C : https://youtu.be/w7yaIcNz_1w

D : https://youtu.be/UZ-zb7NZrRU

E : https://youtu.be/dCtiB_TRfms

Good round! I enjoyed it.

Why the sooooooo tight memory limit in problem G? I didn't see any reason to reject solutions on the memory constant factor!! Or do you really have a meaningful $$$O(n)$$$ memory solution? Anyway, if an acceptable solution uses $$$1\cdot n\log n$$$ memory, why to reject $$$2\cdot n\log n$$$?

No sample code?

Can anyone please tell me why my solution 267122161 for Problem D is giving Wrong Answer on test case 2?

For problem F, I used a unique method yesterday to find the bridge edges in this graph (which seems to be an undirected graph). While some parts may be a bit technical, I want to record and share it with everyone.

First, I used a union-find data structure to find a valid spanning tree (assuming that edge weights are directly assigned to the child nodes). Then, for the remaining edges $$$(u_i, v_i)$$$ that are not in the tree, I increment the path $$$(u_i, v_i)$$$ by one, because this forms a cycle, and cycles do not have bridge edges. This can be achieved through the LCA (Lowest Common Ancestor) and tree difference methods.(maybe this name, sorry for my poor English.)

Here is the submission. 267081057

However, after careful consideration, I realized that we can use a hashing and xor approach. Each time we cover a path, we assign a random value in the range $$$[0, 2^{64})$$$. Due to the properties of xor, the values will cancel out above the LCA, which is equivalent to checking if the path has been covered. Finally, we just need to calculate the subtree sizes in the tree and update the answer accordingly. This method eliminates the need to find the LCA.

Here is the submission. 267125590

Very interesting problemset .

my lazy brain could only thought of the dp solution for the problem E. Am I too dumb to realise the claver and O(N) soln of author ??

Man, I overthinked a lot on D and at last ended up doing it with DP, i got tle because i was using n^4 * t, but just with a simple change (removing prev index and using a bool at its place, as partition can be either of size 2 or 1 I was able to Pass it)

ll rec(int i, int prev, int left, int canskip, string &s, vector<vector<vector<vector<ll>>>> &dp)
{
    ll n = s.length();
    if (left == 0)
    {
        ll val = stoll(s.substr(i, n - i));

        return val;
    }

    if (dp[i][prev][left][canskip] != -1)
    {
        return dp[i][prev][left][canskip];
    }

    if (i >= s.length())
    {
        return 1e9;
    }
    ll add = 1e18, mul = 1e18;

    if (prev)
    {
        add = stoll(s.substr(i-1, 2)) + rec(i + 1, 0, left - 1, canskip, s, dp);
        mul = stoll(s.substr(i-1,2)) * rec(i + 1, 0, left - 1, canskip, s, dp);
    }
    else
    {
        add = stoll(s.substr(i,1)) + rec(i + 1, prev, left - 1, canskip, s, dp);
        mul = stoll(s.substr(i,1)) * rec(i + 1, prev, left - 1, canskip, s, dp);
    }
    ll dont = 1e9;
    if (canskip)
    {
        dont = rec(i + 1, 1, left, 0, s, dp);
    }

    return dp[i][prev][left][canskip] = min(add, min(mul, dont));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    gin(t);
    while (t--)
    {
        gin(n);
        string s;
        cin >> s;
        vector<vector<vector<vector<ll>>>> dp(n + 1, vector<vector<vector<ll>>>(3, vector<vector<ll>>(n + 1, vector<ll>(3, -1))));
        cout << rec(0, 0, n - 2, 1, s, dp) << endl;
        // Always check if the input is 2n
    }
    // cout<<fixed<<setprecision(10);
    // cerr<<1000*((double)clock())/(double)CLOCKS_PER_SEC;
}

Either codeforces has a bigger stack or I suspect weak tests for problem F. My recursive DFS got AC and locally I am able to segfault it with giving it a path on 10^5 vertices.

What is actually the "count array" in G2?

In problem E, why is it advantageous to consider only the odd indices for removal if $$$m$$$ is odd?

Edit: I get it now. Choosing even indices makes the answer worse because you are now pairing up non-adjacent elements, which makes the answer larger.

Why my problem B solution is still in queue☠️, Although I remember that it was accepted last night

in problem E I'm sorting the array and matching each element with the closest one but this greedy is giving wrong at test 10 my answer is 15 but the correct is 14 is this approach really wrong ???

If anyone searching for dp solution for problem D. Here is my solution that got accepted:

ll dp[21][21][101];
ll helper(ll i, ll cnt, string s,string a1){
    ll n=s.size();
    if(a1.size()>2){
        return 1e9;
    }
    else{
         if(cnt>n-2 || i>n){
        return 1e9;
    }
        ll y=stoi(a1);
        //debug(a1);
        if(cnt==n-2 && i==n){
        return stoi(a1);
    }
    if(dp[i][cnt][y]!=-1){
        return dp[i][cnt][y];
    }
    ll a=INF,b=INF,c=INF;
    string x="";
    if(cnt<n-2 )a=stoi(a1)+helper(i+1,cnt+1,s,x+s[i]);
    if(cnt<n-2 )b=stoi(a1)*helper(i+1,cnt+1,s,x+s[i]);
    c=helper(i+1,cnt,s,a1+s[i]);
    return dp[i][cnt][y]=min({a,b,c});
    }
}
void solve()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    string a="";
    a+=s[0];
    memset(dp,-1,sizeof(dp));
    //<vector<vector<ll>>>v(n+1,vector<vector<ll>>(n,vector<ll>()))
    //debug(help("2+3+3+11"));
    //map1[a]=1;
    ll ans=helper(1,0,s,a);
    //debug(map1);
    print(ans);
}

For Problem D : Simple DP solution in O(N)

Why did i get a run time error for C? 267036690

The cheating is going out of hand,I refuse to believe that more than 6k did D.

F was amazing! Please add more graph problems in Div3

Can the F one be done using DSU?

74TrAkToR There is a mistake in the Problem-D editorial.

You mentioned If there is at least one 0 , the answer is 0 . We can simply place all signs as ×.

This is not true even for a given test casen=3 and s='901' whose answer will be a 9 and not a zero.

why such tight memory constraints on G? why cannt they give more memory???? I got G1 accepted, and G2 was MLE on 43rd testcase... sad life...

Problem 1986D - Mathematical Problem solution:

Key observation: As we can use only n-2 sign (+, x), so there must be at least one two-digit number. Then just find the minimum answer as asked.

-Time Complexity O(n ^ 2)

        int n; 
	string s;
	cin >> n >> s;
	int ans = INT_MAX;
	for(int i = 1; i<n; i++){
		int num = stoi(s.substr(i-1, 2)); 
		for(int j = 0; j<n; j++){
			if(j==i-1 || j==i) continue;
			int cur = s[j]-'0';
			num = min(num*cur, num + cur);
		}
		ans = min(ans, num);
	}
	cout << ans << '\n';

Can someone explain for F. How to Find if a edge is a bridge or not.

Can someone explain me F better? I can find the bridges, but can't go any further. Run a single dfs in each bridge will get TLE. I didnt get the size of subtree part.

Changing map to a sorted vector of elements + binary search works in G2, the time complexity is the same but i can't figure out why it removes the MLE i get with map, since intuitively, i am storing count in map and elements in vector, the storage in map is more sparse, is this happening because in testcase 43 the array values are such that, it leads to lower count values in map and thus, reducing the advantage of sparseness?

Map submission

Vector submission

/* https://codeforces.me/contest/1986/submission/267290277

can anyone help me ?I am getting TLE in test case 27. Thanks in advance/* ~~~~~

include <bits/stdc++.h>

using namespace std;

define pi (3.141592653589)

define mod 1000000007

define ll long long int

define all(c) c.begin(), c.end()

define min3(a, b, c) min(c, min(a, b))

define rfl(i, a, n) for (int i = n — 1; i >= a; i--)

define fl(i, a, n) for (ll i = a; i < n; i++)

define ct(x) cout << x << endl

define rd(a, n) fl(i, 0, n) cin >> a[i]

define wrt(a, n) fl(i, 0, n) cout << a[i] <<

define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

// char Array to int Using atoi() like string s // C++ string to int Using stoi() like char str[50]

int main() { fast int t = 1; cin >> t; while (t--) {

ll i,
    j, k, n;
cin >> n >> k;
ll arr[n+5];
rd(arr, n);
unordered_map<ll, vector<ll>> mp;
sort(arr, arr + n);

fl(i, 0, n) mp[arr[i] % k].push_back(arr[i]);

ll ans = 0;
ll odd = n % 2;

ll oc = 0;
for (auto it : mp)
    if (it.second.size() % 2)
        oc++;

if (n % 2 < oc)
{
    cout << -1 << endl;

continue; } for (auto &it : mp) { int sz = it.second.size(); if (sz % 2 == 1) {

ll s = 0;

            vector<ll> pref(it.second.size() + 5, 0);
            for (int i = 0; i < it.second.size(); i++)
            {
                if (i % 2)
                    s += (it.second[i] - it.second[i - 1]) / k;
                pref[i] = s;
            }
            // cout<<endl;

            s = 0;
            ll temp = 1e18;
            for (int i = sz - 1; i >= 0; i--)
            {
                if ((i % 2))
                {
                    s += (it.second[i + 1] - it.second[i]) / k;

                    // pref[i]=s;
                }
                else
                {

                    temp = min(temp, pref[i] + s);
                }
            }

            ans += temp;
        }


    else
    {

        for (int i = 1; i < sz; i += 2)
        {
            ans += abs(it.second[i] - it.second[i - 1]) / k;
        }
    }
}

cout << ans << endl;
}
return 0;

} ~~~~~

can anyone tell the problem with my code on D 267075434 it was wrong on test case 4 https://codeforces.me/contest/1986/submission/267075434

Would like to add some of my thoughts on G to the discussion, this might be a more intuitive approach.

The first step is still to simplify $$$\frac{p_i}{i}$$$ to $$$\frac{a_i}{b_i}$$$. Now we can write out the following brute force pseudocode:

$$$\texttt{for } a_i:$$$

$$$\quad\texttt{for } b_j | a_i:$$$

$$$\quad\quad\texttt{for } a_j:$$$

$$$\quad\quad\quad\texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad\quad\texttt{res += } f(a_i,b_i)f(a_j,b_j)$$$

Where $$$f(a,b)$$$ counts the number of datapoints with simplist form $$$\frac{a}{b}$$$. This is sparse with at most n entries, so we can use something like $$$\texttt{std::vector \lt std::map \lt int, int \gt \gt }$$$ to represent it.

Now we can reduce the number of loops by precalculating a "factor prefix sum" on the table $$$f$$$. The idea is very similar to prefix sum. Let's denote $$$g(a,b) = \Sigma_{b'|b}f(a,b')$$$. Then

$$$\texttt{for } a_i:$$$

$$$\quad\texttt{for } a_j:$$$

$$$\quad\quad\texttt{res += } g(a_i,a_j)g(a_j,a_i)$$$

An elegant form! Unfortunately it doesn't work. Aside from the double loop, we now have a dense table $$$g$$$ (just consider the edge case that $$$f(a,1) = 1$$$ for any $$$a$$$, then $$$g$$$ would have positive value for every $$$(a,b)$$$ pair). So even building the table would take $$$O(n^2)$$$ space and time.

The trick is to change the subscript that we perform the sum operation. Let's first rearrange our original brute force algorithm:

$$$\texttt{for } b_j:$$$

$$$\quad\texttt{for } b_j | a_i:$$$

$$$\quad\quad\texttt{for } b_i:$$$

$$$\quad\quad\quad\texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad\quad\texttt{res += } f(a_i,b_i)f(a_j,b_j)$$$

So we first loop over each $$$b_j$$$, then all multiples of $$$b_j$$$, then each $$$b_i$$$, then all multiples of $$$b_i$$$.

Similar to $$$g$$$, define the prefix sum table $$$h(a,b) = \Sigma_{a|a'}f(a',b)$$$. Then we have

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i:$$$

$$$\quad\quad \texttt{res += } h(b_j,b_i)h(b_i,b_j)$$$

The difference between $$$h$$$ and $$$g$$$ is that $$$h$$$ is sparse: we can see that each $$$(a,b)$$$ adds its $$$f$$$ value to exactly $$$\sigma_0(a)$$$ points (the number of divisors of $$$a$$$), so in total the space complexity is $$$O(nlogn)$$$.

Finally because the table is sparse, we can optimize the double loop as well, by just looping over the keys with positive value:

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i \texttt{ in } [b_i | h(b_j,b_i) \gt 0]:$$$

$$$\quad\quad \texttt{res += } h(b_j,b_i)h(b_i,b_j)$$$

If we are use map here, the time complexity would be $$$O(nlog^2n)$$$. This solution should be good enough to pass G1. implementation

However, the $$$O(nlogn)$$$ time is not good enough to pass G2 (or maybe it is, just that map has a big constant, but let's just push for the best solution). How do we optimize this? A natural thing to do for those 2D tables is to optimize away one of the dimensions, usually the row dimension. However, currently our algorithm uses values from both $$$b_i$$$ and $$$b_j$$$ row, so for one of the rows, we need to sacrifice some extra time to calculate the prefix sum from the raw $$$f$$$ table directly. Since we are looping in $$$b_j$$$ first, let's replace $$$h(b_i,b_j)$$$ with its definition (based on $$$f$$$):

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i:$$$

$$$\quad\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad \texttt{res += } h(b_j,b_i)f(a_j,b_j)$$$

Now $$$h(b_i,b_j)$$$ only uses information from the current row, $$$b_j$$$. To illustrate this, let's change its notation to $$$h_{b_i}(b_j)$$$ (this is in fact the "count array" the official editorial is referring to), so it becomes a 1D table.

Change the order of loop:

$$$\texttt{for } b_i:$$$

$$$\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad \texttt{for } b_j:$$$

$$$\quad\quad\quad \texttt{res += } h_{b_i}(b_j)f(a_j,b_j)$$$

This order change allows us to utilize the sparsity of table $$$f$$$:

$$$\texttt{for } b_i:$$$

$$$\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad \texttt{for } b_j \texttt{ in } [b_j|f(a_j,b_j)=1]:$$$

$$$\quad\quad\quad \texttt{res += } h_{b_i}(b_j)$$$

This algorithm should pass G2. implementation The time complexity is $$$O(200n + nlogn)$$$, where $$$200$$$ is the max number of divisors for numbers <= 5e5. Space complexity is $$$O(n)$$$.

Note that in the implementation you also need to take care of some duplicate cases.

Hopefully this helps those who are strugglign with this problem.

https://codeforces.me/contest/1986/submission/267420939

G2 Question can anyone help me, how to get rid of TLE.

Sorry for asking. Why doesn't my code work on problem E? Here's the submission.