Hello Codeforces!

On Dec/27/2019 17:40 (Moscow time) Educational Codeforces Round 79 (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 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 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:

*Hi Codeforces!*

*Last spots available for Mike Mirzayanov's course Advanced Algorithms and Data Structures, which will take place in Barcelona, from the 6th to 24th of January, 2020.*

*The course will consist of three weeks of training, 5 training days each week. The program includes daily lectures and practical exercises. It will be quite educational, insightful and entertaining!*

*Remember, there’s a special price of 1,000 EUR* for all Codeforces users.*

** The cost does not include travel or accommodation.*

**If you’re interested, send us a message at hello@harbour.space and we will guide you through the next steps.**

**UPD:** Editorial is out

Hope to become specialist in this round

Hope to become pupil in this round

Hope to remain master in this round.

Hope to do some problem solving

No

Hope to wake up and actually do this round

HOPE I DONT COMPLETELY LOSE MY RATING TO ZERO.

hope to have fun this round !

rating is just a number !

You have no need to wait . Just use magic to become specialist before this round .

Could you show me the way you become Legendary when your rating is 1536?

He got gift from santa just like me

Why I didn't receive any gifts =))

Merry Christmas!

Merry Christmas!!

BUT HOW YOU CAN AS YOU ARE A LEGENDARY GRANDMASTER BY THE WAY HOW YOU CHANGED YOUR POST FROM PUPIL TO LEGENDARY GRANDMASTER.

congrats on becoming LGM

Wow, that's amazing!

No

Just Misusing

Santa'sGiftDiv3 registration has started, we could see some blue, or even purple participating officially and rated in div3 contest! UPD:Probably grandmasters in div3 now! Santa is real!

Pls find a way to make it available to anyone across the world. In today's day and age if this is not possible it's only because probably the creator of the program do not wish to share their knowledge to everyone even if they are willing to pay. Hope that is not the case and the program creators will try to find a way to make this program available online too:)

wtf?

yeah lol what?

.

CODEFORCES SANTA BRINGING GIFTS IN THE END OF YEAR.

Is the weird color thing going on the Christmas gift from CF? Yup

after this contest in my messages merry christmas you become newbie :D

Anyone else experiencing the slowness of the website at the moment? Its just taking longer than usual

5 minutes delayed :(

Delayed

delayed :/

why there is no sample test case explanation in c problem

in problem, c is it necessary to reorder all the k elements or he can choose not to place some of the elements again.

Your questions are not related much. Santa cannot choose to not place elements, but it is not necessary for Santa to reorder any elements.

ok

my bad was using 32-bit int all the time so was looking in all other possible directions.

When Speedforces meets slow website ...

Thanks to the authors for educational, I will be glad if all my decisions fall P.S. you can have as many tasks with t requests as possible, I love them so much

1) Problems with test cases

2) Awful pretests

3) Long queue

Choose one.

4

Participants.

I really did that, cooked dinner after solving D.

Only because of that, I have dinner.

Now I know why I shouldn't participate in Educational Rounds

How to solve F?

Looks like minimum cost max flow with binary search but is it normal to have these in Div 2 contest?

Edit: Reading above seems like I was trolling. But actually I had sketched something of that sort. Haha. Anyway, people have solved with a simple dp with binary search.

Well, it uses the trick from Aliens (from IOI 2016). You can read about it here

how can pisquare be a legendary grandmaster? he has a highest rating of 1404

In this contest i got confused by a legendary gm just after my ranking and thus found this user

http://codeforces.com/profile/pisquare

you can change color of your handle(temperory) and u can change ur handle name only once if u want to(permanent), codeforces does it for every christmas

thanks for the info

Now i have become legendary gm too :p

chill bro :>>

PROBLEM D: How is the answer of first test case 7/8? (without modulo) As per me — TOTAL POSSIBLE ARRANGEMENTS OF DECISION ARE: (2 1 1) (2 1 2) (1 1 1) (1 1 2) (1 2 1) (1 2 2) ie: 6 total possibilites, out of which 5 are valid, so the answer should be 5/6

i had the same doubt

Due to the process with which the decision is made, not all of those are equally likely. The first two happen with probability $$$\frac{1}{4}$$$, the last four with probability $$$\frac{1}{8}$$$ each.

