Hello Codeforces!

On Jan/24/2023 17:35 (Moscow time) Educational Codeforces Round 142 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hey, Codeforces!*

*Preparations are under way for the second “Hello Muscat 2023” ICPC programming bootcamp, the continuation of the “Hello” bootcamp series, organised by Harbour.Space University, in collaboration with PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club and Codeforces!*

*Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 8 days intensive Hello Muscat 2023. It will take place in Muscat, Oman and online from March 8th to March 16th, 2023, both participation formats are available. As always, we can’t wait to see you there to learn, practice and compete on the international stage, smoothing your road towards the joined World Finals 2022 and 2023 in Egypt!*

*Our coaching line-up combines talent and experience, featuring ICPC world champions winners and finalists, as well as legendary names from the field of competitive programming: Mike Mirzayanov MikeMirzayanov, Yahor Dubovik 244mhq, Artem Plotkin Rox, Maksym Oboznyi MaksymOboznyi and Nikolay Budin budalnik.*

**The Bootcamp will be split into three divisions:**

**Division A.**Division A will be a mirror of the Petrozavodsk Programming Camp. Suitable for teams who already qualified for the world finals ICPC or are aiming that high.**Division B.**Designed to help teams prepare for the next season of ICPC regional competitions. Appropriate as an introduction for teams and students just getting their foot in the door of the world of ICPC and competitive programming competitions in general.**Division C.**Designed for newcomers to the world of ICPC competitive programming.

**Types of participation: On-Site and Online**

_We believe that participation in our Bootcamp should be accessible by all teams wherever they are and that is why we made onsite and online types of participation. **20% Early Bird Discount is offered to universities and participants who register and pay before Jan 31st 2023.**

**On-site:**

*Price: *

*What is included: training, contests, access to the recordings of the lectures, accommodation for 9 nights in a 4 star hotel Mysk, breakfast and lunch, transfer from hotel to venue every day, leisure, entertainment and welcome pack.*

**Online:**

*Price: *

*What is included: training, contests, access to the recordings of the lectures.*

*Good luck with the round!*

**UPD:** Editorial is out

Welcome to slow-rating-update round #142!

True. These rounds and div3 rounds take a lot of time. maybe because of hacking phase.

Welcome to slow-rating-update round #142!

Me after solving ABCD:

HI!:)

I'm not aware of this: I don't see this contest taken into account on rating because it's not yet processed?

Anybody noticed that quite hell unusual time of 26th Feb contest??!!

Yes, it's unbelievable.

Yeah,12 at night

OMG red round!!!

Hope for the best and prepare for the rest.(★ᴗ★)

Hope to get BLUE today!

Uchiha Madara, you have to be LGM

me too but the rating update is a bit slow

I feel like Educational Rounds are more Mathematical than usual rounds, is this the case?

sure

Good luck! Wish every participant have higher ratings!

no

hahah

Classic Mathforces.

None of A,B and C had anything to do with DSA

A was greedy, B was a math problem, C use binary search. 1 out of the first 3 problems of a div 2 round being math problems doesn't imply that a contest is "Mathforces" dumbass. Also, atleast don't be green and talk shit about a contest not having enough DSA problems.

Mind your language, this is not reddit/twitter. As for rating, I don't take these contest seriously nowadays. I at one point was Blue unlike someone who has never crossed 1500 xD

"Mind your language"- What you say matters as much as how you say it, so that's pretty rich coming from a guy who spouts shit like there's no tomorrow.

Also, I don't want to get into petty comparisons, but I have given like 7 contests till now, so I'm pretty sure my peak will be way above yours :)

Edit: The part about "someone who has never crossed 1500" didn't age well

Bro called me a dumbass for sharing my take on the contest and then preaching me.

And then Bro says he doesnt do pity comparisons but advices me to get out of green and then give my analysis on the contest.

Hypocrisy at its finest!

Considering your past rating you shouldn't have had any trouble doing A, B, or C... idk man skill issue

It's not about whether I am able to solve or not, its about the quality of questions. I was able to solve A and B but still complaining because there was no satisfaction solving those problems

