chemthan's blog

By chemthan, 5 years ago, In English

Hello everyone!

I am glad to invite you to Codeforces Round #604, which will take place on 05.12.2019 17:35 (Московское время). 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

| Write comment?
»
5 years ago, # |
  Vote: I like it +53 Vote: I do not like it

roughly means subtasks ??

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

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

    • »
      »
      »
      5 years 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?

»
5 years 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

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

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

»
5 years ago, # |
  Vote: I like it +196 Vote: I do not like it

Most problems are nice, recommend to participate :)

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

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

    • »
      »
      »
      5 years 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)

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

    I am really excited then!

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

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

»
5 years 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.

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

    Your goal is blue not violet.

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

      Please don't demotivate anyone!

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

        Just joke, he is my friend :)

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

          Am I beautiful?

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

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congrats your dream becomes true after years :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

one more amazing contest :))

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -18 Vote: I do not like it

    I hope you won't call it mathforces

    you downvote you gray

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +139 Vote: I do not like it

      mathforces > hackforces > implementationforces/speedforces > bruteforces > 404ces

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

what does GL and HF mean?

»
5 years 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.

»
5 years 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

»
5 years ago, # |
  Vote: I like it +90 Vote: I do not like it

 every contest...

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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"

  • »
    »
    5 years 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

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

    at least 4

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have a good round!

»
5 years 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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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

»
5 years ago, # |
  Vote: I like it -43 Vote: I do not like it

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

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

    Focus on your rating instead of contributions

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's not that I care that much about contribution but that's weird

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

        It's called decay. Older blogs and comments give a smaller part of the contribution.

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

    It means your rating goes from 1441 to 1431 -_-

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why no registration possible?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My mood is not beautiful.

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

constructforces :v

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.

»
5 years 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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div.1 E ?

  • »
    »
    5 years 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$$$.

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Nice D2 1000

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My summary of the contest: Phew.

»
5 years 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)?

  • »
    »
    5 years 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

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve probability question?

  • »
    »
    5 years 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 )

»
5 years ago, # |
  Vote: I like it +75 Vote: I do not like it

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

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

»
5 years 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..

»
5 years 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.)

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am happy I did the same way! :D

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

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

    • »
      »
      »
      5 years 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 :(

      • »
        »
        »
        »
        5 years 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.

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years 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.

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

          I tried this, did not work.

          • »
            »
            »
            »
            »
            »
            5 years 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.

  • »
    »
    5 years 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]

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What if you have 2 extra 1s?

      • »
        »
        »
        »
        5 years 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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 years 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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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)

  • »
    »
    5 years 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.net/contest/1265/submission/66375662

»
5 years 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.

  • »
    »
    5 years 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

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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).

    • »
      »
      »
      5 years 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

      • »
        »
        »
        »
        5 years 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.

        • »
          »
          »
          »
          »
          5 years 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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 years 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.

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

    Wow!

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

»
5 years 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.

  • »
    »
    5 years 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".

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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.

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

Is anything random in Div1.E intended to fail?

  • »
    »
    5 years 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

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

    Well, some heuristic solutions passed and some failed, classic

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Okay contest. div2D was quite interesting.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 B? Really stucked with it.

  • »
    »
    5 years 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}$$$

    • »
      »
      »
      5 years 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$$$.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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

»
5 years 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.

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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 :<

  • »
    »
    5 years 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.

»
5 years 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.

  • »
    »
    5 years 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...

    • »
      »
      »
      5 years 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.

»
5 years 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 -_-

»
5 years 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...

  • »
    »
    5 years 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$$$.

    • »
      »
      »
      5 years 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)$$$.

      • »
        »
        »
        »
        5 years 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$$$.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the simple DP approach?

    • »
      »
      »
      5 years 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)$$$

      • »
        »
        »
        »
        5 years 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

        • »
          »
          »
          »
          »
          5 years 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.

»
5 years 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?

  • »
    »
    5 years 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.

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

    Check the blogs of Errichto. :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 C? Really stucked with it.

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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

      • »
        »
        »
        »
        5 years 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.

»
5 years 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?

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

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

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

My dreams of reaching blue seems impossible now

  • »
    »
    5 years 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Keep calm. And solve problem after the contest.

»
5 years 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?

»
5 years 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.net/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

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV2 A DFS FTW!

  • »
    »
    5 years 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.

»
5 years ago, # |
  Vote: I like it +73 Vote: I do not like it

needless to say, pretests are shit

  • »
    »
    5 years 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 ¯\_(ツ)_/¯

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

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

»
5 years 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

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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...?

      • »
        »
        »
        »
        5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

so sad. D has weak pretest :((

»
5 years 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!

»
5 years 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.

UselessDev

»
5 years 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 ??

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

    This old comment might help: link

  • »
    »
    5 years 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.

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

Finally I have a nice rating.

tfw not nice anymore

»
5 years 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 ?

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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

»
5 years 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

  • »
    »
    5 years 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"

»
5 years 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}$$$

  • »
    »
    5 years 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 ?

    • »
      »
      »
      5 years 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.net/blog/entry/71916?#comment-562459 you can easily understand it.

      • »
        »
        »
        »
        5 years 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.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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.

      • »
        »
        »
        »
        5 years 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?

        • »
          »
          »
          »
          »
          5 years 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}$$$.

        • »
          »
          »
          »
          »
          5 years 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.

          • »
            »
            »
            »
            »
            »
            5 years 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}$$$.

            • »
              »
              »
              »
              »
              »
              »
              5 years 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.

  • »
    »
    5 years 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 =)

    • »
      »
      »
      5 years 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.

  • »
    »
    5 years 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?

    • »
      »
      »
      5 years 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$$$).

»
5 years 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

»
5 years 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.

»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Beautiful Sequence gives me a beautiful FST :(

»
5 years 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......

»
5 years 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

Unable to parse markup [type=CF_MATHJAX]

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

»
5 years 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

  • »
    »
    5 years 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$$$.

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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.

»
5 years 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 :(

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

When will the editorial be published?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years 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.net/contest/1265/submission/66381723

»
5 years 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++

»
5 years 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)$$$.

  • »
    »
    5 years 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}$$$ ?

  • »
    »
    5 years 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.

»
5 years 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 :(

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how do you solve div2 E

  • »
    »
    5 years 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$$$

    • »
      »
      »
      5 years 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)

»
5 years 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.

»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Please provide the editorials.

»
5 years 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.net/group/gRkn7bDfsN/contest/210347/problem/D

Everybody can give it a try~

»
5 years 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

  • »
    »
    5 years 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++.

    • »
      »
      »
      5 years 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.

»
5 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Where is editorial ?

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Hi chemthan, we need an editorial, thanks!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Your last while doesn't have any reason to stop

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oooo... got it. What a bug?

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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.

      • »
        »
        »
        »
        5 years 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!

»
5 years 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!

  • »
    »
    5 years 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

»
5 years 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

  • »
    »
    5 years 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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for the editorial....

»
5 years 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/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?

»
5 years 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.