chemthan's blog

By chemthan, 4 months ago, In English,

Hello everyone!

I am glad to invite you to Codeforces Round #604, which will take place on Dec/05/2019 17:35 (Moscow time). The round will be rated for both divisions.

Exactly 300 Codeforces rounds passed since my first one (Round 304). I have learned a lot of things here and have much fun in participating in the competitions. Now, I want to contribute to this community by proposing some problems. I hope that you will find something interesting in solving them.

The contest is prepared by me, laoriu, I_love_Hoang_Yen, coordinator isaf27 and CF admin MikeMirzayanov. As usually, we must specially thank to below people who make contest possible:

There will be roughly 6 problems in each division. Scoring will be announced later.

GL & HF! See you on the scoreboard.

UPD 1: Scoring

  • D1: 500 1000 1500 (1000+1000) 2250 3000.
  • D2: 500 1000 1500 2000 2000 2500.

UPD 2: Thanks for participating! Congratulations to the winners!

Top 5 Div1:

Top 5 Div2:

UPD 3: Sorry for delay, this is editorial.

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

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

roughly means subtasks ??

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

    Ask codeforces contest style now. I'm also not fan of it.

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

      Let's talk more about this. You don't have decisive word on this matter? Then who decides it?

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

Please, don't use the $$$+$$$ sign when you don't mean mixed round, it kinda confusees

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

    Fixed, I just copy old one, didn't notice that. Thanks.

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

Most problems are nice, recommend to participate :)

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

    That means I won't be able to solve most problems :(

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

      Seems too much motivation for a guy asking others not to demotivate people(for those who dunno the context, see the below comment)

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

    I am really excited then!

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

    Thanks, Alexey, you haven't lied! (Не обманул)

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

I guess this will be an easy contest for me to achieve my goal of becoming violet.

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

    Your goal is blue not violet.

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

      Please don't demotivate anyone!

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

        Just joke, he is my friend :)

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

          Am I beautiful?

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

            Congrats for +1xx rating. Your dream comebacks now!

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

    Congrats your dream becomes true after years :)

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

one more amazing contest :))

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

It must be difficult and contains a lot of math-based problems =))

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

Good luck!!!

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

what does GL and HF mean?

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

    good luck and have fun -_-

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

      Me reading them: what does good luck and have fun mean? good luck and have fun -_-

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

The writers did awesome job this time — very interesting problems!

I really enjoyed testing this round and I highly recommend to everyone to participate tomorrow.

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

if i do bad it's automatically because mathforces not because i am bad

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

 every contest...

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

Technically how many problems need to be solved to become purple or orange?

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

    At the worst case, you need to solve everything in order to become purple or orange.

    Usually, you need to consistently be among the first few hundred placed people in div2 in order to get purple.

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

      You got him wrong, he meant "Please add me to your friends and see me in top ten"

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

    For purple : A + B + C fast enough, Easy D fast

    For orange : A + B + C + medium D fast enough, + easy E

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

    at least 4

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

Have a good round!

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

As far as I understand there will be sub-tasks in the round, for me personally this discourages any desire to enjoy the round. Because on CodeForces you can simply not solve a more complex subtask, and at this time people who write a simpler solution will bypass you. Yes, I understand that it may be that the subtask is also solved in a non-trivial way, then such a unit has the right to exist, but as I understand it now, it is necessary to add a subtask rather than an interesting division

with all due respect to the author of the round, this most likely refers to the latest trend

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

    Subtask 1's solutions usually are simplified versions of Subtask 2 ones. Like you replace one advanced data structure from the harder subtask with a simpler data structure and then boom you get subtask 1. So don't mind solving easier subtasks because they probably give you hints on harder subtasks.

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

      You probably didn’t follow my thought, if this is a cool subtask, then of course, but now it’s like a TREND and there is a chance that the subtask is solved simply

»
4 months ago, # |
  Vote: I like it -43 Vote: I do not like it

why my contribution went from 41 to 31 by itself :/ anyone knows ?

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

Why no registration possible?

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

My mood is not beautiful.

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

are the contests always hard ?

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

constructforces :v

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

.

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

Hard to focus on tasks while thinking about this NieR_Automata_20170316214758.jpg

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

How to solve div.1 E ?

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

    Minimise sum of squared outdegrees, I guess.

    Basically, any triple of vertices is either a cycle or there's one vertex with edges into the remaining two (while neither of them has edges to the other two, obviously). The number of triples with cycles is the total number of triples minus the number of such pairs of edges, which is $$$N(N-1)(N-2)/6 - \sum outdeg_i(outdeg_i-1)/2$$$.

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

Nice D2 1000

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

My summary of the contest: Phew.

»
4 months ago, # |
Rev. 2   Vote: I like it -74 Vote: I do not like it

I don't want to be rude or impolite or intolerant or whatever, but the round is f*** up!

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

For me contest was hard, but problems were interesting. How to solve div2D(div1B)?

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

    Notice that because of $$$|A_i - A_{i-1}| = 1$$$ condition, consecutive numbers can't have the same parity and hence $$$|cnt(even) - cnt(odd)| \le 1$$$

    Next step is to handle 2 more cases $$$\text{assuming 0-indexing}$$$:

    N is odd: if $$$cnt(even) - cnt(odd) = 1$$$, fill even positions with 0s then 2s and odd positions with 1s then 3s and vice versa when $$$cnt(odd) - cnt(even) = 1$$$

    N is even: try starting with both evens and odds

    Check if the array satisfies the conditions and print if it does

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

    Actually it can be solved in greedy approach.(in case nobody mentioned it before) the answer can start with either the smallest number or the second smallest number, try both of them. When filling a new digit $$$a_{i}$$$ , it could be either $$$a_{i-1}-1$$$ or $$$a_{i-1}+1$$$, try $$$a_{i-1}-1$$$ first, if you don't have more $$$a_{i-1}-1$$$ then try $$$a_{i-1}+1$$$, if you dont have it neither, then stop.

    Hopefully you can understand it cuz my english is not good enough.

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

    1.Take a deque. 2.insert 0 if a>0 or insert 1 if b>0 or insert 2 or 3 using the previous condition for each number. 3.Now you have a head and a tail in the deque. 4.Then you continue pushing the remaining element.if its absolute difference with the tail element is one then push the element in the back of the deque. If it cannot be pushed to the back check whether it can be pushed in front. 5.if you have a+b+c+d>0 and you dont have any opportunity to push a new element you can break and print no.Otherwise the answer will be Yes and print the deque.

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

