Thanks for the participation!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Before contest

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

3 days

Register now »

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

3 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 155 |

5 | -is-this-fft- | 150 |

6 | Petr | 148 |

6 | SecondThread | 148 |

8 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

Thanks for the participation!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round 954 (Div. 3)

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2024 03:11:40 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Fast Editorial♥

why are you posting this type of comments, this is for discussion not for this.

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.

64-bit integer i assume

Are you saying that the default 32 bit int isn't big enough? If so: I resubmitted and replaced everything with long long, and it got the same WA. So the error is for another reason.

your code is wrong

Could you be more specific? I know that the code is wrong, but I'm trying to find where I made an error.

I think this is what causes WA, in this case n=3 and s[1]='0', so there are 4 total variants: if string s='a0b', then the variants are 10*a+c, a+c, 10*a*c, a*c. You always chose variant a*c, but if for example s=303, then your code outputs 9, but the correct answer is 6 (a+c).

Ah, you're totally right. Thank you for catching this!

You're welcome

for problem A you can brute force it

E was awesome!!

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

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

pass the matrix by reference instead of value

bool testCondition(vector<vector>matrix, int i, int j, int n, int m)

Use pass by reference here,

bool testCondition(vector<vector>&matrix, int i, int j, int n, int m).

thanks , as a Java user i didnot checked that haha

I think the problem is that you are passing the $$$matrix$$$ array to $$$testCondition()$$$ by value, which creates a whole new $$$matrix$$$ object. What you need to do is pass it by reference, using the

&operatorHey, every time you run

`testCondition()`

you end up copying over the entire matrix, which is slow. To avoid this you can do place a & before the matrix, so instead of passing over the entire matrix, you're just passing over the pointer to it. This changes your function fromTo

Submitted and it worked 267088502

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?

I think it's about accuracy. you must write a code with good constant to pass hard version

It's a memory thing. My solution for G1 takes around 70MB so on G2 it gives MLE

There are $$$O(n \sqrt n)$$$ and $$$O(n \sqrt n log \ n)$$$ solutions that pass the easy version

Had fun! Thanks.

super fast editorial

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.

Oh yes I fell into that trap :( I spent a good 15-20 minutes trying to optimize iteration using bit mask meanwhile the O(n) solution is not that difficult to realize at all...

I wrote the logical, O(n) solution during contest but later found the bruteforce easier

same i spent 30 min for writing dp, as i am practising dp already these days , but i was not able to write correct recurssion , can anyone give solution using dp ?

`int f(int i, string s, int canSkip, int k) { // Base case if (i == s.length()) { return k + 2 == s.length() ? 1 : 1e9; }

}

void solved() { int n; cin >> n; string s; cin >> s; cout << f(0, s, 1, 0) << endl; }`

This was my code please correct it ,not memorzied it but then its the easy part , can u just correct my recurssive code

check my submission I used easy recursion https://codeforces.com/contest/1986/submission/267070013

If you have any questions let me know

Visit this code 267035503 i have used DP to solve this problem

Yeah, even I spent $$$40$$$ min thinking of a bitmasking approach, but I kept calculating how much time it would take. When the bitmask I ran locally took $$$15600$$$ ms for $$$t=10^4, n=20$$$ for all $$$t$$$, I decided it must be a greedy approach.

TRUE!!!!!!!!

brute force approach o(n*n) https://codeforces.com/contest/1986/submission/267238262

Detailed Video Editorial English

C : https://youtu.be/w7yaIcNz_1w

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

E : https://youtu.be/dCtiB_TRfms

https://codeforces.com/contest/1986/submission/267100334 [My submission]

I am getting WA on 2nd test case ? Why

Edit -> Solved by another algo

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$$$?+1

I actually find the time limit is super tight. With the same core idea, it takes me dozens of iterations to make my Java solution be accepted, with lots of optimizations to reduce runtime and a special handling for the scenario of test 76. A time limit of 4 second instead of 3 would be better. The tight memory limit prevent me from using more time-efficient lookup table but is relatively less critical than time limit in my case.

Yeah also the same issue for me. my cpp submission was running between 3.0 and 3.1s (checked in gym clone Contest) and not being able to pass after experimenting a lot with using maps instead of vectors and vice versa, adding pragmas etc. At the end i managed to get AC by starting my sieve from 2, since i don't need the info that 1 divides every number and got AC in 2.9s.

No sample code?

the algorithm is easy enough for you to implement yourself. so do it as a challenge

PS: first time 5 ac before system tests on a div3 :))

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

