Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, history, 6 months ago, translation, ,

Hello Codeforces!

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

• +100

 » 6 months ago, # |   +2 Hope to become specialist in this round
•  » » 6 months ago, # ^ |   +4 Hope to become pupil in this round
•  » » » 6 months ago, # ^ |   +15 Hope to remain master in this round.
•  » » » » 6 months ago, # ^ |   -7 Hope to do some problem solving
•  » » » » » 6 months ago, # ^ |   +13 No
•  » » » » » 6 months ago, # ^ |   +7 Hope to wake up and actually do this round
•  » » » » 6 months ago, # ^ |   +2 HOPE I DONT COMPLETELY LOSE MY RATING TO ZERO.
•  » » » 6 months ago, # ^ |   +13 hope to have fun this round ! rating is just a number !
•  » » 6 months ago, # ^ |   +13 You have no need to wait . Just use magic to become specialist before this round .
•  » » » 6 months ago, # ^ |   +3 Could you show me the way you become Legendary when your rating is 1536?
•  » » » » 6 months ago, # ^ |   0 He got gift from santa just like me
•  » » » » » 6 months ago, # ^ |   0 Why I didn't receive any gifts =))
•  » » » » » » 6 months ago, # ^ |   +3 Merry Christmas!
•  » » » » » » » 6 months ago, # ^ |   +3 Merry Christmas!!
•  » » 6 months ago, # ^ |   0 BUT HOW YOU CAN AS YOU ARE A LEGENDARY GRANDMASTER BY THE WAY HOW YOU CHANGED YOUR POST FROM PUPIL TO LEGENDARY GRANDMASTER.
•  » » 6 months ago, # ^ |   +1 congrats on becoming LGM
 » 6 months ago, # |   0 Wow, that's amazing!
•  » » 6 months ago, # ^ |   +10 No
 » 6 months ago, # |   0 Just Misusing Santa's Gift
 » 6 months ago, # | ← Rev. 2 →   +9 Div3 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!
 » 6 months ago, # | ← Rev. 2 →   +1 .
•  » » 6 months ago, # ^ |   +12 wtf?
•  » » 6 months ago, # ^ |   +7 yeah lol what?
 » 6 months ago, # | ← Rev. 3 →   -10 .
 » 6 months ago, # |   +1 CODEFORCES SANTA BRINGING GIFTS IN THE END OF YEAR.
 » 6 months ago, # | ← Rev. 2 →   +2 Is the weird color thing going on the Christmas gift from CF? Yup
 » 6 months ago, # |   0 after this contest in my messages merry christmas you become newbie :D
 » 6 months ago, # |   +3 Anyone else experiencing the slowness of the website at the moment? Its just taking longer than usual
 » 6 months ago, # |   +19 5 minutes delayed :(
 » 6 months ago, # |   +16 Delayed
 » 6 months ago, # |   -7 delayed :/
 » 6 months ago, # |   0 why there is no sample test case explanation in c problem
•  » » 6 months ago, # ^ |   0 in problem, c is it necessary to reorder all the k elements or he can choose not to place some of the elements again.
•  » » » 6 months ago, # ^ |   0 Your questions are not related much. Santa cannot choose to not place elements, but it is not necessary for Santa to reorder any elements.
•  » » » » 6 months ago, # ^ |   0 ok
•  » » » » 6 months ago, # ^ |   0 my bad was using 32-bit int all the time so was looking in all other possible directions.
 » 6 months ago, # |   +2 When Speedforces meets slow website ...
 » 6 months ago, # | ← Rev. 3 →   -12 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
•  » » 6 months ago, # ^ | ← Rev. 2 →   +18 1) Problems with test cases2) Awful pretests3) Long queueChoose one.
•  » » » 6 months ago, # ^ |   +10 4
 » 6 months ago, # |   +162 Participants.
•  » » 6 months ago, # ^ |   -8 I really did that, cooked dinner after solving D.
•  » » » 6 months ago, # ^ |   -6 Only because of that, I have dinner.
 » 6 months ago, # |   -19 Now I know why I shouldn't participate in Educational Rounds
 » 6 months ago, # |   0 How to solve F?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -53 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +13 Well, it uses the trick from Aliens (from IOI 2016). You can read about it here
 » 6 months ago, # |   -8 how can pisquare be a legendary grandmaster? he has a highest rating of 1404In this contest i got confused by a legendary gm just after my ranking and thus found this user