How to solve probability question?

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

    Expected days ( x )= sum of p[i]*number_of_days_passed

    x= (1-p[0])*(1+x) + p[0]*(1-p[1])*(2+x) + .... + p[0]*..p[n-2]*(1-p[n-1])*(n+x) + p[0]*p[1]*..*p[n-1]*n

    solve the equation for x under modulo, p[i] being the probability ( after dividing by 100 )

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

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

    The meme of your account photo is so compatible with the picture.

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

EXACTLY THE SAME PROBLEM WITH E Sadly, I didn't know before contest ended..

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

So, what is a "normal" way to implement B?

(I did something very horrible: assume the string is of the form $$$(2)^e (3\, 2)^f (3\, 2\, 1)^g (2\, 1)^h (2\, 1\, 0)^i (1\, 0)^j (1)^k$$$; try values of $$$e, k, i$$$ and deduce the rest from those. Then handle special annoying cases.)

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

    I implemented it by trying all possible values of first number. Then, if the last number is 2, always prioritize going to 3 over 1 and if the last number is 1, always prioritize going to 0 over 2.

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

      I am happy I did the same way! :D

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

        Came out with the idea. Just slight late and couldn't implement.

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

      can you please give proof of correctness of your solution? why does prioritizing works here? I got accepted by your method but still don't know why it's correct :(

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

        Divide numbers into 2 groups (0, 2) and (1, 3). We can see that all numbers in each group will be put at either odd or even positions only. So we only have 4 possible adjacent pairs: (0, 1), (0, 3), (2, 1) and (2, 3). The only invalid pair here is (0, 3) so our strategy would be keep them as far as possible. Hence, we can arrange group (0, 2) like this: 0 0 ... 0 2 2 ... 2 (put all 0s to the left). For (1, 3) it is: 1 1 ... 1 3 3 ... 3 (put all 3s to the right). The first number can be either 0 or 1 and you can fill the following one using above strategy. Then just check if it is a valid sequence.

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

    My solution is like:

    Try to see what the finally path look like: First it will be ...->odd->even->odd->..., i.e. alternating parity. Also 0 and 3 can not be adjacent. So just put 0 as early as possible and 3 as late as possible, and fill in the rest of the positions.

    Upd: There are actually two cases. If you have a sequence starting with an odd number, you should put 3 as early as possible and 0 as late as possible; otherwise, it is just what I mentioned above. Sorry for the confusion.

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

      Do you accomodate for strings like 101012121232323212101 ? [3,8,7,3]

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

        You don't need to put these 3-s in the middle: you can do something like 101010121212121232323.

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

          I tried this, did not work.

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

            What do you mean, didn't work? You don't think the string above is a 3 8 7 3?

            I think your solution probably just has an implementation bug somewhere or you're missing some cases. It's definitely not necessary to put the 3-s in the middle like that in any case.

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

    I implemented it in a very simple way:

    You must match 0 with 1, and so you do until you run out of 0 (otherwise it's impossible since you can't match the extra 0)

    Now you have "a first block" that looks like [0101...0]

    Do the same but for 3 and 2, you have "a second block" that looks like [323...3]

    Now you must merge both blocks with "a third block" that looks like [121...2]

    If you have an extra 1, you can plug it in into the first block. Same for an extra 2 but to the second block

    So the solution ends up being

    [extra 1][first block][third block][second block][extra 2]

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

      What if you have 2 extra 1s?

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

        If you have more than a single extra 1, that means you couldn't match it neither with a 0 (otherwise this extra 1 wouldn't exist, as it would have been plugged into the first block) nor with a 2 (otherwise it would have been plugged into the third block). So the answer is no

        Same if you have more than a single extra 2

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

          Won't it fail for 101012121232323212101 ? [3,8,7,3]

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

            My solution will work as follows

            [first block] := [01010]

            [second block] := [32323]

            [third block] := [1212121212]

            extra 1s = 1

            extra 2s = 0

            So the answer is:

            [1][01010][1212121212][32323]

            Without brackets:

            101010121212121232323

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

      it is not simple way for the second problem of the contest

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

    I have very strange solution. Let's denote how many times x goes exactly before y as c(x, y). And assume path will go from s to t. So we have 4 equations: c(1, 0) — c(0, 1) = (t == 0) — (s == 0) c(0, 1) + c(2, 1) — c(1, 0) — c(1, 2) = (t == 1) — (s == 1) same for 2 & 3... and another 4: c(1, 0) + (s == 0) = a c(0, 1) + c(2, 1) + (s == 1) = b c(1, 2) + c(3, 2) + (s == 2) = c c(2, 3) + c(4, 3) + (s == 3) = d

    For fixed s and t it is system of linear equations, take any 6 of them, solve with Gaussian elimination. So we know how many times we have each pair of elements adjacent, let's make c(x, y) edges from x to y in new graph. now we need Euler path in this graph if it exists. Check it with well known dfs in 10^5.

    Now just try all 4 x 4 pairs for s and t

    Say no to greedy solutions)

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

    I wonder if this solution is intended or not, I just went through all permutations of [0,1,2,3] and tried to find the answer if we use numbers in that order: https://codeforces.com/contest/1265/submission/66375662

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

