Hi Codeforces!

I'm glad to invite you to Codeforces Round #549 (Div. 1) and Codeforces Round #549 (Div. 2), which will be held on Mar/30/2019 20:10 (Moscow time). The round will be rated for both divisions.

Problems were prepared by me, Vladimir vekarpov Karpov, Daniil qoo2p5 Nikolenko, Askhat super_azbuka Sakhabiev and Mike MikeMirzayanov Mirzayanov.

Thanks to KAN and arsijo for helping us, and MikeMirzayanov for the great Codeforces and Polygon platforms.

**UPD:** You will be given 6 problems in the second division, 5 problems in first division and 2 hours to solve them.

Good luck and Have fun!

The scoring distribution will be announced later.

**UPD1:** Top 12 participants of div1 round, who are ICPC world finalists, will get branded Codeforces hats. Further details are here.

**UPD2:** The score distribution is 500-1000-1000-1500-2000-2500 for the second division and 500-1000-1500-2000-2500 for the first division.

List of the winners of the contest:

**Div1**

**Div2**

**UPD3:** Sorry for the delay, the editorial is available here

I hope the problem statements are short as the announcement

no coments

comments* :P

Typical "friendly" person in cf

it is good

If the problem with the 5kk depth of recursion will be again, please write in advance, we should not suffer with runtime errors, like adamant.

Wishing everyone a great contest after almost a week!

Just wondering, how many weeks do you waited for proposal queue to organize this round in Codeforces?

We waited around 6 weeks before our problems were first reviewed, but after that we haven't waited much for everything else

Do they announced or told that you are going to wait even more after you waited for 2 weeks?

What app/website you're using? Good day to you.

clist.by

This time is not friendly to Chinese people.>_<

The last div1 round was at a time that was much friendlier to Chinese, but not to me. Fair turnaround, I guess.

What are you talking about, you can see problem statements 12 hours ahead of us.

can you make it at 20:20 every contest i can't participate because the bad time

OK they delayed it 5 minutes for you

and the electricity delayed 30 minutes and **** me

10:00 on a Saturday morning! California thanks the round setters!

Div2 round is rated for non-rated user? (for me)

Yes. It is rated for everyone whose rating is less than 1900 and also if the user is unrated, it is rated for them too.

Okay, thanks

Sounds good...hope the problem statement will be also great like this announcement.

Yeay! My first Div 1!

Round delayed by 5 min ":(

ICPC Finalists in Div. 1 round, standings

I'm not an ICPC finalist, but I will happily receive a hat if you want xD

I gave up the div1 contest because the description of problem A was too difficult to understand, and even did not give the picture.

So?

Lack of understanding? literal meaning

I get the error ~~~~~ You have submitted exactly the same code before ~~~~~ even though i haven't submitted anything yet. Anyone knows why?

Could someone tell me that, if in a round all the participators' rating is higher than me, and I get the last place in the round(the lowest point), will I lose my rating?

I found that I can't solve the Div1B and div1A is a little difficult for me. But only Master and International Master Solve that in 15min.

QAQ...

Can't submit code anymore. Can't even send feedback in the contest page. I keep on getting the error "You have submitted the same code before" and I don't see any submissions in my submission page.

Cheating notice: rusau and King_01 submissions on problem B are same

I don't even know that guy dude! ... neither a single connection between us

Check this out!!

Hahahah nice!

GFG is saviour :)

They both know GFG ;)

I was stuck on pretest 4 of div. 1 B. any help?

My code that failed pretest 4 broke with this:

3 4 1

1 2 3

1 2 2 3

1 4

Hmm, that didn't break mine. Guess I'll just wait for sys tests to finish.

Div2/B is available in geeksforgeeks. https://www.geeksforgeeks.org/find-the-number-in-a-range-having-maximum-product-of-the-digits/

Div2B is a copy of this: https://www.geeksforgeeks.org/find-the-number-in-a-range-having-maximum-product-of-the-digits/

Sorry, my bad. I offered the problem, and it coincides.

I think the contest should get unrated

I think that problem should be removed from scoring distrubution. As its unfair to other candidates who tried on their on.

Before creating the problem, one should search google.

If not google, one should search on codeforces. Same problem in codeforces https://codeforces.com/gym/100886/problem/G

SURPRISINGLY, it is a Grand Prix of Saratov :)

I have seen many people have copied the code exactly from the above-mentioned website. Not fair for all those who tried on their own.

You can also have a prewritten code that make an integer segment decomposition over base-k segment tree. The problem is too standard for talks like "omg this is googlable".

Div2 B is just B. Does anybody know a solution without dp?

.

My idea: I found product of digits of Some integers from 1 to n that they have the greatest digits(kinda integers have more 9), in this way:

if n=d