of course you didn't have any satisfaction solving them, they aren't supposed to be hard for anyone above 1k rating

idk B was kinda annoying for me, C was good tho

what is "educational" about the problems in this round?

Does anyone know which test case was giving a lot of wrong answers in problem C?

mine were

5

1 2 3 5 4

and

3

3 2 1

how to solve c?

Problem C is the literal definition of million corner cases and i love it lol

Think about binary search approach

Huh? I have 0 corner cases.

(now someone will definitely hack me xd)

well, my first approach is to find middle positions not numbers, and when i realised that, i also realised the sample test cases has outsmarted me ._.

190436527 No corner cases whatsoever.

Nice problem D, it took a while before I noticed the name of the problem :) great hint

I quite liked problem C. I am pretty proud of an elegant solution I came up with inspired by some monotonic stack problems I was solving the other day.

Can you share the link to the problem which you are talking about?

can you share the approach to solve it, i completely didn't get the idea to appraoch this

how to solve 1st ?

My approach was to count the number of frequency and take their sum, and ans should be max to max n what is wrong in this?

My solution is to count number of 1-s in array and print n — (count_1 / 2).

Only double 1-s pair in the array can decrease operation times, so all you need to do is just count the pair's amount.

You can kill monsters of health 1 in pairs and remaining you can kill individually.

I was stuck with problem C. My code outputs correctly for samples and inputs I give. Perhaps I can't find the edge cases. Here is my code https://codeforces.com/contest/1792/submission/190399259 .

Counterexample:

Output should be 2. Pick (2, 7), then pick (1, 8). Your code seems to output 3.

Thanks, man. I didn't account if the numbers were not continuous.

Can anyone give hint how to solve third problem?

leave it there is an easy way to solve D then my way

A nice perfectly balanced contest. Kudos to the authors.

OMGGG solved E on 01.59.54 les goo

I tried to solve problem C with a monotonic stack but no luck.

how to solve 2nd problem

my approach was if we can have a > 0 then one joke from b and one joke from c and alternating it till either b or c runs out . so it's min of (b , c) + min jokes in total . now these jokes will balance it and bring it back to a . now if d > 0 i can take the min of d , a extra jokes . if( b or c ) are not 0 . add one more joke .

If $$$a = 0$$$, output $$$min(1, a + b + c + d)$$$.

Else the answer is $$$a + min(b, c) * 2 + min(a + 1, b + c + d - min(b, c) * 2)$$$

Can u explain how min(a+1,b+c+d-min(b,c)*2) come up .Beacause I am not able to figure it out

Take all $$$a$$$

Taking $$$1$$$ $$$b$$$ then $$$1$$$ $$$c$$$ until $$$b = 0$$$ or $$$c = 0$$$.

Now both of them will have $$$a$$$ points and at least one of them cannot get anymore points. You can take at most $$$a + 1$$$ from $$$b + c + d$$$.

both alice and bob will have a mood of "a" initially . now since we alternate between the other 2 jokes until one runs out, the mood for both will increase and decrease and end up with "a" again .

now finally if a is smaller than the remaining jokes you can have a+1 extra jokes else if a is much bigger than the remaining jokes it's just that remaining .

Dude if ur approach was right then why the heck did u NOT solve it during the contest.

screwed up with the implementation

D was nice combination of DP and trie.. loved the question

How is DP being involved? Do you store the answers so that you do not insert a permutation again?

no, You create

`dp[i][j] = Indices of all the permutations, which has '1' on i'th index and 2 on j'th index`

.Then, for each permutation, u can loop. this will give you ( 5 * 10^4 * 8! ) roughly... Also, u need to put break statement if you already found the ans of length 'm' .

You can follow my solution here.

ALAS, I was just 2 minutes late from finishing my final solution :( ...

If you need understanding my solution, feel free to ping me.

Unfortunately your solution got TLE at 31

yeah, it got TLE, I am resolving the errors. Sorry. I will update once done. Thanks :)