no

can someone explain how to solve problem B? I was really stuck in problem B, especially thinking if the a[i][j] is a corner piece, edge piece, or neither. Thanks, really appreciate it!

are we just trying to find the minimum of maximum adjacent cells of a[i][j]?

We have to modify the array in such a way so that there's no element greater than either of its adjacent cells, and return the total number of such modifications we might have done to form the required array. You might not have to write different code for corner/edge/center piece, you can write code such that it wouldn't matter. I think you'd gain clarity if you see someone's submission

for the corners just increase the size of the grid by at least 2 like if it's 5 5 you make it 7 7 and also start indexing from 1 not from 0

that way you don't have to worry about i+1 or i-1

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

Why not use Tarjan's algorithm?

It can solve the problems more than find bridges.And this method is interesting.

damn!!!

An alternative way to avoid LCA is finding a DFS tree instead of a spanning tree, in such a way that all the extra edges go from a node to one of its ancestors.

Your both solutions are very interesting. Thank you.

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 ??

i use dp to tackle the case of odd numbers :))

didn't wanna use prefix/suffix sums cause i don't wanna go that way

can you explain a little bit your dp code ?

Can you explain how you used DP for that? I am unsure how to use a prefix/suffix array to find which odd index to remove. Can anyone explain how to do it optimally

this is my code: 267060049

for clarification!! (cause most are confused by the dp)

here i define "legal" as a legitimate way to insert elements into the array, which means that an element cant be used twice.

dp[i][0] is the optimal cost if we chose vv1[i] dp[i][1] is the optimal cost if we chose vv2[i]

this is to make sure all moves are legal, cause vv1 and vv2 are seperated.

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)

Code herewhat is prev ?? I feel it's the same as can skip

ok I got it I think you can also convert canskip to third value to ensure that we don't take 2 NEIGHBOURING numbers twice which will make it 3 states only and also we don't need left because you can check at the end if canskip is used or not

ah yes sure i can also remove canskip and just make it a 2*n dp, prev here is a bool which checks if we are making this partition as a 2 sized partition or not and as we can do that once i used canskip for that, but it's redundant as you said

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.

Codeforces actually gives you large stack space (256MB) for C++. See the

`--stack=268435456`

flag given in the compiler options..

n-2 operands are to be used, you used 4 operands

the Editorial Is not listed within the contest

problem c has a similar idea to this

Can someone explain problem G

C has been hacked? How?

Fast Editorial!

What is actually the "count array" in G2?

since no one replied let me try...

for A/B, C/D...; count array keeps track of D-s of C-s which is divisible by B. here B is the fixed b_i in the editorial; A=a_i, C=a_j, D=b_j. then to calculate their contribution to the answer you go through divisors x_1, x_2, x_3... of A and sum all count[x_1]+count[x_2]+... for the final answer. because for each B; you search for C which is divisable by B such that D from C divides A.

lets say you have 6 at index 7, 14 at index 3, 19 at index 7 and 21 at index 9(by taking gcd-s this will become 7/3). so actually you have 6/7, 14/3, 19/7 and 7/3.

as said in the editorial you iterate through b_i-s, so actually you iterate through denominators {7,3,7,3} and let's say you are at the first 7.

(so the input corresponding to 6/7)

you wanna check how many other fractions exist which have a number divisible by 7 in nominator and number which divides 6 in denominator. to do that you go through all the elements whose nominator is divisable by 7 i.e. {14/3,7/3}. then for each element you mark their denominator with count array, so in this case you process count[3]++ two times so you get count[3] = 2. count[x] = 0 for every x except 3.

as a next step (the part with "Now, for a fixed b_i" in the editorial); you go through all nominators which have 7 in denominator so through {6/7, 19/7}. for every such element go through their divisors; so for 6; you go through 1,2,3,6; and you update your answer with count[1]+count[2]+count[3]+count[6].

check my submission which passed in 2999ms (シ_ _)シ check

`unordered_map <int,int> count`

in my code 267200592check out my latest comment below

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.

yeah, This was the only observation I missed during contest, literally did everything else.

Same. My Idea was that it was optimal to remove either the very first element or the very last element, but by the time I realised middle elements could also be removed for an optimal answer, it was too late.

Was going through the comments, was pretty sure someone might've asked the same question. Thanks for explaining it as well.

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

system test going on The submissions are being judged again with more test cases(all the hacks are included in the new set)