1 1 1 and 1 1 2 and 1 2 1 and 1 2 2 have all 1/8 chance

2 1 1 and 2 1 2 have all 1/4 chance

X, Z all chosen independently but Y is not (depends on X)

P(X = 1) = P(X = 2) = 1 / 2

So P(X = 1 and Y = 1) = 1 / 2, P(X = 2 and Y = 1) = 1 / 2

Same doubt. Anyone can explain why 7/8?

Either you pick item 1 or item 2. Probability of picking item 1 is 1/2*1 (you pick student 2 ) + 1/2*1/2 (or you pick student one in the first step). Therefore probability of picking item 1 is 3/4. Probability of picking item 2 is therefore 1/4 (sigma has to be 1). Now if you pick item 1, probability of making a valid decision is 1, but if you pick item 2, probability of making valid decision is 1/2. Therefore P(pick item 1)*P(valid | item 1) + P(pick item 2)*P(valid | item 2) = 3/4 + 1/8 = 7/8

Because not all of them are equally probable. (1 1 1) has 1/2*1*1/2 chance of being chosen while (2 2 2) has 1/2*1/2*1/2.

That's not true Answer is 7/8

Model of calculations:

1) possibility to choose a person = 1 / n 2) possibility to choose a gift from a list = 1 / size_of_list; 3) possibility to choose a person who would like this gift = number of good kids / n; Lets sum everything i = 1, j = 1, 1/2 * 1/2 * 1/2 = 1/8 i = 1, j = 2, 1/2 * 1/2 * 1 = 1/4 i = 2, j = 1, 1/2 * 1 * 1 = 1/2 ans = 1/2 + 1/4 + 1/8 = 7/8

This is because all tuples are not equiprobable. Let you have 10 balls then probability of selecting each ball is 1/10. Now divide the ball into two groups of 8 and 2. Now first select a group then select a ball. Then half of the probability will be distributed among 1st group and half will be distributed among second group. If a ball is in group containing 8 then probability of selection 1/16 and for other group it's 1/4. This is how 5/6 become 7/8 here.

Well-balanced round lol

How to solve E?

I think it can be solved using the observation that any good permutation is a one where $$$p_1=i$$$, and values of $$$p_j$$$ ($$$1\leq j\leq i$$$) are $$$\leq i$$$, $$$p_{i+1}=k$$$, and values of $$$p_m$$$ ($$$i+1\leq m\leq k$$$) are $$$\leq k$$$, and so on. Then we can use some greedy and dp to find the required permutation.

I finish impl just now.. find kth-lexi painful..

note good form is |i... | j...| k...|..., each region is cycle. with max be first.

first define f[n], total-derangement, i.e. p[i]!=i, but they're exactly one cycle.

r.relation $$$f[n] = (n-1)f[n-1] = (n-1)!$$$. which is circle-perm.

define dp[n][j], ways of good-perm. s.t. first j elements in a cycle with j is first. i.e. j,..., where ... part is f[j-1].

define g[n]: ways of good-perm of [n], i.e. $$$g[n]=\sum_{j=1}^n dp[n][j]$$$.

r.relation $$$dp[n][j] = f[j-1] * g[n-j]$$$.

for kth-lexi. first iter j, find satisfied dp[n][j]. then problem separate to j part, n-j part. where n-j part is original problem.

for j part, first of all, let $$$p[1]=j$$$, then for remain position, pick smallest x, don't violate total-derangement, and just satisfied lexi.

I have one doubt, how to use xth lexicographical smallest perm in creating cycle for a particular group. Will be very helpful, if someone can help in this https://codeforces.com/contest/1279/submission/67755772

Since no one is asking, how to solve E and F?

I have a small doubt. Will be very happy if someone can answer this. Is the cf rating predictor working fine or is there a possiblity of some discrepancy in it because of cf magic?

Magic changes the color, not the rating which predictor uses.

Thanks :)

its working fine

Thanks :)

What was the test case 5 for problem D What could be done to prevent long value overflow in problem D

You are trying to maintain the probability value of each event as fraction. Then you are adding all those values to compute final answer, overflowing can easily happen when you multiply numerators of fractions to bring them in