i freaking could not implement trie, i chocked and even forgot dynamic allocation !!!

If you are talking about D, straightforward polynomial hashing (without the mod) would do.

you mean rolling hash right? I could not think of this in contest, wasted an hour googling dynamic allocation and still could not do because of the stress of the contest.

Can you explain what polynomial hashing is? or post a link please. I'm having a hard time implementing D as well

polynomial hashing is basically encoding an array/string into a number. So for example the permutation $$$5, 3, 1, 4, 2$$$, you just encode it into the number $$$53142$$$. This way, you can easily compare array in $$$O(1)$$$, in order to binary search/use map

If you use map with vector it also works

Can you explain how that would work, I saw many submissions with maps but I can't seem to comprehend them? Im not able to understand how the map solutions are working.

Map remembers a value by their key, a key can be almost anything, even vector, so when you are itterating over an array and you are looking at what prefix should the other array have to get beauty of A with the array we are looking at, you can remember that prefix as a vector and use that vector as a key in map, and remember value 1 in map at that key. after doing that for all arrays, you are now looking for an answer for an array lets say C, you itterate over its prefixes, push them in vector, and for every prefix vector you check if you have written 1 in the map at the place of this vector( so you use this prefix vector as a key) if you have then you can get the beauty of the lenght of the prefix vector

If you use bitset it also works(of course you need to do some prework!)

I think I had an interesting approach for C, curious if anyone else had the same idea:

For i = 1 : n:

While queue.front() == min or queue.front() == selected, queue.pop(), min++ if queue.front() == min

Selected.insert(i, n-i-1), ans++;

Done! Return answer.

Damn. beethoven97 hacked LGM turmax's solution

For me C > E > D. I Spent more than 40 min on C and am still not able to solve it. What's the solution?

Think in terms of binary search. Can we solve the problem with $$$i$$$ operations? Now think what should the last operation be? What should the second to last operation be, and so on so forth ...

My reasoning was that if we select some elements, we will always select 1, n, 2, n-1, etc... The order we select them should not matter because some optimal ordering should exist anyways. So I created a queue and popped off elements while it was sorted. Then, whenever it was unsorted, I removed elements i and n-1-i from the array and continued to pop while it was sorted. The number of times you remove i and n-1-i is the answer.

Submission: 190357765

You can see that you can not use operation on numbers that are close to each other and ordered for example 4,5,6. 4,5,7 and 6,5,4 will not go. So if array is like this 4,8,7,5,3,2,1,6 you can do operation on every other number except these 3 numbers = 4,5,6, and answer will be max(min(numbers)-1, n-max(numbers)) = max(4-1, 8-6) = 3.

Just do n/2,n/2+1;n/2-1,n/2+2;... if n%2==0 or do n/2,n/2+2;... if n%2==1 and skip the first operations if they are already in place.

You have to find the longest

MIDDLEsubarray.The longest you can find is

`2 3 4`

.yeah that's what i did too, O(n) is great

Would C Problem be solved by 2 Pointers ? if not, then what?

Yes, 2 pointers is fine my submission.

Yes

Can someone give stress test for 2nd testcase on E? 190401625

A: Use first spell for 1-health monsters and second spell for others.

B: First tell all type-1 jokes, then tell type-2 and type-3 jokes alternately, until one type of jokes run out. Then tell all remaining jokes until someone leaves.

C: Take n=6 as example. First let ans=3=n/2, and check if the order of {3,4} is correct (which means, 3 appear earlier than 4 in the initial permutation), here 3,4 are "central" elements of 1-6. If it's not, we need ans=3 operations. Otherwise, we need to do ans--, and check the order of {2,3,4,5}. Do this repeatly until we fail at any check or we've checked the whole permutation. If n id odd, let k=(n-1)/2, start at ans=k and checking {k,k+1,k+2}.

D: We need to check the longest common prefix of ai and aj^(-1) (where aj^(-1) is the inverse of aj), we could store all aj^(-1) in a trie and find for all ai.