_{3}d_{2}d_{1}d_{0}for every digits greater than zero in n except d_{0}like d_{1}i subtracted one from d_{1}and digits on the right of the d_{1}turn to 9 which product of them are d_{3}*d_{2}*(d_{1}-1)*9like if n=1099 they are 1099,1089,099 or if n=100000 they are 100000,99999

i didn't know how to explain better https://codeforces.com/contest/1143/submission/52059415

I named this solution as the solution with dp))

Just precalc)

it was calculated with the help of a computer that for any number from interval [m[i].first, m[i + 1].first) the answer is m[i].second?

Yes. Precalc took 2 minutes.

This solution is kind of dp, but looks more like brute force.

One can notice that the number of different possible products is not really big. For example, I considered that for a d-digit number there should be around $$$9 ^ d / d!$$$ distinct products. Then, I just did a recursion memorizing the products already computed.

Solution

Any idea how to solve div.2 E,F ?

In F, when you convert all points in the input $$$(x, y)$$$ to $$$(x, y - x^2)$$$, then the problem reduces to finding the number of lines that pass through atleast a pair of points where no points are strictly above the line, instead of parabola (since, the new equation becomes $$$y^l = bx + c$$$ from $$$y - x^2 = bx + c$$$). This is just the size of the upper convex hull of the transformed points. (Need to take care of the case with lines of same x coordinates, i.e vertical lines)

wauw. this is beatiful

What was the intended solution for Div2E/Div1B? My solution seemed ridiculously complicated, and I imagine there was a simpler way to solve it.

You want to pick some position in the range [l, r] and $$$N-1$$$ times repeat: if you're currently at $$$a_j = p_i$$$, then jump to the next $$$a_k = p_{(i+1)\%N}$$$ (for the smallest possible $$$k \gt j$$$); at the end, you shouldn't be at $$$j > r$$$. The rest is just simulating this efficiently with precomputation and RMQ.

It seems like this should be $$$O(n)$$$ per query, did you use binary lifting to simulate it efficiently or is there another way to do it that I'm missing?

Yeah, binary lifting is probably what it's called.

This will probably work

For each position find r[i] — first position of next value in permutation(p[2] for p[1], p[1] for p[n] and so on). Now for each position calculate R[i] — min pos where subsequence exists using r and binary jumps, and answer for each query is just checking if minimum of R on segment <= r.

My solution was to first find the largest $$$l$$$, for every $$$i$$$, such that there is a subsequence in $$$[l, i]$$$, which is a cyclic shift of permutation. For finding this $$$l$$$, what we can do is add an edge from each ind $$$i$$$ to the nearest ind $$$j$$$ in left, such that $$$a_j$$$ is the left element of $$$a_i$$$ in the permutation. Now, we can easily find $$$l$$$ for each $$$i$$$ using the approach of binary lifting. Once, we find $$$l$$$ for each $$$i$$$, we maintain a segment tree, which gives a maximum $$$l$$$ for a range. So, for query $$$[ql, qr]$$$, if the maximum $$$l$$$ in the range is greater than or equal to $$$ql$$$, then subsequence exists.

Hmm, I did the same thing without the segment tree (I think we can delete certain $$$[l, i]$$$ intervals and store the rest in a set, and use a lower_bound call, but I could be wrong), but I couldn't really see a nice way to do the binary lifting and ended up having to import my LCA code lol

Me in div1A: number of steps = lcm(L, NK) / L = (L / gcd(L, NK) * NK) / L. Can you spot the fail here?

Fortunately, I fixed it, resubmitted and hoped I'd get some points back by hacking, since pretests don't handle it. >Mfw everyone else used NK/gcd

UPD: And now it turns out I actually could have hacked people, just not on this...

Why is NK / gcd wrong?

It's right, that's the problem. I couldn't hack anyone because of that.

NK/gcd is right, but what he wrote can overflow

How can I solve problem D?.. T^T. I just read and read D for 1 hour... OMG..

same T_T

It was also difficult to understand the problem...

Any idea of what test case 4 for div2 E(div1 B) is?

What is was testcase 14 in problem D?

It was (i assume, since this is how i fixed it) n=100000 k=100000 so that n*k overflows if you use int for intermediate results.

Is it only me who didn't get that we can go to different vertices by different colors in E?

I am too stupid to look into samples, so it took me 5 minutes and a question to find it out. (I thought that there has to be a color and a vertice such that...)

It definitely wasn't clear to me as well and lost some time because of this.

How to solve Div2 C?

take every node that have zero respect child and insert it in array and then sort array and print , get pass in test case wish will not failed on main test

Can you please prove if this would give the correct result?

If we have a node that doesn't respect parent and have zero respect child,it should be removed, in case of tie, remove the one with smaller number. That gives indication that they should be deleted in sorted order, we now need to prove 2 things