common denominator form.(While adding fractions)Instead of doing so, immediately convert the fraction into "numerator.(denominator)^-1" (inverse modulo of denominator) form.

and now the add the fractions in their "converted form", using appropriate modular arithmetic.

The gap between D and E is SOOOOOOOOOOOO HUGE

Seems F is easier than E...

Can someone help me understand why the answer to the first test case in Problem $$$D$$$ is $$$7/8$$$ ?

According to me, there are $$$6$$$ possibilities totally.

Totally, there are $$$4 + 2 = 6$$$ choices, out of which only $$$(1, 2, 2)$$$ is invalid.

Please help me.

1 1 1 and 1 1 2 and 1 2 1 and 1 2 2 have all 1/8 chance

2 1 1 and 2 1 2 have all 1/4 chance

X, Z all chosen independently but Y is not (depends on X)

P(X = 1) = P(X = 2) = 1 / 2

So P(X = 1 and Y = 1) = 1 / 2, P(X = 2 and Y = 1) = 1 / 2

Look, the probability that we choose the three $$$(2, 1, 2)$$$ is not equal to the probability that we choose the three $$$(1, 1, 2)$$$.

How the answer is counted:

notcorrect;We just summarize all the correct options and get the answer. It is equal to $$$\frac{7}{8}$$$.

Why was the round sooooooooo unbalanced? Like if you solved tasks A-D, the contest is ended for you. And if you solved tasks A-D not so effectively, then you definitely lose your rating. Hope to see more balanced contests on Educational Codeforces Rounds. :)

Happy New Year and Merry Christmas, by the way!

I definitely agree with that

Well, it seems that it's my fault. I greatly overestimated the difficulty of D — it is very simple in coding, but I expected that a lot of people would make wrong assumptions such that all outcomes are equiprobable, so the concept of probability would make this problem much more difficult than simply coding it. It turns out that I was wrong.

How to solve F?

Alien trick (or Lambda optimization, wqs binary search) is the keyword.

As others have mentioned, the solution relies on a technique known as Aliens' Trick. This is essentially a DP optimization for problems where we want to perform $$$K$$$ operations, each with some "value" (in this case, the value of an operation would be the number of characters we convert from lowercase to uppercase, assuming we're trying to minimize the number of lowercase letters, or the other way around). There's a natural $$$O(NK)$$$ solution, of course, but Aliens' Trick allows us to optimize this to $$$O(N \log X)$$$, where $$$X$$$ is a value related to the precision of the solution.

The trick is fairly simple: essentially, rather than trying to compute the best we can do with $$$K$$$ operations, we assign some "cost" to each operation and attempt to maximize the number of uppercase letters in the final string minus the cost times the number of operations, while allowing ourselves to use any number of operations. In other words, each operation decreases our score by a certain cost. In this problem, we can easily determine the best solution given a fixed cost in $$$O(N)$$$ using some fairly simple DP. The trick, then, is that we can binary search for the greatest possible cost that will make us use at most $$$K$$$ operations. Then, we can reconstruct the answer using that cost, solving the problem.

Thus, for this problem, we split into two cases--in the first case, we try to convert as many letters as possible to uppercase, and in the second, we try to convert the letters to lowercase. The two cases can be handled identically. Within each case, we binary search for the cost of setting a substring of length $$$L$$$ to uppercase/lowercase, keeping track of how many operations we use for each cost (using the aforementioned $$$O(N)$$$ DP). Then, we can find the cost that ensures that we use $$$K$$$ operations: if a certain cost encourages us to use too many operations, we should try a higher cost, and vise versa. This lets us reconstruct the answer in either case, and we can simply print the better of the two results.

Thank you very much, I understand

For me, 'F' reduce to this problem

"Given n segments, select k from them such that they cover maximum points"

Is this some classical problem?

May be i am in completely wrong direction.

This reduction has removed some (potentially useful) restrictions on the input. Notice that all n of the segments have the same length, so the value of two adjacent segments differs by 0, 1, or -1 only. I don't know that you have to abuse this restriction to solve the problem, but it exists and isn't in your simplification.