•  » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ |   +12 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
•  » » » » 6 months ago, # ^ |   0 thanks for the infoNow i have become legendary gm too :p
•  » » 6 months ago, # ^ |   +19 chill bro :>>
 » 6 months ago, # | ← Rev. 3 →   +30 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
•  » » 6 months ago, # ^ |   +8 i had the same doubt
•  » » 6 months ago, # ^ |   +56 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.
•  » » 6 months ago, # ^ |   +1 1 1 1 and 1 1 2 and 1 2 1 and 1 2 2 have all 1/8 chance2 1 1 and 2 1 2 have all 1/4 chanceX, Z all chosen independently but Y is not (depends on X)P(X = 1) = P(X = 2) = 1 / 2So P(X = 1 and Y = 1) = 1 / 2, P(X = 2 and Y = 1) = 1 / 2
•  » » 6 months ago, # ^ |   0 Same doubt. Anyone can explain why 7/8?
•  » » 6 months ago, # ^ |   +3 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
•  » » 6 months ago, # ^ |   +3 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.
•  » » 6 months ago, # ^ |   +4 That's not true Answer is 7/8Model 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
•  » » 6 months ago, # ^ |   +4 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.
 » 6 months ago, # |   +22 Well-balanced round lol
 » 6 months ago, # |   +12 How to solve E?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -11 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   +12 Since no one is asking, how to solve E and F?
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ |   0 Magic changes the color, not the rating which predictor uses.
•  » » » 6 months ago, # ^ |   -8 Thanks :)
•  » » 6 months ago, # ^ |   0 its working fine
•  » » » 6 months ago, # ^ |   0 Thanks :)
 » 6 months ago, # |   +1 What was the test case 5 for problem D What could be done to prevent long value overflow in problem D
•  » » 6 months ago, # ^ |   +3 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.
 » 6 months ago, # |   +17 The gap between D and E is SOOOOOOOOOOOO HUGE
•  » » 6 months ago, # ^ |   +3 Seems F is easier than E...
 » 6 months ago, # |   0 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. We choose $x = 1$, Now, we have $2$ options for $y$ and $2$ options for $z$. This is $2 \times 2 = 4$ different choices We choose $x = 2$. Now, we have $1$ option for $y$ and $2$ options for $z$. This is $1 \times 2 = 2$ Totally, there are $4 + 2 = 6$ choices, out of which only $(1, 2, 2)$ is invalid. Please help me.
•  » » 6 months ago, # ^ |   0 1 1 1 and 1 1 2 and 1 2 1 and 1 2 2 have all 1/8 chance2 1 1 and 2 1 2 have all 1/4 chanceX, Z all chosen independently but Y is not (depends on X)P(X = 1) = P(X = 2) = 1 / 2So P(X = 1 and Y = 1) = 1 / 2, P(X = 2 and Y = 1) = 1 / 2
•  » » 6 months ago, # ^ | ← Rev. 2 →   +4 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: the probability that we choose $(1, 1, 1)$ is $\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$ , and this is correct; the probability that we choose $(1, 1, 2)$ is $\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$ , and this is correct; the probability that we choose $(1, 2, 1)$ is $\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$ , and this is correct; the probability that we choose $(1, 2, 2)$ is $\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$ , and this is not correct; the probability that we choose $(2, 1, 1)$ is $\frac{1}{2} \cdot \frac{1}{1} \cdot \frac{1}{2} = \frac{1}{4}$ , and this is correct; the probability that we choose $(2, 1, 2)$ is $\frac{1}{2} \cdot \frac{1}{1} \cdot \frac{1}{2} = \frac{1}{4}$ , and this is correct; We just summarize all the correct options and get the answer. It is equal to $\frac{7}{8}$.
 » 6 months ago, # |   +57 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!