So, the Solutions will now also run for the Successful Hack Test Case for all Participants? Does that mean if I got an AC now my solution was not hackable in the hacking phase?

Yes. Thats the whole point for open hacking phase. If you get AC now that means no successful hack could have been used to hack your submission

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 ???

It would be better to include your submission in the comment. I guess this test case will help you explain. Assume n as 5 and k as 1 elements are 1,8,3,20,19. sort it you get 1,3,8,19,20 by your approach you will pair 1 and 3 then 8 and 19 but optimal pairing is 1 and 3 then 19 and 20. You may fix this but this method would still give tle.

Yes because I have to exclude one element if the size is odd I'm trying to come with an approach to exclude that one element in O(1) instead of the O(n) am I close ?

You are actually calculating it in O(n2). (Excluding every element and trying to get the number of operations). Your approach seems incorrect or very high complexity. If possible include your submission

https://ideone.com/xHwj6U this is O(n^2 logn) I know but am I even on the right way like can I optimize this ? or my whole approach has to be changed ?

I suggest you to read the editorial. You may try grouping elements based on ai%k (Obviously two numbers with different remainders can't be paired). If more than one group has odd number of elemnts then return -1 or proceed with your original approach for each group (here you wont have to check if the numbers can be paired or not cause it will always be possible to pair numbers in the same group) for even size groups just pair b1 and b2 b3 and b4 and so on. For one odd size group if it exists you have to find that one element which you need to exclude.

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

can you brief about your DP solution? what are the params of the recursive function and the recursive function?

dp[i][j][k] represent minimum value till the ith index and operation used is j and the integer value of previous string is k . Actually since we have to do exactly (n-2) operation, the previous string's size can go to max 2 and that we can store by assigning maximum value of k =100.

I think in Problem-D solution the case where a "0"(zero) exists the answer must be zero, is missing a case where n==3 because you will see p0q, which will not lead to zero, it will lead to min(p*10+q,p+q,p*10*q). Else everything is fine

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

Hint 1We can see that we have to take two adjacent numbers and rest will be one digit per operator....

Hint 2Maintain a DP of 2 states, till ith index if we have taken that 2 digit or not, so the dp will look like dp[n][2]....

Code for Reference267060168

Can you please review this code and help me debug.

CODE}

Update : Final AC code:)

Spoilerdo you have dp for E

u doing dp[i-1]* val

but if if u have ( a1 + a2 + a3 * a4 )

a4 will be multiplied by a3 only , but in ur code u r checking multiplied by the prefix

how this leads to the correct answer ?

i think i got, bcz we only do the multiplication if a[i] == 1

so only this case will be covered and this is what we want

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

maybe cause of the overflow of upper and lower?

upper and lower are always between 0 and n, and they are both long long

it is possible to upper is less than zero( upper < 0) underflow and lower is greater than n-1 ( lower >= n) overflow But your code is right and i got ac without any change check it https://codeforces.com/contest/1986/submission/267226535

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

but considering that only 25% of people got A also got D, i'd say it's pretty reasonable (and also, this is div3, second easiest division)

I'll say around 500-800 people cheated there way to D.It's kinda disheartening,my positive delta keeps shrinking even with similar ranks, and negative delta keeps on increasing. In the last div2,I did first 2 in 17mins,got a rank of 5700, and a delta of -5,even when my rating was just 1203, we are now expecting pupils to do div2 C too now,to just remain a pupil?

im afraid so :). even when i do C on a div2 (as a pupil), the rating bump is almost nonexistent.

Man dropped editorial as soon as the contest ends. Nice work.

F was amazing! Please add more graph problems in Div3

Can the F one be done using DSU?

why did i get runtime error for problem d? Please help me out 267184148

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 case

`n=3 and s='901'`

whose answer will be a 9 and not azero.yes if number of operations are 1 or n=3 then the answer would be zero only if the 0 is at the ends of number.

`If all numbers are 1, the answer is 1. We can simply place all signs as ×.`

This is incorrect as well. Simple test case would be

`s = "111"`

and the answer should be`1 * 11 = 11`

Yes

You did this process

after you had $$$n-1$$$ numbers.I think in D if all numbers are 1 then answer should be 11 not 1 because we will need to concatenate two numbers.

If all numbers after the concatenation are 1, then the answer will be 1. We can't consider this before the concatenation.

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)

Solution is the same, just brute force without heuristics.

I didn't able to guess it at the contest time! Sad Life!