It's high time we explained why the answer for test 1 in D is $$$\frac{7}{8}$$$.

It seems that possible decisions are $$$(1, 1, 1)$$$, $$$(1, 1, 2)$$$, $$$(1, 2, 1)$$$, $$$(1, 2, 2)$$$, $$$(2, 1, 1)$$$ and $$$(2, 1, 2)$$$. Among them only $$$(1, 2, 2)$$$ is invalid. So the answer should be $$$\frac{5}{6}$$$, right?

Nope.

These decisions are not equiprobable. The probabilities of choosing $$$x = 1$$$ and $$$x = 2$$$ are both $$$\frac{1}{2}$$$. But if we choose $$$x = 1$$$, there are two options for $$$y$$$: $$$y = 1$$$ and $$$y = 2$$$; and if we choose $$$x = 2$$$, there is only one option for $$$y$$$: $$$y = 1$$$.So, the outcomes $$$(2, 1, 1)$$$ and $$$(2, 1, 2)$$$ are twice more probable than all of the other outcomes. That's why the probability of $$$(1, 2, 2)$$$ is just $$$\frac{1}{8}$$$.Thanks for explaining. I just posted a comment asking why. :)

**Happy new year for all !!! & I'm very happy for this round !!! **

How to solve A and C? :'(

How to solve F?

problem B confused me a Lot solved it in 22 attempt!

Test case 3 of C?

I did with maintaining a visited array concept. You can check my submission. My code — https://codeforces.com/contest/1279/submission/67746000

I tried my code on various cases but it failed. Any help?

Thank you :)

Answer should be 10. Your code outputs 6. Once you take out the 1, you still need to take out the 4 and 5 again before you take out the 3.

Hello, dear pikmike, it seems to me that you would be good at doing olympiads for mathematicians!

I see no really mathy problem.

Sorry, I didn’t read the problems, I thought they were as usual on mathematics

Dont understand why my C is wrong? Seems such an easy problem -> https://codeforces.com/contest/1279/submission/67724577

Probably I am not understanding the problem correctly, can anyone take a look as the wait is going to be too long!!

Okay, I figured out that this is because of a peculiar reason in Java that I encountered first time, and maybe will helpful to others, so putting it here. I had Integer (not ints) values in the array, and I was using the comparison !=. This works fine for numbers in the range between -128 to 127 because Java is handling it separately (see this). However for numbers outside of that range, it treats it differently. When I used the equals method instead, the same code passed.

Kind of annoying, for 1.5 hours, I was trying to see what is wrong in my approach, including things like misinterpreting the problem etc. For example, I had implemented another approach which was giving even lesser results and so on..

Approach for A ?

Proof for A?

If a > b + c + 1 or b > a + c + 1 or c > a + b + 1 then its impossible. In the other case, it's always possible to construct it like 1 2 3 1 2 3 .. 1 2 3 2 3 2 3 2 3 ( 1 is the biggest 2 is the second and 3 is min) and if there is 1 left we can place it between 2 and 3 in the triples.

If the max count among the counts of b, r, and g is $$$mx$$$, the 2 minimums are $$$mn_1$$$ and $$$mn_2$$$, then we obviously can't make a valid configuration if $$$mn_1+mn_2<mx-1$$$ (we will definitely have 2 of the max color adjacent to each other). But what is the proof that we can always find a valid configuration if $$$mn_1+mn_2>mx-1$$$? Consider the case when $$$mn_1=mn_2=mx$$$, assuming without loss of generality that the max color is r, you can obtain a valid configuration of the form rgbrgb...rgb, and for every $$$mn_1$$$ and $$$mn_2$$$ values where $$$mx-1<mn_1+mn_2<2*mx$$$ you can always remove an instance of b or g without making two r's be adjacent to each other.

how to come up with such ideas during contest? Anything other than practice?

query contest

Can someone help me figure out why am I getting Runtime Error in Problem D Test case 3. Here is my submission 67746943

UPD: I am not able to understand what the diagnostics are saying.

Its because of the following declaration

Here, you declare an array of 10

^{5}whereas a_{i,j}can be 10^{6}as given in the constraintsOh it was a silly mistake thanks!

E seems copy of 553B - Кёя и перестановка?