•  » » 6 months ago, # ^ |   0 I definitely agree with that
•  » » 6 months ago, # ^ |   +4 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.
 » 6 months ago, # |   +6 How to solve F?
•  » » 6 months ago, # ^ |   +100
•  » » » 6 months ago, # ^ |   +18 Alien trick (or Lambda optimization, wqs binary search) is the keyword.
•  » » 6 months ago, # ^ |   +50 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.
•  » » » 6 months ago, # ^ |   0 Thank you very much, I understand
 » 6 months ago, # |   +7 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.
•  » » 6 months ago, # ^ |   +1 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.
 » 6 months ago, # |   +23 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}$.
•  » » 6 months ago, # ^ |   0 Thanks for explaining. I just posted a comment asking why. :)
 » 6 months ago, # |   +15 **Happy new year for all !!! & I'm very happy for this round !!! **
 » 6 months ago, # |   +3 How to solve A and C? :'(
 » 6 months ago, # |   +10 How to solve F?
 » 6 months ago, # |   +1 problem B confused me a Lot solved it in 22 attempt!
 » 6 months ago, # |   0 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/67746000I tried my code on various cases but it failed. Any help?Thank you :)
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 1 5 2 4 5 1 3 2 1 3 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.
 » 6 months ago, # |   -42 Hello, dear pikmike, it seems to me that you would be good at doing olympiads for mathematicians!
•  » » 6 months ago, # ^ |   0 I see no really mathy problem.
•  » » » 6 months ago, # ^ |   -27 Sorry, I didn’t read the problems, I thought they were as usual on mathematics
 » 6 months ago, # |   +1 Dont understand why my C is wrong? Seems such an easy problem -> https://codeforces.com/contest/1279/submission/67724577Probably I am not understanding the problem correctly, can anyone take a look as the wait is going to be too long!!
•  » » 6 months ago, # ^ |   +3 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..
 » 6 months ago, # |   0 Approach for A ?
 » 6 months ago, # |   +3 Proof for A?