E: Didn't solved. Maybe we can let set s={d: m1*m2%d==0 && 1<=d && d<=n} and do loop for(d1:s) for(d2:s && d2>=d1) but I don't know if this approach will get TLE (for cases like n=1e9, m1=m2=735134400).

Stored all aj in a trie and searched for aj^-1, didn't realize the solution during contest. :(

D: Sort the permutations and For every prefix of every permutation, binary search permutations that match this prefix and use segment tree to update range

`(l <= i <= r) a[i] = max(a[i], x)`

. 190359788there is much more simple solution with trie :)

190383705

Any hints for E?

two pointers

In defense of this hint, my submission passed system testing with a two pointer-like approach: https://codeforces.com/contest/1792/submission/190397103.

Although upon further reflection, the analysis I had of its time complexity was not correct, so if anyone can come up with a proof of correctness (or a hack), that would be cool!

The main idea was to process the divisors in ascending order. Let the current divisor be $$$a$$$. We will maintain a pointer to the minimum divisor, $$$b$$$ such that $$$a / b <= n$$$. Then we just search from $$$b$$$ until the last divisor <= $$$n$$$. It feels like there might be an argument that the average number of elements we check is not too high, but I can't find it.

The dp solution seems much more straightforward to understand, so apologies for the misdirection.

Don't know for sure that this is the intended solution.

First, find all the divisors by brute force as the maximum number of divisors for (large) n cannot exceed cube root n. And for every divisor x below 1e9, remove the divisors of x until x*1e9 iteratively and update the answer.