E was invented after Ne0n25 misunderstood the statement of that problem and solved a wrong version.

I know D was simple for many including myself, but while solving it, did anyone have analogies with neural networks like me ?

Did someone fail in D at test case 37?

Probably overflow

Yup same case. https://codeforces.com/contest/1279/submission/67745426 Still dunno what's actually wrong.

[Resolved]

How did you correct it?

Instead of taking modInverse(n*n), I did modInverse(n)*modInverse(n).

Damn man :(

Why doing long long int got accepted (https://codeforces.com/contest/1279/submission/67744302) in problem C whereas int was failing (https://codeforces.com/contest/1279/submission/67739629) on test case 3 ?

This can essentially go $$$O(n^2)$$$ for cases like sorted queries. And overflow $$$int$$$ with ~$$$10^{10}$$$

thanks! you are right. Even the output in third case goes beyond int .I should have thought about it before asking.

Why so many downvotes? comment section here is weird

I think,

If a comment is lucky and the first few votes it gets are positive, then others also see that and after that the comment mostly gathers positive votes....

If unlucky, the comment gets a few downvotes, and in a snowball effect fashion, others also downvote it, just because it is already downvoted...

I think maybe people want to increase the absolute value of whatever number there is already there on a comment...

Legendary steeped CF =)) everywhere. I wish try once :>

I thought the items in problem D are numbered from 1 to n after reading the sample data, and this cost me 1h30m to debug my code... Now I know those are not numbers but items' names. I think I may not be the only one who made this kind of mistake.

I hate problems like D _ I now the solution,but can't implement it,because there is MOD,can anyone help me to learn how to do problems with MOD? I am having issues with it so long...

Just treat fractions like (a/b) as ((a%mod)*((b^(mod-2))%mod))%mod

Funny thing I learnt this during the last 5 mins ..., was lucky enough to make changes to the code just in time

Which fraction properties work in this way? I have checked several solutions and haven't found any with proper fraction implementation.

I think you could read articles on Modular multiplicative inverse and extended euclidean algorithm, to clarify your doubts.

Well I almost always use proper fraction implementations :) Why is it so difficult? 67745436

Instead of storing fractions like $$$p/q$$$, under mod $$$M$$$, we can store the fraction as a single number $$$p \cdot q^{-1}$$$, where $$$q^{-1} = q^{M-2} \pmod{M}$$$. I think you will find it's actually easier than trying to calculate with fractions.

It's a basic skill in number theory.

According to Fermat's little theorem, $$$a \cdot a^{p-2} \equiv 1（mod \enspace p)$$$, so we can use

`a * qpow(b, p - 2)`

instead of`a / b`

.It may help you

https://codeforces.com/contest/1279/submission/67731448

Why do you use java style, while classes and operator overloading is available?

Use modular class, which allows to divide by Fermat's little theorem

Not pretend on quality of my code, but works fine and fast enough: 67754717

so huge difficulty gap between D and E

I can't solve problem D because of not attending Math class at University. :((

What's the hack test for

B?can anyone tell why this case is showing 6 on this test case on an accepted solution. Problem B:-

6 26

1 1 1 23 109 110

value of s is 26 so according to me it's not possible to reach till 6 so how it can skip 6th part.According to me answer should be 0. Did I understand the problem wrong? Please tell someone.Thanks.

Multiple correct solution

I think both 0 and 6 are correct answer

Surprised that so less people used binary search in B.

How to use binary search in B.

Assume that you have skipped over ith element, now try to find maximum index j (j>i), till where you can sing.

used binary search got wrong answer 3 times :(

What was the non-binary search way to solve B?

Removing the maximum from a range starting from 1st index is efficient. Store prefix sum and and prefix max for each position. If prefix sum is less than s then you need not remove any go to take next one.

If prefix sum>s then check prefix sum-prefix max<s or not. If less than then you can remove that max and proceed and go for next one. If s is less then you can't proceed any more. Stop and print position of your removed max.

Ah, got it, thanks!

Was just easier to write the brute force binary search without thinking

Really helped me, an amazing solution Thanks :)

What are the hacking test cases for 1279F - New Year and Handle Change ?