Is there any efficient way I can increase my implementation ability? I got stucked in implementing A, C resulting to be unable to solve D(still implementation difficulty). I get stucked when I get multiple conditions and specially corner cases.

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

    It's alright to get stuck,you'll now solve the problems you were stuck on and won't get stuck in the future. :D

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

    How to solve B?

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

    Implementation is probably the easiest skill to improve because it's literally just practice. You can look at other people's solutions to see if there is a cleaner high-level idea that you are missing (and a lot of these carry over to other implementation problems as well), but in general just doing a lot of implementation problems makes you much better at it.

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

    For A the key observation is that you can substitute all ? by any of the three chars what is fitting there, ie simply check the previous and the next index.

    C and D simply anoying. There is surely some greedy, but that kind of problem is just search for corner cases.

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

      It's not common, but I actually think the nice insight in Div2D is one that lets you eliminate the corner cases (it's mentioned above, where you just try all possible starting values and force an order after that).

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

      C was simple. Take gold less and it's done. This idea needed a 30 minutes of coding. Can you imagine? I am dealing with the problem of implementing a solution quicker

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

        I tried. Giving as less gold as possible. Then as less silber as possible. Then as much bronze as possible.

        Sound fairly simple greedy, did not work for some reason.

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

          This solution works, you must have a bug. You can check my submission if you have any problems debuging yours. 66332463

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

      66352986 check this out for D, no corner cases at all.

»
4 months ago, # |
  Vote: I like it -63 Vote: I do not like it

Was not able to find the interesing problems in this contest, div2. A, B was more or less simple.

C, D anoying, I assume there is some greedy, but thats trial and error programming, at least for me. How can one find a proved solution ?

E is boring math and F way out of sight.

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

    Wow!

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

    yeah no, C D are not trial and error programming. Obvious greedy is obvious. Ain't the contest's fault if you don't know how to do greedy.

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

    Div. 2 A and B were always intended as obstacles for starters. They were not intended to be complex for people who have already been blue.

    C and D were greedy, yes, but you can easily prove their solutions. It was not even remotely hard to prove a greedy solution for C/D. Obvious greedy is obvious. If you don't like trial-and-error style of programming, then C can be solved with basic DSU, and, well, the math behind D can be easily proven with some analysis. I'm sure that such solutions wouldn't be too heavy in the implementation, and still satisfy what you called as "interesting".

    Okay, let's admit that E is too easy for an average div.2 E — but the math behind it was a nice practice for everybody, and encourages blue/cyan competitors to try out probabilities problem. F was hard, yes, but it was intended as a challenge for the best (among blues, at least). Most div.2 F is often 2100+ — what did you expected? E 1500, F 1600, and you need to solve all 6 problems to be in top 1000?

    Overall, the round does have some problems — E being a bit too easy, D's tricky 16th test case — but it was nowhere abysmal as you described. It's not the contest's fault when you sucks in the contest, and the contest wouldn't care either.

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

D1 was a nice subtask this time.

The depth can be calculated as follows: Pick some position, count number of ( on the left side, count number of ) on the right side, answer minimum of those. But there could be multiple positions giving the maximum depth. The observation we need is that there always exists a unique position where the count on the left side equals the count on the right side, and further at that position the count is always maximal.

To show this, find any position where the minimum is maximal, and move the position left (if there are more ('s) or right (if there are more )'s) until there is an equal amount of both. At that position both counts are equal, and the position where both counts are equal is unique (moving left either adds 1 to the number of )'s or decrements 1 from the number of ('s, and similarly for right.

So we can calculate for every position, for every count, the number of ways to have exactly that many ('s on the left side and exactly that many )'s on the right side, then multiply this by the count and add it to the answer. This is easy to do in $$$\mathcal{O}(n^{2})$$$, but I did not figure out how it could be done in $$$\mathcal{O}(n)$$$ for the second subtask.

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

    It was a useful subtask, but still not very interesting. It's just some DP(number of ways such that the i-th character is the d-th opening bracket) and DP(number of ways such that we have at least d closing brackets among the last i characters).

    At least D2 offers "hmm, how do I solve this?" rather than "yeah I'll obviously do this".

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

      A unique maximal position existing wasn't immediately obvious for me, that took longer to figure out than writing the implementation, so for at least the subtask was interesting.

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

        When the depth is at least $$$D$$$, we need $$$D$$$ opening brackets before $$$D$$$ closing ones, so for a fixed sequence, we just want to find the $$$D$$$-th opening bracket and check if there are at least $$$D$$$ closing ones after it. That was my way of thinking.

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

Is anything random in Div1.E intended to fail?

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

    For me it looks that they are trying to hack all greedy solutions now :)

    It would be great if someone knows counter-testcase for greedy, just to stip waiting :D

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

    Well, some heuristic solutions passed and some failed, classic

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

Okay contest. div2D was quite interesting.

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

How to solve Div2 B? Really stucked with it.

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

    You iterate $$$\mathrm{i}$$$ from $$$\mathrm{1}$$$ to $$$\mathrm{n}$$$, update $$$\mathrm{left}$$$ (leftmost position of all previous iterations) and $$$\mathrm{right}$$$ (rightmost position of all previous iterations) with position of $$$\mathrm{i}$$$, and $$$\mathrm{i}$$$ is beautiful if $$$\mathrm{right-left+1=i}$$$

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

      That is a really beautiful solution. Thanks for it. :) My solution during contest was much messier.

      I would just like to explain the intuition that I derived out of your solution: Since, we know that if there is a range possible for some $$$i$$$, it must only contain all elements $$$\le i$$$. So, at every step, we ensure that we are maintaining the smallest range $$$[l, r]$$$ s.t. all elements $$$\le i$$$ are contained in it, and just check to see whether it contains some other elements or not. If it does, the answer is $$$0$$$, otherwise $$$1$$$.

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

    Make an array of pairs of (number,index) and sort this array by number. Now for each prefix (1-i) of this array, we only need to check if all indices of this prefix form a subarray in the original array. If they do, then answer for i is 1,else 0.

    To check that, let S be the sum of the indices of prefix (1-i). And let M be minimum index in all these indices. Then (S- M*i) should be the sum of first i whole numbers (i.e sum(0-(i-1)) =(i*(i-1))/2.

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

    Keep index of all numbers in map, now start with i=1 to i=m use a set and result string initially which is initially empty

    for each m insert m in set, now take the first and last value from set, if this is equal to size of set then append '1' else append '0' to the result string

»
4 months ago, # |
  Vote: I like it -14 Vote: I do not like it

division 2 be like everybody do 3 questions and forget about the contest.

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

Can Div. 1C/2E be solved by segment tree and merging its left and right equation?

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

    Sure. When you know the formula for expected value, the rest is fairly standard "compute function over interval". It also works for a more general version of this problem where $$$P_i$$$ can be updated too.

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

      Oh wait, my wip solution actually works when the Pi can be updated too. I was overthinking on how to merge 2 intervals, where you have to store 2 value for each end. Turns out you just need a function to compute each interval value and can lazily update the checkpoint. Guess I'm still far away from being a master :<

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

    Probably, but that's a bit overkill for the problem. You really just need prefix computations of certain sums (in particular the product of the first i probabilities and then prefix sums on the product of the first i probabilities). Then you can answer any segment in log time by calculating the numerator and denominator independently and using modular inverse.

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

It was a very cool contest, especially considering that Div1B has so weak pretests, that solution from contestant, that didn't understand the statement, pass all of them.

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

    whaaaat?

    There were sooo many WA16 and several WA6 as well, and until I checked all cases thoroughly I got WA...

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

      I thought that all abs(s[i]-s[i+1]) should be equal to each other, not equal to 1. And my solution passed all pretests. There are no tests like 0 2 0 0 or 2 0 2 0.

»
4 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I participated after 1 month and totally disappointed that....i couldn't do what was my minimum expectation -_-

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

Thank you for perfectly balanced round!
I will wait your next rounds :)

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