Generate all divisors of $$$m$$$ (there's about $$$10^5$$$ of them in the worst case). For every divisor, instead of the minimum row where it appears, let's search for the maximum column (it's easy to see that these two are equivalent). So, for every divisor, we need to find its maximum divisor which is not greater than $$$n$$$.

This can be done with the following dynamic: $$$dp[d]$$$ is maximum divisor of $$$d$$$ not exceeding $$$n$$$. If $$$d \le n$$$, then $$$dp[d] = d$$$, otherwise iterate on the prime divisor $$$p$$$ in the factorization of $$$d$$$ and find the maximum of $$$dp[d/p]$$$.

Could you mention the time complexity of this approach? It's not immediately clear this solution can fit into time limit?

Something like $$$O(D \log D \log m)$$$, where $$$D$$$ is the number of divisors of $$$m$$$. There are $$$D$$$ states in the dynamic programming, each state has up to $$$\log m$$$ transitions (each transition corresponds to dividing by a prime from the factorization of $$$m$$$), and an extra logarithm because everything is stored in a map.

upd: Plus $$$\sqrt{m_1} + \sqrt{m_2}$$$ to factorize $$$m$$$.

More accurately, $$$D \le 105\,000$$$, "$$$\log{m}$$$ transitions" is actually $$$\le 15$$$.

And don't use maps for $$$dp$$$, use vectors.

How to not use maps? The factors of m could be large right?

I generated all divisors of $$$m$$$ . For each divisor $$$a$$$ , I brutely searched minimal row number within the range $$$[\lceil \frac a n \rceil,min(n, \sqrt a)]$$$ among divisors of $$$m$$$ .This naive solution seems to run very fast.

Is it reasonable to let this solution pass? I mean, this solution is unbelievably too simple, meanwhile hard to know exact time complexity.

My best guess is that for each divisor $$$a$$$, there's a big chance that you have to go through like $$$50$$$ divisors on average (maybe much less I don't really know) before finding an answer. You see, for highly composite numbers, aka numbers that has a lot of divisors, its divisors are also expected to have a lot of divisors, thus it is likely for the algorithm to encounter a divisor of $$$a$$$ in very few loops. For number that has less divisors, I think that there simply isn't enough divisors to make a simple $$$O(n^2)$$$ getting TLE

Why dp[d] = std::max(dp[d], dp[d / p]), I don't understand this, please explain it to me.

I think dp[d] must equal std::max(dp[d], dp[all_of_divisors(d)])

If you do dp[d] in order then dp[d/p1/p2] would've already been considered during the transition of dp[d/p1]

Oh, thank you so much

D could have been a really nice binary search + trie task if bounds were N<=1e5, NxM <= 1e5

Hmm bs, i think only Trie + dfs

Why binary search tho? You can just DFS down the trie, and the answer would simply be where the DFS end.

I feel bad when I heard that $$$O(n^2)$$$ solution can pass F2.

I feel worse when I really pass it after the contest. Here

I guess the author think D&C + fft is too slow, but it is not that slow, and is it reasonable to let $$$n^2$$$ solutions pass?

The problem F of last contest also be passed by some O(n^2) solutions.

Unfortunately, looks like really fast templates for modular arithmetics do the trick. I haven't come up with the D&C+FFT solution, the model one has slower asymptotics than D&C+FFT. So, basically, I could try one of the following two things:

I still think that 2nd is better choice. Maybe my mistake was even trying to distinguish $$$O(n^2)$$$ and $$$O(n \sqrt{n \log n})$$$. I am sorry for that, but I hope not a lot of participants were affected by the issue.

The formula is like $$$f_{i} = \sum{f_{j}\times f_{i-j}}$$$, in my memory it can be solve by D&C and fft(since $$$f_{i}=\sum{f_{j}\times g_{i-j}}$$$ for fixed $$$g$$$ can be solved) , but maybe I remember it wrong(I feel sorry), and I didn't figure it out during the contest.

However, OEIS A000311 shows that $$$ans = exp(f(x)) = 2f(x) - x + 1$$$, thus we can solve it by Polynomial Newtonian iteration($$$O(nlogn)$$$ maybe?).

I squeezed in $$$O(n^2)$$$ by precomputing for biggest n and putting it into the source code and running the $$$n^2$$$ normally for small $$$n$$$. I didn't use any very optimized modular arithmetic. 190408679 (there seems to be no test with a number in range of [3.5e4,4e4), so the runtime is misleading but testing the worstcase on custom invocation gives 4500 ms.

In fact we can directly get a formula using lagrange inversion. the final result (plus 2) is the $$$x^{n-1}$$$ coefficient of $$$2(n-1)!(\frac{x}{2x+1-e^x})^n$$$

Did any1 use strings for D?

I concatenated values in array and stored them in hashmap, but I did it because golang doesn't support custom key types in hashmap.

Yup! I did.

Could anyone help me understand why my code for D gives incorrect output here:

https://codeforces.com/contest/1792/submission/190405242

your answer would have been fine if r

_{j}= p_{qj}Thanks for helping. What makes this hurt more is that I would have got last 5 second AC instead of WA, had I not done that silly mistake xD.

It happens 😹 😹

Wait a minute, but wont p(q(j)) and q(p(j)) be like the inverse of each other, ie. they will produce each other?

For example, wouldn't the product of p = 3142 and q = 2413 be 1234 whether you take r = p.q or r = q.p?

No take this for example

2 4 1 3

2 1 4 3

In the first sample test case, the optimal p for i = 1 such that k for ai * p is maximised will be [3 1 4 2] right? But none of the given arrays have a prefix 3, So how is the answer 1 and not 0?

I'm extremely sorry if I'm asking dumb questions rn, I'm a bit sleep deprived.

You are getting confused 💀, take a vector of pair store the values of "p" in that vector along with index ({value,index}), sort it and then take the prefix of indexes , what you are doing is you are still finding p

_{qj}💀 💀I must sleep. Urgently.

Good night 🛌

Is E solved by observing numbers of divisors is relatively little(milion or so cause max 20 diferent primes in numbers) and then searching through primes?

Trie method for problem D https://codeforces.com/contest/1792/submission/190408398

What's wrong with my solution for problem C? 190408656

Test Case

1

5

4 1 5 3 2

your output3

expected output2, as you can first select 2 and 4, and in the next select 1 and 5

Thank You

In C what I did for every index I find the fine permutation till that then I will find the left portions towards left and right of the this range 3 1 2 4 5 here fine permutation of index 4 will be 3 4 and then in final permutation 1 2 should come on left of it and 5 in right so greedily we pick 2 and 5 first then 1 and 5 My submission https://codeforces.com/contest/1792/submission/190407907

Google punctuation mate, it'll change your life.

Why so many hacks of B? Is there any edge case?

I think people are simulating it, which is too slow. Most of the hacks are TLEs.

I think it's becaues of the $$$1e18$$$ upper limit of $$$a1,a2,a3,a4$$$, which causes the TLE

You scared the heck out of me when I read 1e18 because I used ints in my program, but thankfully I rechecked the constraints and saw that they were 1e8.

oops, I guess I misread it xd, anyway it will still TLE regardless

Am I the only one who solve problem D with trie and later see that it has an easy solution?

I used a trie too, I found it to be somewhat intuitive. What's the easier way?

maybe bitset?

You are not alone bro.

yeah I firstly thought of trie but then realised that a map would just suffice because of the low constraints.

Can someone give a failing TC for this submission of Problem B?

190391460

Thanks.

Upd: Found the TC.

if a==0 then answer at max can be 1 only.

you can check this https://youtu.be/TOotS4TDzTI

F1 can be cheesed since $$$n$$$ is small and the answer is required modulo a fixed number, You can pre-compute the answers in $$$O(n ^ 3)$$$ and copy the array into your code.

My solution 190420429

Yesterday I was practicing hashing, but I tried to don't think biased and made a solution with custom sorting and binary search in D :)

My solutionI sorted all permutations, first by the order of key 1, then by the order of key 2 and so on. with a binary search I found lower and upper bound of each number in the permutation order, and updating the range of the search to it, until range equals 0

D was really standard...even using simple map for counting will pass for me C>D

I passed E in 15 minutes after the match，it didn't seem like a difficult problem，what a pity

I understood that problem D can be solved by trie, and I was having some difficulty so I looked at some submissions. I see that many people have implemented trie (or something similar) using map. Can anyone explain the logic behind the implementation?

I haven't implemented using trie but the intuition is somewhat similar to using a map. you can check the solution here — https://youtu.be/TOotS4TDzTI

any hints for D

C can also be solved using DP: 190339025

what's the meaning of vector d and statues shifting funcion

$$$d_i$$$ means the length of Longest Continious Subsequence ($$$...,i-2,i-1,i$$$) (End with number $$$i$$$)

Oh this $$$O(n)$$$ is better than std's $$$O(n\log n)$$$ :)

Hi guys if you are still stuck on the problems or want a editorial on it you might wanna check this out: https://youtu.be/TOotS4TDzTI

happy coding!

B seemed quiet simple but at the end I did it out of intuition, eager to see how to properly solve it. I found problem C really interesting too!! dying to see how to solve it, thanks for the round, it was fun!!

Edit: Any hints for C?

Bad F due to oeis.org/A006351.We can search exsamples+2 to get this

how is that related to the problem, ur solution to the problem (F1) doesn't use the formula mentioned in the link, how could someone possibly use it ?

also i dont think someone possibly would search first two samples + 2 in oeis and if so, it displays 316 results found, i dont see any reason calling it "Bad" because of such a reasoning.

Several participants did search the answers for $$$n$$$ between $$$1$$$ and $$$4$$$, found the formula, and had their solutions accepted. Moreover, one could find these values with simple combinatorial considerations.

look at this: a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). — Ilya Gutkovskiy, Aug 28 2020