1) If we deleted a node, is there another node in the sorted list won't be delete-able?

2) If we deleted a node, is there another node will be added to the list?

let's prove the first, the only case that a node won't be delete-able, if a respecting node will be attached to it, that won't happen, because a respecting node will go up iff its parent got deleted, and its parent can't be deleted because it has respectful child (contradiction).

let's prove the second, to make a node delete-able, you have to make all it's children disrespectful, and you can't delete a respectful node to create space for disrespectful child.

There is a simpler solution. For every vertex u from 1 to N if u has 0 respect to its ancestors mark u and its parent. Then just iterate for all vertices from 1 to N and add vertex to your answer array if it's marked.

I lost interest while reading DIV2D. Can someone say the technique to patiently read such problems?

What's the problem with this statement? It is relatively short.

Maybe too many variables to remember

I think "solve more problems" is the right approach here I think, once again. The more you struggle through such statements, the more accustomed your brain becomes to processing such information.

Also taking notes or writing a short summary of the statement by yourself has helped me in the past. It also helps you to get closer to solving the problem because it makes you rephrase the question, which may in turn make it simpler in the end.

How do you come up with making summary/notes of the problem statement, can you please post an example for div2.D. I end up writing the whole sentences xd.

I did not really feel the need to make a summary here.

Just to satisfy your curiosity. Please do not take this as an example on "how to take notes". Also, this was a relatively simple problem, too. In general, there's no recipe of what you need to write during problem-solving. You should write down what you feel you need to write down.

How to solve Div1.D? Thanks in advance.

Let $$$b$$$ be an integer between $$$0$$$ and $$$9$$$ inclusive. Then the position $$$\pmod{11}$$$ of $$$10a+b$$$ in the sequence is uniquely determined by $$$b$$$ and the position $$$\pmod{11}$$$ of $$$a$$$ in the sequence.

Consider an inadequate number x with $$$k+1$$$ digits, or in other words $$$x \in [10^k, 10^{k+1})$$$. It turns out that following information is sufficient to know whether $$$10x+l$$$ is inadequate:

1) d1: Number of inadequte numbers $$$<10^k$$$

2) d2: Number of inadequate numbers $$$<10^{k+1}$$$

3) c: Index of x in a list of inadequate numbers mod 11

Moreover this information is sufficient to recalculate this information as well for k:=k+1 and x:=10x+l in case 10x+l is inadequate.

Everything heavily relies on fact that $$$11 | 0+1+...+10$$$.

This is already sufficient to solve this problem in $$$O(n^2)$$$ since in constant time you can determine whether number after appending some digit is inadequate.

Moreover it turns out that number of inadequte numbers < 10^k falls into a cycle 9, 10, 9, 10, ... and if you look at formula keeping information about c then knowing that (d1, d2) is either (9, 10) or (10, 9) you can deduce that it actually doesn't matter what out of these two pairs (d1, d2) is, new value of c just becomes (l+c(c-1)/2+10)%11. This means that if you fixed some beginning position in our string and processed some digits, we need to keep only one number (between 0 and 10) to determine whether after appending new digits our number stays inadequate. This allows you to write O(n*11) dp.

I think these kinds of problems are pretty "cancer".

Duh, not a fan of D, it was kinda hard to digest what am I asked about and the problem itself is not very interesting as well. At least the resulting code was very clean.

Can anybody look at my problem C code and tell me where am I going wrong

https://codeforces.com/contest/1143/submission/52037703

You don't have to remove the root. Since it doesn't have a parent it cannot disrespect its ancestors.

C looked so much like problems where magically you must calculate the convex hull. I gave up after 5 minutes of that approach. Turns out the solution is the convex hull...

But this time you are looking at the solution from the beginning, you just need to see it. Rewrite $$$y=x^{2}+bx+c$$$ as $$$y-x^{2}=bx+c$$$ and you are done.

Funny problem, thanks to authors. Actually, I liked all of todays problems, more or less.

FALLLLINNG DOWN!!!!

Does anybody have an idea for n =10^5 nodes recursion is giving runtime error in python even after using setrecursionlimit()

My submission

Even if you write 10**6 as a recursion limit,Python won’t increase it more,than 10000-20000(I don’remember the exact num)

previously I used so many times dfs for 10^5 nides in python

Waiting for rating!~

RIP to those submissions which initialized minimum as 1e9 in DIV2 D. TC #33 .

https://codeforces.com/contest/1143/submission/52055235 I'm getting WA in pretest 8. Why is it not 888999999? please help!

because it can be 799999999, which gives a larger product.

Can you please explain your approach to problem b?

maybe 799999999?

Because it's 799999999

I will never forget this contest because of the problem D! It's a sad story about inf!!!!!!

Quick instruction for those wondering:

