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

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

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

 
 
 
 
  • Vote: I like it
  • +100
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to become specialist in this round

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, that's amazing!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just Misusing Santa's Gift

»
6 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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   Vote: I like it +1 Vote: I do not like it

.

»
6 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

CODEFORCES SANTA BRINGING GIFTS IN THE END OF YEAR.

»
6 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

5 minutes delayed :(

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Delayed

»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

delayed :/

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why there is no sample test case explanation in c problem

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +2 Vote: I do not like it

When Speedforces meets slow website ...

»
6 months ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

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, # |
  Vote: I like it +162 Vote: I do not like it

Participants.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I really did that, cooked dinner after solving D.

»
6 months ago, # |
  Vote: I like it -19 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -53 Vote: I do not like it

    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   Vote: I like it +13 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
6 months ago, # |
Rev. 3   Vote: I like it +30 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

    i had the same doubt

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same doubt. Anyone can explain why 7/8?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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, # |
  Vote: I like it +22 Vote: I do not like it

Well-balanced round lol

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve E?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +12 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it +17 Vote: I do not like it

The gap between D and E is SOOOOOOOOOOOO HUGE

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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, # |
  Vote: I like it +57 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I definitely agree with that

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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, # |
  Vote: I like it +6 Vote: I do not like it

How to solve F?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +100 Vote: I do not like it

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much, I understand

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it +23 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for explaining. I just posted a comment asking why. :)

»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve A and C? :'(

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    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, # |
  Vote: I like it -42 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see no really mathy problem.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Approach for A ?

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Proof for A?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

query contest

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    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, # |
  Vote: I like it +10 Vote: I do not like it

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

Did someone fail in D at test case 37?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +25 Vote: I do not like it
    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Why so many downvotes? comment section here is weird

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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, # |
  Vote: I like it +2 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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   Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # ^ |
      Vote: I like it +1 Vote: I do not like it
    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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

»
6 months ago, # |
  Vote: I like it +25 Vote: I do not like it

so huge difficulty gap between D and E

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

What's the hack test for B?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Surprised that so less people used binary search in B.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to use binary search in B.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    used binary search got wrong answer 3 times :(

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, got it, thanks!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really helped me, an amazing solution Thanks :)

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why the upper_bound of s+a[i]?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it -8 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack for B ?

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain solution for Problem D ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay thank you

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +33 Vote: I do not like it

When will ratings get updated?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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].

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +4 Vote: I do not like it

Was this round Unrated?

»
6 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why pretests for B are so weak?

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Waiting for editorial.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      so if they declared that the garland is open(special) than the process would be diffrent right,,,,,,,,,,,,

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the editorials be available?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Won't we have the tutorial?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.