I don't think the reasoning is correct, although the algorithm will yield correct outputs accidentally.

`1 + 2 * 34`

, since`34`

goes first.`(12 + 3) * 4`

but not`12 + 3 * 4`

.However, the algorithm yields correct outputs since it follows the correct reasoning by accident.

`0`

,`num`

will be`0`

.`1`

,`num`

will be unchanged.`num += cur`

.In case of minimization, it's always

correct. Because the intuition behind is that You never want to multiply number that gives greater result than just adding those two numbers. And that's what asked in the problem statement.can tell me anyone what is wrong in my code 267195219 // i have basically find every 2 digit pair and min number towards left and towrards right and then left — central — right 4 cases * * + * * + + + it is frustrating

Why this contest is showing in unrated?

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

Clean and fast Editorial

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

Good site to learn about bridges.

Can anyone please review my Dp soln and tell what is wrong here, either any logical error or overflow. The output seems like it is an overflow, if it is then how should i avoid it?

CODE}

Update-1: The Base case was wrong and in if(taken){} there should be "true" in further recursive calls. Base case:

This helped in avoiding overflow and correct output on many test cases but for few test case the answer was wrong.

Update-2: Final Accepted code :)

CodeCan anyone tell me whats wrong with my prefix and suffix handling in problem in case of odd length 267095361

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.

Ok, I managed to understand that. If I have an edge (u,v) that is a bridge, then when I pass from u to v in the dfs, I cannot go back to u anymore, so the number of nodes visited after v is the number of vertices in the other component after a disconnection.

Lets say you found the bridges between i and j. But we also need to find the sizes of the components i and j which we can be done efficiently by maintaining a subtree size where every subtree size of a node can be calculated during the dfs traversal. This way we dont need to calculate subtree size individually for each bridge.

After that the size of component i will be

`subtree[i]`

and j will be`n-subtree[i] or subtree[j]`

. Now we just need to minimize the ans which is`(subtree[i]*(subtree[i]-1))/2 + (subtree[j]*(subtree[j]-1))/2.`

My submission : 267232116

would not we will need to use rerooting approach for finding subtree of a node. as if (u,v) is a bridge then the precomputated subtree[u] will store no of all nodes which are below u not above.

In problem E any one can help on how to approach the idea of excluding one element using DP

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

why show node for us? still have questions

Can anyone pls provide cpp code for E problem , doing the same thing but got tle

you can filter search the submissions section

/* https://codeforces.com/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--) {

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

} ~~~~~

maybe the unordered map. it's been mentioned before that unordered_map can run in O(1), but in worst case O(n^2). this can be used in hacks.

my solution got AC with the same algorithm, and i used map.

I can confirm that this was the case for me as well

my TLE submission with unordered_map: https://codeforces.com/contest/1986/submission/270152201

submission replacing unordered_map with map https://codeforces.com/contest/1986/submission/270152730

Related read that I found https://codeforces.com/blog/entry/62393

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

i'm not too sure, but it seems like tha algorithm is wrong

using your algorithm (sorry if i'm wrong, that'd be embarrsaing) and the test 1117

the smallest 2 digit number is 11 the optimal cost if u use 11 is 11 x 1 + 7 = 18

but the optimal cost is 1 x 1 x 17 = 17

upd: just realized i'm wrong here.

nope it will take 17 as optimal number and cost 17. try another test case it might give wrong it is wrong for 500 something number in test case 4

my submission for B. works on my computer but not here :267313352 Help.

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<std::map<int, int> >}$$$ 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) > 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.com/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.

I think the issue is with the odd number of elements (where the middle element is matched with itself). In this case, you cannot place any element in the middle, you need to choose one optimally.

For the above testcase, it is optimal to place to place 10 as the middle element but your code uses 28 as the middle element.

Ah, I see. Thank you!

hey how i can increase my speed in contest a guy solves the same number of problems as me but got much better rank than me

Has Anyone done the DP solution for the D problem?

I think it can be solved using the Partition DP pattern(Similar to the MCM problem), but I couldn't able to code it.

Thanks in advance.

my solution for 1986B-15 is shown to give wrong answer on test case 3 i cant find the reason

https://codeforces.com/problemset/submission/1986/268558565

Can anyone tell me what is wrong with this solution for the problem F? I find the bridge and calculate the maximum pairs of vertices not reachable, then the answer is $$$ n * (n + 1) / 2 - pairs_cut $$$. But I think I messed up because some answers are negative.

Code.