use this recursive, we can solve F1 and then the recursive is a convolution, while module is 998244353, which means it is easy to brainstorm NTT. And let me tell you why I searched answer+2. the problem said that at least one edge should be painted as red/blue, that means when n>=2, there are two illegal answer(all red or all blue) being removed, while n=1, one illegal answer(no edge) will be removed, so let's search 1,2,8,52(see samples) in oeis.

hope to get green

Good luck!

About E.Divisors

Does this problem have too strict time limit?This is my solution https://codeforces.com/contest/1792/submission/190443658 and it has been hacked for 3 times, I think this problem may need to have more loose time limit like 4 seconods.

There are some better solutions that don't iterate over divisors of every single divisor of m. See this. Also your code is T^2 (T is the number of divisors of m), which is even worse...

thanks，But I think number of divisors of m will not exceeded 10^4.

Number of divisors can go upto 10^6.

thanks so much，i even donot know this before

Nah, there's at most $$$1e5$$$ divisor. Upper Bound for number of divisors

Number 614889782588491410 has 32768 divisors. But anyway ((10^4) ^ 2) * 10 = 1e9, which isn't good (there are 10 testcases)

I will study better solution soon，thanks

The question is, you only need to make a few changes to your code to pass all testdata.

I raised my question here , but still no one answered.