I forgot to add very stupid test. As far as I know the only test which broke solutions is just any test with $$$k \cdot l > n$$$.

For me it wasn't any test with $$$k \cdot l > n$$$; it was any test where 2 of the intervals had to intersect.

Sorry, this was a very silly mistake on my part :( I didn't even notice that because when I wrote my solution I tested it a lot and decided to just add a special if statement to handle that.

UPD: And, as I know, the only case where segments should intersect is the case when $$$k \cdot l > n$$$, otherwise you can arrange them in a way that they're not intersect and the answer will not increase.Yes, it's true that every test which breaks those solutions has $$$k \cdot l > n$$$, but not every test with $$$k \cdot l > n$$$ breaks those solutions(which is what your first comment said).

Can anyone tell the value p/q of second test case in D?

$$$\frac{3}{5}$$$

thanks

how to solve B?

You can remove one so removing the one with maximum value is efficient. prefix sum(no remove) or prefix sum-max(1 remove) should be less than s.

Make a prefix array. Iterate from start till pre[i]<=s (beacuse if pre[i]>s, there is no point of skipping this part), find the position of upper bound of value s+a[i] on prefix array. The position which gives the maximum value(upper bound position) is the answer

My CodeWhy the upper_bound of s+a[i]?

What is the maximum number of verse can be recited from the start using

s? What is the maximum number of verse can be recited from start if we don't include a[i]? Since we have built a prefix sum array, we will get same answer by adding a[i] to s. Consider it as we have recited a[i] already without using s.Can someone please help me debug my Problem D solution? Thanks in advance. https://codeforces.com/contest/1279/submission/67745426

The problem I face is in test case 37 where this code is outputting a negative number.

Remplace all a * b with (long long)a * b % mod

No it was a different mistake. Found it, Thanks anyways.

Hack for B ?

I think it's integer overflow!!

Is there any point in reporting people (if I happen to notice them) intentionally creating solutions from secondary accounts and hacking them?

For example, 67741362.

Can someone please explain solution for Problem D ?

For each gift, store the count of kids wanting it (cnt[ki]). The probability of selecting a kid is 1/n and the probability of selecting a particular gift for a kid is 1/size(ki), and probability of selecting a kid with having same gift is cnt[ki]/n.

Total prob for particular gift being valid decision = (1/n)*(1/size(ki))*(cnt[ki]/n)

Answer will be summation of all such prob.

can someone explain the idea for solving B problem please?,i didnt get idea

You can remove one so removing the one with maximum value is efficient. sum(no remove) or sum-max(1 remove) should be less than s.

okay thank you

Removing max value is not sufficient I think? in s = 3, and verses = [1,1,2,1,30] we should remove 2 not 30?

You need to find first prefix with sum > s and remove maximum in that prefix.

Got it, thanks!

My approach for problem B: Because you have to recite in the given order from the beginning, so you can recite parts until the total time $$$cur$$$ exceeding $$$s$$$. Now you find the longest part so far to skip because you can only skip 1. After skipping, total time $$$cur$$$ decrease to $$$cur - a_{max}$$$, keep reciting forward to the end if you can $$$(cur <= s)$$$. If the removing make the number of part larger, the skipped part is the answer, otherwise you shouldn't skip any parts.

okay i got it,thank's

When will ratings get updated?

Why the rating does not change for this round!!!

Can anyone tell me the problem in this cod, question B: 67739681

I have used set to store the cumulative sum of array. And for every index i , I am finding minimum number greater than s+ a[i].

How come div 1 people are there in final standings was this round unrated??

yes they will be in final standings..but while calculating ranks..they are not considered ..just observe the difference in your rank from the standings and the one that is on your profile

In problem B, what will be the output for the test case: 1 3 11 2 9 1 I think it should be 1. But when I checked the code of various others, their output varies between 0, 1, 2.

You have to maximize the no. of songs you can take. In this, there's no way of taking all 3 songs, so you can take atmost 2 songs. But, for that, you may exclude any song or not exclude any song at all, you may still be able to take only 2 songs. So, the possible answers are 0, 1, 2, 3.

Oh, thank you very much. Got it.

how to slove C? I can only think of a O(n^2) approach.

The optimal strategy is: each time you take a present, sort all presents above it in the order in which you will take them. So, when you take a present, if you already took some present that was under it, it will take 1 second to take it and otherwise it will take 2k+1 seconds (k is the number of presents above it).

Was this round Unrated?

Were there only 6 tests in problem B during the contest? And none with overflowing int.. hmm why!

Why pretests for B are so weak?

Waiting for editorial.

Upload the editorials now? I can't wait to learn how to solve D

PROBLEM (A)

what about this line????????

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<Note that it's ok to have lamps of the same color on the ends of the garland.

if i put 6 3 1 will it be okay?

because there 2 lamps will be the same color!! right or wrong?

Garland actually is a closed loop. If you had 5 red, 3 green, 1 blue, then a possible garland would have been $$$X-\color{red}{R}-\color{green}{G}-\color{red}{R}-\color{green}{G}-\color{red}{R}-\color{green}{G}-\color{red}{R}-\color{blue}{B}-\color{red}{R}-X$$$

Note that the two $$$X$$$ characters will be joined together when the garland will be worn, and then essentially two Red will come together.

But the question says that don't worry about satisfying the

different coloured neighbours conditionon closed loop, only worry about opened garland.so if they declared that the garland is open(special) than the process would be diffrent right,,,,,,,,,,,,

They already have indirectly conveyed that the garland is open, by saying

"Note that it's ok to have lamps of the same color on the ends of the garland"By

'the ends', they mean opposite ends. So your case of 6 3 1 will not be possible, because by the word "end" they don't mean same end.if A=6,B=3,C=1;

then ABABABACAA

HERE in the open garland two lamps are the same color!! so it satisfied the condition!!**__**

"Note that it's ok to have lamps of the same color on the ends of the garland

At the ends means the first and the last not the two last elements

When will the editorials be available?

In Problem E: I cannot understand how for input: 5 15 (In the given test case) ans= 3 1 2 5 4 Because all the possible permutations using 5 digits in lexicographical order are:

Can someone please explain me?

Is there someone who could help?

how to solve D? I feel it complex to get the probability when there's a lot of data. I can get 7/8 in example 1. I want to know how to get it in a easy way.

Since the values of present for each kid are distinct. Let the number of presents each of the n kids want be k1,k2.....kn respectively. Now Let us denote the values of presents that the first kid wants to be b1(1), b1(2), b1(3), ............., b1(k1) Similarly for the second kid b2(1), b2(2), b2(3), ............., b2(k1)....and so on for other kids.

Since the presents are distinct each available present can int the list of say d number of kids where d may vary from 1 to n. We can create a map to store the number of kids that want present i at index i of the map.

Now the choose in the way it is given in the question i.e. using all the three steps but consider only the valid ones.

So, probability to choose any child =(1/n) say the chosen kid is 3rd one .

Probability to choose any one of his present=(1/k3).

Say now the present chosen is denoted by b3(p).

Now the third step assigning is present it to any of the n kids. But we want it to be assigned to a kid who actually wants it. Then only that will be valid.

The number of kid that actually wants it we can get it from map, by mp[b3(p)].

So, now the probability that the present is correctly assigned =(mp[b3(p)])/n, where n is total number of kids.

So as a whole for that particular b3(p) present selected we have probability of (1/n)*(1/k3)*(mp[b3(p)])/n).

Do this for all the presents for every kid.

i.e.

1/(n*n) *[ 1/k1 *{ mp[b1(1)]+ mp[b1(1)]+ mp[b1(1)]...+mp[b1(k1)]} +1/k2 *{ mp[b2(1)]+ mp[b2(1)]+ mp[b2(1)]...+mp[b2(k2)]} + 1/k3 *{ mp[b3(1)]+ mp[b3(1)]+ mp[b3(1)]...+mp[b3(k3)]} ................................. ................. + 1/kn *{ mp[b2(1)]+ mp[b2(1)]+ mp[b2(1)]...+mp[b2(kn)]} ]

Apply MMI and get your answer.

Thank you vere much, and I have solved it with your help! Your answer is very detailed.

You're Welcome, wxc0914!

Won't we have the tutorial?

Auto comment: topic has been updated by pikmike (previous revision, new revision, compare).