Congratulations on making it to the Red level! I've noticed you've been an active member since quite a time. You deserved it.

You were pretty adamant in doing contests.

Am I the only one who read "subsequence" as "substring" in Div1B(Div2E)?

It was so sad to find out such mistake after struggling with my Hash code, which is able to solve "substring" one. QAQ

You're not :-)

Can someone confirm that Div2C test 10 is 100000 nodes with i being the only child of i+1 (and node 100000 is the root)?

Thank you grphil and others for setting nice problems.

This contest was quite enjoyable for me ! At last I have succeeded to cross the 1600 rating barrier !

2nd question of div2 was easily googlable!!

How to solve div2 B? thanks in advance.

Precalc or dp. Precalc: link

Lemma.

If m is optimal for n, then there exists such position p that:

in positions 0..p-1 digits of n and m are equal,

in position p digit of m is less by one,

in next positions m has digit '9'.

52044460

that moment when I noticed I switch the positive and negative sign for Div 1 A and debugged for 2 hrs... and stupid mistake for Q2. I can kill myself

please upload the editorial of this contest...

Can anyone explain why my submission for Div2E/Div1B is getting TLE?

$$$\text{next}[i]$$$ is the closest right index where next permutation number occurring, $$$\text{next}_{n-1\text{ th}}[i]$$$ is equivalent to $$$\text{next}[\text{next}[... (n-1 \text{ times nested}) ..\text{next}[i]]]]..]]$$$. I used read-only segment tree to determine if the given query is possible or not.

I think time complexity of calculating $$$\text{next}$$$ (in

`main`

) is $$$O((n+m)\text{ log}(n+m))$$$, $$$\text{next}_{n-1\text{ th}}$$$ (in`construct_nextn`

) is $$$O(n+m)$$$, and the time complexity of each query is $$$O( \text{log}(m))$$$.But I can see it barely passes some large test cases, while other users pass in less than quarter of my submission's used time..

Can anyone explain? Thank you.

Your code uses quadratic time in a case like this:

Where the sequence first has n copies of 1, and then the integers from 1 to n.

The queries can be whatever. What happens is that while

`construct_nextn(i)`

is not called for i that are already checked, none of the n ones ever get marked as checked before being handled. So for each of the ones, your code goes through the entire n-length loop in`construct_nextn(i)`

. Therefore the code does O(n^2) work in this instance.Thanks for detailed explanation. I got accepted using different approach for $$$\text{next}_{n-1\text{th}}$$$.

What's the approach for Div2D(Div1A) please ?

Let's denote $$$S$$$ as starting point, $$$L$$$ as moving length, $$$R_{i}$$$ as $$$i+1$$$ th restaurant met. $$$R_{0}$$$ is the closest restaurant to point $$$S$$$, and $$$R_{i}$$$ is the closest restaurant to point $$$S+L$$$. You can check 4 scenarios for $$$i$$$ in $$$[0, n]$$$.

Scenario 1: $$$S \rightarrow R_{0} \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow R_{i} \rightarrow S+L$$$ : $$$a + b + i*k = l$$$

Scenario 2: $$$R_{0} \rightarrow S \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow R_{i} \rightarrow S+L$$$ : $$$a + l = b + i*k$$$

Scenario 3: $$$S \rightarrow R_{0} \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow S+L \rightarrow R_{i}$$$ : $$$l + b = a + i*k$$$

Scenario 4: $$$R_{0} \rightarrow S \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow S+L \rightarrow R_{i}$$$ : $$$a + l + b = i*k$$$

In each scenario, calculate $$$l$$$. Then the number of stops for that case is $$$\text{gcd}(l, nk)$$$. Of course you should not calculate when $$$l \le 0$$$.

seems like problemsetters are jojo fans)

Can someone help me understand why solution for Div2 C was getting MLE on TC 10 (skewed tree)

https://codeforces.com/contest/1143/submission/52052934

Assume you didnt't call vector.clear() after moving children to the parent of current node, space complexity will be O(n^2) which will get MLE.

In fact, vector.clear() makes its size = 0, it doesn't deallocate the memory reserved by it, so it's the same memory as if you didn't call clear :)

When the solutions will be availible?

When will the tutorial be published?DIV1-A / DIV2-D. I know ans is $$$ n * k / gcd(n * k, k * x + c) $$$, but cannot figure out why $$$ x < n $$$. Anybody can help? Thanks in advance.

At least in my solution (which es the same formula), x is the amount of restaurants you travel through.

That's because if $$$x$$$ is grater than $$$n$$$, then in each jump will be at least $$$x \cdot k > n \cdot k$$$, which means that it is more then circle length. And so the place where you will get after the jump is the same as if the jump was $$$k \cdot (x - n) + c$$$.

Wow, I got it, thx a lot.