How to solve div.1 C?

I can only solve its easier version div.2 E with a simple probability dp...

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

    I couldn't finish impl it on time.

    but this should work, if you can get E(i,j)=from ckpoint i to ckpoint j. in O(1). since each update just change adj-ckpoint.

    you need to preprocess prefix sum of $$$P_i= p_1*..*p_i$$$, $$$S_i = \sum P_i$$$, $$$T_i = \sum P_i*i$$$

    since $$$E(i,j) = j-i + [dT_{i-1,j-1} - (i-1)*dS_{i-1,j-1} - (dT_{i,j} - i*dS_{i,j})] / P_j$$$.

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

      Thanks very much, I get your main idea.

      But I failed to understand your formula.

      According to yogeshk972 's comment, $$$E$$$ equals expected days from $$$1$$$ to $$$n+1$$$.

      $$$ E=(1-p_1)(E+1)+p_1(1-p_2)(E+2)+p_1p_2(1-p_3)(E+3)+ \dots + n\prod_{i=1}^n p_i \\ (\prod_{i=1}^n p_i) E=1+p_1+p_1p_2+\dots+\prod_{i=1}^{n-1}p_i \\ E=\sum_{i=1}^n \prod_{j=i}^n 1/p_j $$$

      Prework the suffix product of $$$p$$$, and the suffix sum of $$$\prod_{j=i}^n 1/p_j$$$, since we can get $$$E(i,j)$$$ in $$$O(1)$$$.

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

        damn it, you're right. The formula could much simpler as yours. perhaps that's why I didn't finish impl it on time:(.

        my formula is just directly calc all positive, and all negative. yes you can get much simpler form $$$(i+1)*Pi - iP_i=P_i$$$.

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

    Can you explain the simple DP approach?

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

      $$$E(X) = (E(X-1) + 1) * \frac{1}{P_{i}}$$$

      $$$E(0) = 0$$$

      Where $$$E(X)$$$ is the expected amount of days to get a "you're beautiful" from the X'th mirror.

      Intuition — To transition reach the i'th mirror, we first need to reach mirror i-1, which takes $$$E(i-1)$$$ days. After we get a yes from mirror i-1, we need one extra day (hence + 1) to get an answer from mirror i. Now we have a "cycle" of ($$$E(i-1) + 1$$$) days for the amount of days we expect until we have reached the i'th mirror and gotten an answer from it. Then it will take $$$\frac{1}{P_{i}}$$$ (geometric distribution) passes through the cycle until we expect the the i'th mirror to return "you're beautiful".

      Final answer is $$$E(N)$$$

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

        i have seen most of the solution involve this

        power(p[1], mod — 2, mod) why are we raising it by mod-2

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

          1 / p[i] means the inverse of probability p[i]. As we have to get the result modulo something, we can't simply just divide it with p[i], we have to take the modular inverse of p[i].

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

          Because the modulus is prime, $$$a^{m-2} \equiv a^{-1} \pmod m$$$ via Fermat's little theorem (which is a special case of Euler's theorem). It's a popular way of obtaining the modular multiplicative inverse $$$a^{-1}$$$ where $$$a \cdot a^{-1} \equiv 1 \pmod m$$$, which is the easiest way to "divide" numbers in a modulo field.

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

Expected number is too complex in wikipedia.Can anyone explain it more simple?

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

    Expected number of $$$x$$$ is summation of all possible values of $$$x$$$, each multiplied by its probability of occurrence. If $$$x$$$ is a continuous (not discrete) variable the summation is converted to integration.

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

    Check the blogs of Errichto. :)

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