•  » » 6 months ago, # ^ |   +1 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.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +1 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_2mx-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 •  » » » 6 months ago, # ^ | 0 how to come up with such ideas during contest? Anything other than practice?  » 6 months ago, # | +3 query contest  » 6 months ago, # | ← Rev. 2 → 0 Can someone help me figure out why am I getting Runtime Error in Problem D Test case 3. Here is my submission 67746943UPD: I am not able to understand what the diagnostics are saying. •  » » 6 months ago, # ^ | ← Rev. 2 → +2 Its because of the following declaration int item[100005]; Here, you declare an array of 105 whereas ai,j can be 106 as given in the constraints •  » » » 6 months ago, # ^ | -8 Oh it was a silly mistake thanks!  » 6 months ago, # | +10  » 6 months ago, # | -8 E seems copy of 553B - Kyoya and Permutation? •  » » 6 months ago, # ^ | +33 E was invented after Ne0n25 misunderstood the statement of that problem and solved a wrong version.  » 6 months ago, # | 0 I know D was simple for many including myself, but while solving it, did anyone have analogies with neural networks like me ?  » 6 months ago, # | +3 Did someone fail in D at test case 37? •  » » 6 months ago, # ^ | 0 Probably overflow •  » » 6 months ago, # ^ | 0 Yup same case. https://codeforces.com/contest/1279/submission/67745426 Still dunno what's actually wrong. •  » » » 6 months ago, # ^ | 0 [Resolved] •  » » » » 6 months ago, # ^ | 0 How did you correct it? •  » » » » » 6 months ago, # ^ | ← Rev. 3 → 0 Instead of taking modInverse(n*n), I did modInverse(n)*modInverse(n). •  » » » » » » 6 months ago, # ^ | 0 Damn man :(  » 6 months ago, # | ← Rev. 2 → 0 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 ? •  » » 6 months ago, # ^ | ← Rev. 2 → +25 ans+=2*ce+1; This can essentially go$O(n^2)$for cases like sorted queries. And overflow$int$with ~$10^{10}$•  » » » 6 months ago, # ^ | 0 thanks! you are right. Even the output in third case goes beyond int .I should have thought about it before asking. •  » » » 6 months ago, # ^ | +16 Why so many downvotes? comment section here is weird •  » » » » 6 months ago, # ^ | +13 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...  » 6 months ago, # | +2 Legendary steeped CF =)) everywhere. I wish try once :>  » 6 months ago, # | 0 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.  » 6 months ago, # | +3 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... •  » » 6 months ago, # ^ | ← Rev. 2 → +3 Just treat fractions like (a/b) as ((a%mod)*((b^(mod-2))%mod))%mod •  » » » 6 months ago, # ^ | +1 Funny thing I learnt this during the last 5 mins ..., was lucky enough to make changes to the code just in time •  » » » 6 months ago, # ^ | 0 Which fraction properties work in this way? I have checked several solutions and haven't found any with proper fraction implementation. •  » » » » 6 months ago, # ^ | 0 I think you could read articles on Modular multiplicative inverse and extended euclidean algorithm, to clarify your doubts. •  » » » » 6 months ago, # ^ | ← Rev. 3 → 0 Well I almost always use proper fraction implementations :) Why is it so difficult? 67745436 •  » » 6 months ago, # ^ | +3 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. •  » » 6 months ago, # ^ | +5 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. •  » » 6 months ago, # ^ | +1 It may help you https://codeforces.com/contest/1279/submission/67731448 •  » » » 6 months ago, # ^ | ← Rev. 2 → +1 Why do you use java style, while classes and operator overloading is available?Use modular class, which allows to divide by Fermat's little theoremNot pretend on quality of my code, but works fine and fast enough: 67754717  » 6 months ago, # | +25 so huge difficulty gap between D and E  » 6 months ago, # | 0 I can't solve problem D because of not attending Math class at University. :((  » 6 months ago, # | +6 What's the hack test for B?  » 6 months ago, # | 0 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 110value 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. •  » » 6 months ago, # ^ | +10 Multiple correct solution •  » » 6 months ago, # ^ | 0 I think both 0 and 6 are correct answer  » 6 months ago, # | +4 Surprised that so less people used binary search in B. •  » » 6 months ago, # ^ | 0 How to use binary search in B. •  » » » 6 months ago, # ^ | 0 Assume that you have skipped over ith element, now try to find maximum index j (j>i), till where you can sing. •  » » 6 months ago, # ^ | 0 used binary search got wrong answer 3 times :( •  » » 6 months ago, # ^ | +1 What was the non-binary search way to solve B? •  » » » 6 months ago, # ^ | 0 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 •  » » » » 6 months ago, # ^ | 0 Ah, got it, thanks! •  » » » » 6 months ago, # ^ | 0 Was just easier to write the brute force binary search without thinking •  » » » » 6 months ago, # ^ | 0 Really helped me, an amazing solution Thanks :)  » 6 months ago, # | +7 What are the hacking test cases for 1279F - New Year and Handle Change ? •  » » 6 months ago, # ^ | +31 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$. •  » » » 6 months ago, # ^ | 0 For me it wasn't any test with$k \cdot l > n$; it was any test where 2 of the intervals had to intersect. •  » » » » 6 months ago, # ^ | ← Rev. 2 → 0 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. •  » » » » » 6 months ago, # ^ | 0 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).  » 6 months ago, # | 0 Can anyone tell the value p/q of second test case in D? •  » » 6 months ago, # ^ | 0$\frac{3}{5}$•  » » » 6 months ago, # ^ | 0 thanks  » 6 months ago, # | 0 how to solve B? •  » » 6 months ago, # ^ | 0 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. •  » » 6 months ago, # ^ | ← Rev. 2 → 0 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 Code`int n; cin>>n; ll s; cin>>s; ll a[n]; forn(i,0,n) cin>>a[i]; vector vec(n); vec[0]=a[0]; for(int i=1;imx) { mx=cnt; ans=i+1; } } } cout< •  » » » 6 months ago, # ^ | 0 Why the upper_bound of s+a[i]? •  » » » » 6 months ago, # ^ | 0 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.  » 6 months ago, # | -8 Can someone please help me debug my Problem D solution? Thanks in advance. https://codeforces.com/contest/1279/submission/67745426The problem I face is in test case 37 where this code is outputting a negative number. •  » » 6 months ago, # ^ | +1 Remplace all a * b with (long long)a * b % mod •  » » » 6 months ago, # ^ | 0 No it was a different mistake. Found it, Thanks anyways.  » 6 months ago, # | 0 Hack for B ? •  » » 6 months ago, # ^ | 0 I think it's integer overflow!!  » 6 months ago, # | +6 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.  » 6 months ago, # | 0 Can someone please explain solution for Problem D ? •  » » 6 months ago, # ^ | ← Rev. 2 → +1 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.  » 6 months ago, # | 0 can someone explain the idea for solving B problem please?,i didnt get idea •  » » 6 months ago, # ^ | 0 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. •  » » » 6 months ago, # ^ | 0 okay thank you •  » » » 6 months ago, # ^ | 0 Removing max value is not sufficient I think? in s = 3, and verses = [1,1,2,1,30] we should remove 2 not 30? •  » » » » 6 months ago, # ^ | ← Rev. 2 → +5 You need to find first prefix with sum > s and remove maximum in that prefix. •  » » » » » 6 months ago, # ^ | 0 Got it, thanks! •  » » 6 months ago, # ^ | 0 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. •  » » » 6 months ago, # ^ | ← Rev. 2 → 0 okay i got it,thank's  » 6 months ago, # | +33 When will ratings get updated?  » 6 months ago, # | 0 Why the rating does not change for this round!!!  » 6 months ago, # | 0 Can anyone tell me the problem in this cod, question B: 67739681I 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].  » 6 months ago, # | +1 How come div 1 people are there in final standings was this round unrated?? •  » » 6 months ago, # ^ | ← Rev. 2 → 0 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  » 6 months ago, # | 0 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. •  » » 6 months ago, # ^ | 0 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. •  » » » 6 months ago, # ^ | 0 Oh, thank you very much. Got it.  » 6 months ago, # | 0 how to slove C? I can only think of a O(n^2) approach. •  » » 6 months ago, # ^ | 0 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).  » 6 months ago, # | +4 Was this round Unrated?  » 6 months ago, # | ← Rev. 2 → +8 Were there only 6 tests in problem B during the contest? And none with overflowing int.. hmm why!  » 6 months ago, # | 0 Why pretests for B are so weak?  » 6 months ago, # | +19 Waiting for editorial.  » 6 months ago, # | +1 Upload the editorials now? I can't wait to learn how to solve D  » 6 months ago, # | 0 PROBLEM (A)what about this line???????? <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< •  » » 6 months ago, # ^ | 0 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 condition on closed loop, only worry about opened garland.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 so if they declared that the garland is open(special) than the process would be diffrent right,,,,,,,,,,,,
•  » » » » 6 months ago, # ^ |   0 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.
•  » » » » » 6 months ago, # ^ |   0 if A=6,B=3,C=1;then ABABABACAAHERE 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
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 At the ends means the first and the last not the two last elements
 » 6 months ago, # |   0 When will the editorials be available?
 » 6 months ago, # |   0 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: 1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 1 2 5 3 4 1 3 2 4 5 1 3 2 5 4 1 4 2 3 5 1 5 2 3 4 2 1 3 4 5 2 1 3 5 4 2 1 4 3 5 2 1 5 3 4 3 1 2 4 5 3 1 2 5 4 4 1 2 3 5 5 1 2 3 4 Can someone please explain me?
•  » » 6 months ago, # ^ |   0 Is there someone who could help?
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 6 months ago, # ^ |   0 Thank you vere much, and I have solved it with your help! Your answer is very detailed.
•  » » » » 6 months ago, # ^ |   0 You're Welcome, wxc0914!
 » 6 months ago, # |   0 Won't we have the tutorial?
 » 6 months ago, # |   0 Auto comment: topic has been updated by pikmike (previous revision, new revision, compare).
 » 2 months ago, # |   0 Is there anyone who can help me to find bug in my code? I can't find out why it is showing wrong answer in test case 3. Question no C. submission — https://codeforces.com/contest/1279/submission/79246638 I have seen codes with same logic got accepted so I am pretty sure my logic is fine.