We knew about such solution and it passes. We suspect that either the number of divisors is small (so $$$divs(m)^2$$$ is fine) or divisors are "packed" close, so it's near enough.

Add here that divisors, you actually need to find their own divisors, are in the segment $$$(n, n^2]$$$. So if $$$n$$$ is big, many divisors $$$\le n$$$. If $$$n$$$ is small, many divisors $$$> n^2$$$.

Anyway, we decided that it's okay if some participants gamble and get AC.

P.S.: Even so, you need to write it accurately enough.

I'm not saying that a naive solution needs no skill. I'm saying that, such solution needs obviously less skill than people always expect for E.

If you attribute my not_pass to my cowardice or bad strategy, that's right.

In addition, the naive solution is not only "near enough", but far more.

I found all factors during the contest. Now I added two for-loops. Guess what, it costs 156 ms only.

156 ms

If you say that this solution requires some advanced mathematical knowledge, which you had already used to prove the time complexity, so this solution can be an alternative. I would blame me for my lack of knowledge.

But you said otherwise. Emm... whatever, it was history.

thanks，i will write it more detailed soon

OK，i will try it soon，thanks so much

There will be only 6 hrs before next round begin. Maybe the rating update of the next round will be earlier than this round.

I am sensing Problem B is a broken copied problem. I don't know source but its just my hunch

.

wait.

System Testing is running.

After system testing everything will be fine.

Too slow system testing.

When will the Editorial be published ?

when will ratings update?

Why am I always

This is to address the concerned authorities about my submission 190353992, which got skipped because the system considered it similar to another submission by BoosterImpulse , submission id 190386013.

I think the major reason why these 2 codes appear similar, is because of the use of a template of MOD INT (MINT), which I have used many times in my code and is clearly written before the contest and you can clearly see my code is completely different from the other person's code, my code is a normal implementation of two pointers. You can also check the timings of the submission and other persons' submissions. Please look into this matter as soon as possible cause I will become an expert if my solutions are been judged fairly. awoo BledDest Neon MikeMirzayanov adedalic

Yes I too am pretty confused as to why the solutions are plagiarised.

.

Have you ever read the rules?

Rating updated :D

When will the editorial be published?

System said that I cheated but I did not.

wsyear/190368291, LXH-cat/190370101 we used a similar template of modint and checked oeis to find a formula:

`a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).`

With the same formula, our codes are similar.

The code that I used modint before this contest.

awoo MikeMirzayanov Neon antontrygubO_o

When the editorial will be updated?

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Hi my submission 190325251 is said to coincide with submission 190323813. I believe the logic to this problem is very straight forward and the solve() template we both used is very standard. Any of my previous submission uses a similar template + style and I believe this is just a mistake from the automated plagiarism checking system. Please update I dont want to be flagged for cheating :(

IMO the problems were great. I enjoyed thinking about and solving them. Also I got caught on the special case for B (a1 == 0) haha.

Through this comment, I want to address the cheating charges levied on me and Numinous , for having a coinciding solution to problem C in Educational Round 142. The submissions are 190386013 and 190353992. The reason for getting plagiarised was having a similar template, going through solve function for both speaks out the difference clearly. I hereby in my humble opinion ask MikeMirzayanov Neon BledDest adedalic vovuh awoo to provide us justice and the ratings we deserve . Thank You for your time and effort .