How to solve Div2 C? Really stucked with it.

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

    take minimum gold, take silver until it"s greater than gold rest till n/2 is bronze. Also you can't take the contestants with minimum solve and can't divide contestant with equal solve between silver and bronze or bronze and no prize.

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

      Thanks, It really helps me a lot!

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

      I used same idea. But it gives me WA.Can you please tell me what wrong in my approach?

      Here is my Code

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

        I think problem is with your global array a. You are not initializing it to zero for each test case.

»
4 months ago, # |
  Vote: I like it -21 Vote: I do not like it

I just want to say problem C has too long of a statement. So, statementforces?

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

Well, that was an interesting round. Thanks to the creators!

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

My dreams of reaching blue seems impossible now

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

    Be calm see my profile I have struggled more than you but still I have not become an expert this site is more challenging.

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

    Keep calm. And solve problem after the contest.

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

Did anyone else solve div2B using DSU, where the adjacent values in permutation to be considered an edge, and we join them one by one while processing for each i, and the number being beautiful when the number of roots in dsu being 1?

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

https://hastebin.com/vezonuxuve.cs

So I'm relatively new to this, and I was pretty stumped on Problem A, Div 2 (got a TLE). https://codeforces.com/contest/1265/problem/A

Looked over a correct solution and noticed that instead of creating and adding to a string like I did, they first converted the inputted string to a list, and went through and modified the list.

Is working with a list, and not creating any new variables like this, really that much faster? Is it something else? Or is there a roadblock in my code that I haven't mentioned yet? Would appreciate any help

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

    From my point of view using a list does not give advantage in this problem. One hast to check the chars at position +1 and -1, both is a[i+-1], using a list or a string.

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

DIV2 A DFS FTW!

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

    Why do you need it? You can look at the front and back for questions and find the answer from this.

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

      I'm just too lazy to think of a greedy solution.

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

needless to say, pretests are shit

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

    So my B failed because of this dumb typo:

    if (a + b == b + d)

    I decided to look at the pretests and found that out of 17 pretests, 11 have no answer and the remaining 6 have an odd total numbers. Don't know if it's intentional or not ¯\_(ツ)_/¯

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

      No, it was not intended. It's just you are unlucky.

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

In problem B, what thinking or method has to be applied ?

»
4 months ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

For Div2 ProblemD: It was said that "The only input line contains four non-negative integers a, b, c and d (0<a+b+c+d≤105)."

But I got wrong answer on testcase #16 which is: 0 0 1 2

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

Why the answer for DIV2, D for 10th pretest (1 3 40001 40000) is NO? Why can't we do this like: 1 0 1 2 3 ... 3 2?

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

    it would be 1 zero and 2 ones but test case needs 1 zero and 3 ones.

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

      OK, so why it couldn't be with one more one at the end of answer, I mean: 1 0 1 2 3 ... 3 2 1, now I think it would be correct...?

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

        This test case will have an answer according to question. That can be either 1 0 1 2 1 2 3 2 3 .. or 1 0 1 2 3 .. 3 2 1.

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

          So why the answer is "NO"?

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

            The answer is "YES" but your output is "NO"

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

    NO is your output. Correct answer is what you say. Read the detail of your submission carefully.

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

    Answer would be YES 1 0 1 2 1 then (23) 40,000 times

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

      Read the detail of your submission carefully.

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

        OKK, right, so sorry.

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

so sad. D has weak pretest :((

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

Can someone please explain how do we get 112 as the answer in E second example? I was getting 100. Probably applying a wrong concept here!

»
4 months ago, # |
  Vote: I like it -21 Vote: I do not like it

66326596 Someone stole my code from ideone.com. It wasn't intentional but I used ideone.com with the default settings (public access to your code), Here is the link: https://ideone.com/pwlcr1 but I used the same link to write the answer for problem B in the Div 2 contest: 66336397 and as you can see it is the same as in the link.

Feynman

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

how can I increase my ability to solve B C D type problem easily??

just improving my skill in data structure.... is it enough ??

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

    Lmao, good one

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

    This old comment might help: link

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

    Nop , for solve those problems on CF is most important the experience , and always do upsolving reading the editorial and read betters codes of others contestants.

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

Finally I have a nice rating.

tfw not nice anymore

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

This is my 3rd contest on codeforces, and I am confused about the ratings change. In my first contest I was able to solve A only , my rating was 1370. In 2nd contest I was not able to solve any, my rating was 1255. In this contest I was able to solve A,B,C and my rating is 1314 ! lesser than the 1st contest even after solving more problems ?

How is this possible ?

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

    Rating is determined based on the rest of the competition. Let me give a fake example. 9000 people participate in one contest and 8000 of them are able to get >1 problem right. Let's suppose there is another contest with equally good people and the same number of people in which only 3000 of them get >1 problem. Then, if you solve a problem in the first contest, it is not as impressive as if you solve a problem in the second contest. So your rating does that; it is based not exclusively on how many problems you solved but how many you solved relative to how many other people solved. For more detailed information, see here.

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

    Here's an outline of how the rating system works. Contest rating != performance in only the last contest. It's a cumulative measure. It increases if you perform better than the expected performance (which depends on your rating before the contest began), and decreases (or stays constant) otherwise. Also, before the first contest, your base rating is taken as 1500, so think of the first contest as a change in rating from 1500 to 1370.

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

      Thanks bighead, you live here free of a rent for whole year — Jin yang

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I think problem c on div1 is be more beutiful if have one more query that change the Possibility

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

    Nah it's pointless a bit more codin'. Doesn't make it any more "beautiful"

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

For anyone interested to know why the expected number of trials in mirror $$$j$$$ before going to mirror ($$$j+1$$$) is $$$\dfrac{1}{p_j}$$$ ($$$0<p_j\le 1$$$, will remove the subscript $$$j$$$ in the proof to reduce typing):

Let the expected value be $$$E$$$,

$$$E=\sum_{i=0}^{\infty} (i+1)*p*(1-p)^i$$$

$$$=p*\sum_{i=0}^{\infty} (i+1)*(1-p)^i$$$

Let $$$s = \sum_{i=0}^{\infty} (i+1)*(1-p)^i\, \textbf{(1)}$$$

Multiply both sides by $$$(1-p)$$$: $$$s(1-p) = \sum_{i=0}^{\infty} (i+1)*(1-p)^{i+1}\, \textbf{(2)}$$$

Subtract $$$\textbf{(2)}$$$ from $$$\textbf{(1)}$$$: $$$s(1-(1-p)) = 1 + \sum_{i=1}^{\infty} (1-p)^i = 1 + (1-p)\dfrac{1-(1-p)^{\infty}}{1-(1-p)}$$$ (using sum of geometric series)

$$$\therefore s = \dfrac{1}{p} + \dfrac{1-p}{p^2}$$$

$$$\therefore E = p(\dfrac{1}{p}+\dfrac{1-p}{p^2}) = 1 + \dfrac{1-p}{p} = \dfrac{1}{p}$$$

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

    Can you please explain how to build the solution to Div2 E using this ?

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

      I don't understand this , but you can see XLor comment https://codeforces.com/blog/entry/71916?#comment-562459 you can easily understand it.

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

        This is essentially needed to solve $$$Div1C$$$. But you can solve $$$Div2E$$$ in an easier way.

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

      90qvB

      I was just proving why the expected number of trials in mirror $$$j$$$ is $$$\dfrac{1}{p_j}$$$.

      This is how I solved $$$Div2E$$$:

      Let $$$E(i)$$$ be the expected number of days we have to spend before going to mirror $$$i+1$$$ if we started at mirror $$$i$$$. If we calculated $$$E(i)$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$, the answer is just $$$\sum_{i=1}^N E(i)$$$. To calculate $$$E(i)$$$:

      For $$$i=1$$$: $$$E(1) = \dfrac{1}{p_1}$$$ (because every trial at this mirror corresponds to one day).

      For $$$i>1$$$: $$$E(i) = (\dfrac{1}{p_i}-1)*\sum_{j=1}^{i-1} E(j) + \dfrac{1}{p_i}$$$ (because every trial from the first $$$\dfrac{1}{p_i}-1$$$ trials corresponds to going back to mirror $$$1$$$, and we have to spend $$$\dfrac{1}{p_i}$$$ trials (days) in total at mirror $$$i$$$ itself.

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

        Thanks a lot for the solution, never used Expectations this way. I solved it sometime back using the idea mentioned in this comment which appears slightly more intuitive. You may wish to look at it, in case haven't.

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

        I don't understand "expected number of trials in mirror $$$j$$$ is $$$\dfrac{1}{p_j}$$$".

        Won't that be the case if with probability $$$1-p_j$$$ you started back at $$$j$$$. But here, we are going back to $$$1$$$ right?

        I have read both your comments again and again, am I missing something obvious?

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

          I feel like I finally understand. I am too used to thinking about it using the Law of Total Expectation, so sharing it for others who might be stuck too.

          So, we have

          $$$E(j) = E(j|B)*P(B) + E(j|not B) * P(not B)$$$

          $$$E(j) = (1)*(p_j) + (E(j)+1)*(1-p_j)$$$

          Here, B is the event that the $$$j$$$th mirror tells you that you are beautiful, and $$$E(j)$$$ denotes expected number of days until we reach mirror $$$j$$$.

          Solving, gives the same thing, $$$E(j) = \dfrac{1}{p_j}$$$.

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

          Yes, this is the case if we started back at $$$j$$$. And since we actually start at $$$1$$$, each of the $$$1^{st}$$$ ($$$\dfrac{1}{p_j}-1$$$) trials is followed by going back to $$$1$$$, and hence we add $$$\sum_{k=1}^{j-1} E(k)$$$ ($$$\dfrac{1}{p_j}-1$$$) times.

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

            I meant that, we cannot calculate time spent at $$$j$$$ this way.

            This first line you used,

            $$$E=\sum_{i=0}^{\infty} (i+1)*p*(1-p)^i$$$

            I still don't understand how the calculations are working out.

            This, according to me, assumes that with probability $$$1-p$$$ we start again at $$$j$$$.

            Also, in my own calculation above, when I use "expected number of days until we reach mirror $$$j$$$" it makes sense, but that means it's wrong, because then the answer would simply be $$$\dfrac{1}{p_n}$$$.

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

              Yes this assumes that we will start again at the same mirror, as if this mirror was a checkpoint.

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

    $$$E = 1 + (1 - p) \cdot E$$$ (We do one step and with probability (1 — p) we start over)

    You could start from this as well =)

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

      Thank you. I didn't express expected values before using this way, but it seems really great.

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

    Generally, your explanation is the same as the expected value of Geometric distribution?

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

      Yes it looks similar. Some example (as mentioned in the Wikipedia page) would be the expected number of dice throws until the number $$$1$$$ appears (here $$$p=\dfrac{1}{6}$$$, so the expected value is $$$6$$$).

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

For Div1 E,it can be showed that this problem is quite similar to a problem in Chinese Contest WinterCamp 2007,the code can be easily searched by Baidu or Google. for example,the following blog posted the code in 2018 https://www.cnblogs.com/zhoushuyu/p/9146420.html According to the rule about the Third Party code,i think i should not be unrated. MikeMirzayanov Please investigate this matter,Greatly thanks

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

Crazy match! I only solved A in the first hour. Thanks to E, It's very similar to bzoj2597 I solved. It gived me hope.

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

Beautiful Sequence gives me a beautiful FST :(

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

For div1 C, by mistake I output n lines. And perfectly, The pretests satisfy n=q, so I get a perfect FST......

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

Nice problems <3 BUT too many corner cases. BTW, Thanks for such a awesome contest <3

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

This is my solution for Div1 D1:

Let's first think about how to calculate the depth for a definite bracket sequence.

If the first element is ) or the last element is (, then it's useless and we can reduce the length of the sequence by one or two.

Otherwise, the first element is ( and the last element is ), so they form a match and we can increase the depth by one.

So we can define $$$\operatorname{solve}(x, y)$$$ for calculating the sum depth of interval $$$s[x\ldots y]$$$:

For the situation that $$$x\geq y$$$, the result is obviously $$$0$$$.

If $$$s_x$$$ is ) or $$$s_y$$$ is (, then $$$\operatorname{solve}(x, y)$$$ equals to $$$\operatorname{solve}(x+1, y)$$$ or $$$\operatorname{solve}(x, y-1)$$$.

Otherwise there is ability to increase the depth of the interval $$$s[x\ldots y]$$$:

  • $$$s_x$$$ is ( and $$$s_y$$$ is ): No matter how you determine the ? between $$$s[x+1\ldots y-1]$$$, $$$s_x$$$ and $$$s_y$$$ always form a match to increase the depth by one, so $$$\operatorname{solve}(x, y)=\operatorname{solve}(x+1, y-1)+2^{k}$$$, where $$$k$$$ equals to the number of ? in the interval $$$s[x+1\ldots y-1]$$$.

  • Either $$$s_x$$$ or $$$s_y$$$ is ?: You can determine whether the ? can be matched or not, and if matched, it's similar above, else we can just ignore the ?.

  • Both $$$s_x$$$ and $$$s_y$$$ are ?: If we determine $$$s_x$$$ to be ( and $$$s_y$$$ to be ), it's $$$\operatorname{solve}(x+1, y-1)+2^{k}$$$. If we determine $$$s_x$$$ to be )(and keep $$$s_y$$$ undetermined), it's $$$\operatorname{solve}(x+1, y)$$$, and $$$s_y$$$ to be (, it's $$$\operatorname{solve}(x, y-1)$$$. Note the situation that $$$s_x$$$ is ) meanwhile $$$s_y$$$ is ( will be calculated twice, so we need to subtract $$$\operatorname{solve}(x+1, y-1)$$$ from it.

Then we can solve Div1 D1 in $$$O(n^2)$$$. But I had trouble optimizing it to $$$O(n\log n)$$$ or better. Can someone help?

Upd: My code for Div1 D1: 66373927

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

In problem D. Beautiful Sequence The only input line contains four non-negative integers a, b, c and d (0<a,b,c,d <= 10^5) It should be <=0 because it says non-negative integers and input actually contains 0. I tried the question after contest and had a wrong ans because I thought that a,b,c,d>0

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

    The problem statement says $$$0 < a+b+c+d \leq 10^5$$$. I see why this could be misinterpreted, however it is not a mistake as it does not imply $$$0 < a, b, c, d$$$.

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

      you are right. I misinterpreted. Thank you for pointing out

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

Is there any reason that my all the solutions were skipped???

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

    Either you've shared your codes with somebody during contest or probably you'll be using online compiler like ideone in default mode public . And during the contest someone else have just copied and pasted your code and so you have been removed from this contest.

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

I coded E 10 minutes into the contest. When I was thinking of whether I should submit or not because it seems improbable for me to be able to solve E in 10 minutes, my PhD advisor called me and saved me the dilemma.

I just submitted and found out the solution was correct after all :(

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

    The important part is you can solve it.

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

When will the editorial be published?

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

can anyone explain me how to solve div2-D/ div1-B ?

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

    Form a graph with 0,1,2,3 as the nodes and edges from i to i+1 and i to i-1 for each i in [1,2] and the edges 0->1 and 3->2. Then perform a DFS from each node and check if all the frequency of occurrence of each node can be made zero. Whenever a node is visited, decrement its frequency. When the frequency of a node becomes 0, then you can't visit it. Also, the DFS should be modified, since from one node, you should visit only one of the adjacent nodes. The answer is the order in which the nodes are visited if the frequency of all the nodes are made 0.

    https://codeforces.com/contest/1265/submission/66381723

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

easily passed div2c&e... pity went sleep early last night, or maybe rating++

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

My approach for problem Div.1D :

Given a string $$$s$$$, how to calculate its depth? It equals the number of positions where it reaches a depth for the first time. For a position $$$i$$$, suppose that there are $$$a$$$(s in $$$s[1,i]$$$ and $$$b$$$)s in $$$s[i+1,|s|]$$$, then we count this position if and only if $$$s[i]=$$$( and $$$a\le b$$$. Example: for string (()()), we count positions $$$1,2$$$.

When the string contains ?, things become harder. We iterate each position and find the number of string in which this position should be count. For a position $$$i$$$ that $$$s[i]=$$$( (if $$$s[i]=$$$?, we assume it's (), $$$a$$$ and $$$b$$$ are the same as above, $$$c$$$ is the number of ?s in $$$s[1,i]$$$, $$$d$$$ is the number of ?s in $$$s[i+1,|s|]$$$. Then the answer for this position is

$$$ \begin{aligned} \sum_{i\le j}{c\choose i-a}{d\choose j-b} \end{aligned} $$$

Bruteforce is $$$O(n^2)$$$. But we can find that

$$$ \begin{aligned} &\sum_{i\le j}{c\choose i-a}{d\choose j-b}\\ =&\sum_{i+a\le j+b}{c\choose i}{d\choose j}\\ =&\sum_{i+a\le j+b}{c\choose c-i}{d\choose j}\\ =&\sum_{c-i+a\le j+b}{c\choose i}{d\choose j}\\ =&\sum_{i+j\ge a-b+c}{c\choose i}{d\choose j}\\ =&\sum_{i\ge a-b+c}{c+d\choose i} \end{aligned} $$$

$$$c+d$$$ is a constant (or minus $$$1$$$ when $$$s[i]=$$$?), thus the problem is solved in $$$O(n)$$$.

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

    In the second step $$$\sum_{i+a\leq j+b} \binom{c}{i}\binom{d}{b}$$$

    shouldn't it be $$$\sum_{i+a\leq j+b} \binom{c}{i}\binom{d}{j}$$$ ?

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

    share a simple way to get formula instead of math.

    just let all ? be ( first. then $$$delta = b - k$$$, where $$$b=$$$#( before i, $$$k=$$$#) after i.

    then any ? no matter before/after i, change to ). will make $$$delta$$$ $$$-1$$$. and we wanna goal that $$$delta <= 0$$$. then get the answer equal to prefix sum of binomial.

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

Anyone want to explain their solution for Div1 E? I saw from other comments that it is a problem that has appeared before, but it seems like it's mostly appeared on Chinese contests so I can't read the solutions :(

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

    Brief Outline: The problem is equivalent to minimizing the sum of squares of outdegree of each node. Create a min cost flow graph where each unassigned match corresponds to an auxillary node, connected with cap 1 cost 0 to source and cap 1 cost 0 to the two players. For each player, add edges of cap 1 with costs $$$2o+1, 2o+3, ...$$$ where $$$o$$$ is the current outdegree of the node.

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

      Ah thanks, the sum of squares reduction was not at all obvious to me. Neat trick, in the end I guess it's just complement counting. The MCMF after that makes sense. It's a cool problem!

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

Good Luck!

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

how do you solve div2 E

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

    Let $$$E(i)$$$ represent the number of days to reach the $$$i^{th}$$$ mirror. Then we have:

    $$$E(i) = E(i-1) + 1*(p_i/100) + E(i)*(1-p_i/100)$$$

    Basically the equation means that if you reach the $$$(i-1)^{th}$$$ mirror, then with $$$p_i$$$ probability you reach the $$$i^{th}$$$ mirror the very next day, or you start over and reach it after the expected number of days to reach the $$$i^{th}$$$ mirror

    You can rearrange the equation to get a formula for $$$E(i)$$$ in $$$p/q$$$ form and solve using modular arithmetic.

    Base case is $$$E(1) = 1$$$ and final answer is $$$E[n+1]-1$$$

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

      I use similar approach.

      But i think (1−pi)/100 may be replaced with (1-pi/100)

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

The constraints of div1.E is too small. Actually it can be solved in $$$\Theta(n^4/w)$$$ by optimizing the process of cost flow.

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

Please provide the editorials.

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

There is a hard version of Div.1 B (s_i can range in [1,20000]) from my own host contest in the past:

https://codeforces.com/group/gRkn7bDfsN/contest/210347/problem/D

Everybody can give it a try~

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

For div2 problem A: I am getting a segmentation fault which I am trying to debug but unfortunately was unable to debug. Can anyone help me find the error I have made?

Here is the link to code: Link

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

    You have a typo in line 14 — it should be j++, not i++.

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

      But it becomes confusing for me when I print t. How this typo assigning t to a garbage value? where he is not using t later in the while loop.

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

      Thank you so much for pointing that out :)

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

Where is editorial ?

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

Hi chemthan, we need an editorial, thanks!

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

Waiting for author's solutions to the problems...)

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

    Your last while doesn't have any reason to stop

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

      Oooo... got it. What a bug?

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

      I get into problems during contest for these silly mistakes. And can't find what's wrong? How can I get rid of that?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +18 Vote: I do not like it
        • Print debug statements. For example, your while loop bug can be found by just including a debug statement in the loop.
        • Imagine you're the compiler and run everything in your head.

        Take a deep breath and tell yourself that you love debugging and there's nothing else you can't debug.

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

        It's not a silly mistake, or at least I don't call it so. You learn not to make these mistakes after failing at them. Next time when you have TLE you probably will look for infinite loops first, and after couple of times you'll start paying more attention to them while you're coding.
        Best way to not make these mistakes during the contest will be to make them during the practice!

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

Well I am so weak,Can somebody tell me how to do Div2 C?Thanks!

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

    take minimum gold (all with maximum solve)

    take silver until it's greater than gold

    rest til n/2 is silver

    while taking g,s,b make sure you are not violating rules 2,4,5

    finally have a check if conditions are fulfilled with your g,s,b

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

How to solve Div2 prob B, my solution is getting TLE. What is wrong with it? Would someone please explain

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

    I think your submission has complexity like t*n*n which is very large to complete in 1s even the sum of n from all test cases in the input doesn't exceed 2⋅10^5

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

      What is the efficient solution

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

        See the editorial I use the same approach

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

When will the editorials be uploaded?

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

Waiting for the editorial....

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

At least let us know when the editorial will be published? I am bored and tired of checking.

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

https://codeforces.com/contest/1264/submission/66453921

Looking at the comments my idea is similar, we first calculate answer with no checkpoints (which works, since I pass Div2E), and afterwards if we add a checkpoint j in interval [i, k], we have to decrease the answer by prod(i, j — 1) * prod(j, k) and add val[j — 1], when we delete j we need to merge intervals [i, j — 1] and [j, k], we do the opposite (add products, subtract val). This fails on first checkpoint addition on big test, so I cannot research that manually. Any ideas what I did wrong?

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

I get the error message "You are not allowed to view the requested page" when trying to view the editorial. chemthan please take a look.