send_nodes's blog

Codeforces Round #370 (Div. 2)
By send_nodes, history, 8 years ago, In English

Hi everyone. I'm trashfirstsearch, and I used to be blue...

Anyways, Codeforces Round #370 (Div. 2) will take place on 10 September 2016 at 19:35 MSK. As usual, Div.1 participants can join out of competition.

Much thanks to GlebsHP for helping me with preparing the contest, MikeMirzayanov for the Codeforces and Polygon platforms, and minimario and Wrong_Answer_Exceeded for testing problems.

This will be my first contest prepared on Codeforces, and I have prepared all the problems with the intent of making them interesting for everyone. It is, as usual, strongly advised to read all the problems.

Good luck, and I hope you will gain rating(and force someone else to lose it >:) ).

Update: Congratulations to the winners:

Div.1

  1. KrK

  2. halyavin

  3. fhlasek

  4. vintage_Vlad_Makeev

  5. Kmcode

Div.2

  1. __0v0__

  2. palayutm

  3. Strikeskids

  4. khanh.tang

  5. pkq2010

Here is the editorial.

I sincerely apologize for the problems during the contest. However, I hope everyone found the problems interesting! Thanks to everyone who participated and helped with the problems!

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

Comments Comments (127)
| Write comment?
»
8 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Round 370 clashes with Topcoder Wildcard Round and Round 372 clashes with Topcoder SRM 698. ;(

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

    Oh come on! after long time we're having a CF contest and now it conflicts with another contest! such life! -_-

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Good luck and high rating to all.....

→ Reply
»
8 years ago, # |
  Vote: I like it +257 Vote: I do not like it

Hope you prepare problems better than solve them

→ Reply
»
8 years ago, # |
  Vote: I like it -58 Vote: I do not like it

" and I used to be blue " is pretty unnecessary. everyone had a higher rating once (well, except tourist )

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Subregional ACM-ICPC in Brazil will be in same time ;(

→ Reply
»
8 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I love you, minimario :)

this contest will be good because minimario is test the problems :)

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I hope one day i can be a problem setter too :) :)

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    nowadays, anybody can be a problem setter (wish you be one :) )

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck to all

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

hope I can solve problem A & B this time

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

    hope you solve A to D! a strong start!

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope the queue will not be working slowly like on some previous contests

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Well After A long time CF Today! Have to do Something Good B-)

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi, for a few weeks the page is showing me this js errors:

enter:399 Uncaught SyntaxError: Unexpected token <

jquery-1.8.3.js:4680 Uncaught Error: Syntax error, unrecognized expression: href=#

or on anaother page: contests:297 Uncaught SyntaxError: Unexpected token <

It makes difficult to log in (once you are logged out), as the js stops to work, I had to submit the login form from js console manually.

Please also let me know where is better place to discuss such issues.

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

strongly advised to read all the problems :) :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats the time duration for the contest?

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Looking forward to interesting problems~ good luck && have fun!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I like the line "Hi everyone. I'm trashfirstsearch, and I used to be blue..." I hope that I will be blue after today's contest.
EDIT: I still wish to be BLUE

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

    I hoped about being purple. I almost got it but then the round was declared unrated.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

excited for the round

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Delayed 10 Minutes

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Unrated! ): I was doing pretty well this time too.

→ Reply
»
8 years ago, # |
  Vote: I like it +83 Vote: I do not like it

Old but gold

Open questions:

1) is P!=NP ?

2) What is the fastest algorithm for multiplication of two n-digit numbers?

3) Can the rotation distance between two binary trees be computed in polynomial time?

4) Will a day come in future that Codeforces server problems be permanently solved?

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

    i don't know the answer for 1 & 2 & 3 but the last one my answer is impossible

    → Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

CF issues aside, the problems were quite nice and interesting

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck, and I hope you will gain rating(and force someone else to lose it ) Unrated

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain B?

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

    take the count of l,r,d,u.

    if((l+r+d+u)%2==1) ans is -1.
    else
    ans is (abs(l-r)+abs(u-d))/2;

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

      Thanks! Awesome solution

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      why did you divide by two! (abs(l-r)+abs(u-d))/2; To me, just abs(up-down) + abs(right-left) makes more sense! Any idea?!

      UPD: I got the idea, sorry for the inconvenience!

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

    Assume that an L is a -1 while a R is a +1. Similarly for D and U. Find the absolute net vertical movement and the absolute net horizontal movement. There is three cases. Let vert = abs of vertical. hor = abs of horizontal then 3 cases are:

    Case 1) vert==horizontal: Swap all horizontal to vert or all vert to horizontal, so answer is horizontal =vert Case 2) vert>horizontal: Two cases. Vert-horizontal is even or odd. If it is odd then answer is -1 because you can't make the odd go back to the origin. if they are even then the answer is (vert-horizontal)/2 + horizontal Case 3) Similar as case 2 but horizontal>vert. same logic.

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

      Isn't it simpler just to output (vert + hor) / 2 when the sum (vert + hor) if even, and output  - 1 otherwise? In fact, solution is equal to yours, but a little bit shorter.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Round is very very exiting, thanks! Only I hate probability in fifth task :P

P.S. I think I won't return in div 1 soon :D

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Haven't solve problems for a week and did a bad job in this round. Luckily it's unrated.

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Regardless of the server issues and the round being unrated, I have to say, the problemset is really interesting....

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D? I managed to come up with DP solution but it was too slow(by factor of k) and I couldn't get the complexity down.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    use partial sum

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 5   Vote: I like it -9 Vote: I do not like it

      UPD: This approach will get TLE. I didn't pay attention to complexity. My bad.
      Let dp[i][j] be the number of ways of playing i turns such that first player receives atleast j extra points than second. Clearly answer would be dp[turns][b - a + 1].
      For negative j, you can have another array dp2.
      See my code

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

        Okay, I did my dp iteratively and I guess by doing that I made too many unnecessary caluclations, but I tried doing it the same way, thanks!

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

        isn't this O(t * k * sum) ? Won't that be too slow?

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    tags : offline increment, dp

    let dp[i][j] be number of ways to gey sum j after i increments. for every dp[i][j] we mast increment from dp[i + 1][j - k] to dp[i + 1][j + k] by dp[i][j]. how to do it quicly in O(1). offline increment. just inc dp[i + 1][j - k] and dec dp[i + 1][j + k + 1] by dp[i][j]. then for every j (j > 0) dp[i + 1][j] += dp[i + 1][j - 1].

    so we have dp for A and for B now let's find the answer. let's brute possible A after t increments and if (dp[n][A] > 0) ans = ans + pref[A - 1] * dp[n][A], where pref[i] is prefix-sum of dp[n] for B

    that is all. so it works in O(t * mx) where mx is t * k

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

      thank you for explanation. I didn't understood the editorial, but your solution seemed easier to understand

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

    This is what I did; let me know if you need any clarifications: http://codeforces.net/contest/712/submission/20515549

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

It was a nice round.

I think that there should have been a testing round after changing the data center.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A is harder then usually

→ Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

First of all, contest frequency has greatly reduced. If CF is conducting a round after 10 days, then atleast there should be both Div1 and Div2 contests. The questions were really very nice. I didn't expect the quality to be this good. Hope to see more contests from you @trashfirstsearch.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why it is not rated it should be rated because the technical error involved all participants???

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

    No, I don't think so. For example, when I can load problem A, contest has started more than 10 minutes and a lot of participants AC two first problems!

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

I want to share one amazing solution for the third task :

20512612

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

    can u please explain it?

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

      I can not explane, I got two unsaccessful hacks on it :D

      but it is amazing!

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      I do.

      Let's invert the process and go from small triangle to big one.

      Proposal: If we can go from (y, y, y) triangle to (p, q, r) in T steps, and min(p, q, r) ≥ x, then we can go from (y, y, y) to (x, x, x) in T steps (or less).

      Let's use following greedy strategy: if we have triangle (a, b, c), a ≤ b ≤ c, we will change it to (b, c, b + c - 1).

      Proposal: if we start from (y, y, y) and use this strategy, after T ≥ 1 steps we will have (FT(y - 1) + 1, FT + 1(y - 1) + 1, FT + 2(y - 1) + 1) (FT being Fibonacci sequence). Proof: by induction.

      So when we reach min(a, b, c) ≥ x? When fT(y - 1) + 1 ≥ x. As fT is integer, we want . Linked solution finds exactly such T.

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

        Cool proof !

        I understood relation wih Fibonnaci sequence very fast, but I couldn't put  - 1 in any of my formulas :)

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

          Basically all +1 and -1 are due to triangle inequality a + b > c being equivalent a + b - 1 ≥ c in integer case. Which in turn is equivalent to (a - 1) + (b - 1) ≥ (c - 1). This problem is equivalent to problem when we allow degenerate triangles (e.g. a + b = c) after substracting 1 everywhere, i.e. original problem for (x, y) is degenerate-allowed-problem for (x - 1, y - 1).

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

    Is there ever going to be a -1?

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

      If x could be 1, then you could not proceed to any other triangle. But the contraint mentions that its not possible.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        When x=1 => y=1 (As area is always positive). Answer=0, right? I know constraints don't have x=y=1, but even if there was, it can't be an invalid transformation.

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

    I have added explanation below if you are interested.

    → Reply
»
8 years ago, # |
  Vote: I like it +81 Vote: I do not like it

Problem E: Quite ironically, 'Memory' couldn't recall its gender

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Genuinely surprised by the amount of AC's in C and D respectively. It appeared to me that D was much easier than C.

Does C really feature a simple and elegant solution to it? I feel like a retard looking at the number of successful submissions for this problem.

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

    Yes. You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks. Never thought of looking at the problem that way :(

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I agree with you. I think D is much easier than C. Simple solutions aren't necessarily easy.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you send_nodes! I like it!

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I feel that pretest for C is weak.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Another UNRATED contest!

Recent CF server problem is really taking a toll on everything :/ It totally decreases the enthusiasm and interest of the contest. Last few contests were really nice but this server failure is becoming a frequent issue now. I think the CF team should look into the matter and try to solve this quickly :(

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How much time system testing takes ?

→ Reply
»
8 years ago, # |
  Vote: I like it +227 Vote: I do not like it

Codeforces servers

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

    what does this circuit do?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Cooks potatoes

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

        you know that you can use potatoes as a batteries, I once did that on a university project, but the circuit caught me curiosity, I am interested in such things, if you can understand what i mean :3

        → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain problem C. I tried a greedy solution but obviously it didn't pass even the third test case given so I didn't submit. Is it solved by DP?

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

    you need the minimum number of steps to transfer an equal sides triangle to another equal sides triangle with length y and it has a greedy solution but in every step you should form a triangle so that a+b>c where a,b,c is the lengths of the sides

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

      I did, but I got the wrong answer for test 3. (22,22,22) to (4,4,4) Using the greedy algorithm I got:

      (22,22,22) (4,22,22) (4,19,22) (4,19,16) (4,13,16) (4,13,10) (4,7,10) (4,7,4) (4,4,4) but this solution takes 8 seconds not 6, the optimal solution.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1. :P

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

      Why is this correct? I thought of this solution but didn't write it because I couldn't prove it was correct.

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

        once u go from x to y, then u will figure out that this method is reverse of method y to x. it is like greedy. :)

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

        Yeah I was hung up on trying to prove it too & I couldn't, but I wrote it anyway since it felt right. Here's a proof I have afterwards, it's a bit convoluted but main idea is just that each triangle in the reverse process is the biggest possible:

        Let's always express a triangle is a triple [a,b,c] with a <= b <= c.

        Note first that it doesn't matter which way we go: the optimal number of modifications will be the same going from [x,x,x] to [y,y,y] as with [y,y,y] to [x,x,x].

        We'll compute the [y,y,y] to [x,x,x] sequence.

        The procedure is to start from [a,b,c] = [y,y,y] and then each step you transform triangle [a,b,c] into [a',b',c'] = [b,c,b+c-1]. You keep going till the maximum side length is >= x. The answer is (# of transformations)+2.

        A sequence of modifications that achieves this answer: do the same sequence of transformations, except in the last step, make the largest side x (instead of whatever b+c-1 >= x). Then in additional steps, modify the other 2 sides to equal x.

        Proof this answer is optimal:

        Property: our transformation [a,b,c]->[b,c,b+c-1] generates the "biggest" of all possible triangle that can result from modifying [a,b,c].

        That is, any triangle [d,e,f] that can be produced by legally modifying some side of [a,b,c] is "smaller" than our transformed triangle [b,c,b+c-1]:

        d <= b, e <= c, f <= b+c-1.

        Formally, this property is true because you're only allowed to change one side per step. So at least two of the the original sides of the triangle must remain in the new triangle: this means d <= b and e <= c. (to be sure of this you can check all three cases: a & b remain, a & c remain, or b & c remain: in any of the cases, the smallest side must be <= b, and the second smallest must be <= c).

        To bound f, we can use the triangle inequality & the bounds we have for d & e:

        f <= d+e-1 <= b+c-1.

        So [b,c,b+c-1] is indeed the biggest possible new triangle.

        Applying this property inductively, we see that the triangle produced after k of our transformations from a start triangle [y,y,y] is larger than any other triangle that could have been produced after k modifications from [y,y,y] (any other sequence of k modifications will produce a smaller triangle at each step)

        Now we can show that (# transformations)+2 is optimal for [y,y,y] to [x,x,x] with x > y: let k be the number of transformations we did in our process.

        By the optimality of the triangle in step k-1, we know that any triangle that is k-1 modifications from [y,y,y] has maximum side < x. This means you need at least (k-1)+3 = k+2 steps to get to [x,x,x]: after any k-1 steps, each side is strictly smaller than x; so then you're going to need at least one extra modification on each side to get to [x,x,x], which is >=3 extra modifications overall; so at least (k-1)+3=k+2 modifications are required to get to [x,x,x], which is what we wanted.

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

    just do brute force...

    define all sides=y... increase the smallest sides by maintaining positive area.. while akk the sides are not x, do this operation..thats it..

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

    I did greedy . start with triangle of side Y and in every move pick the shortest side and set it to min(X,sum of other two sides-1) . Break when one of the sides reach X .

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

    Try the greedy solution from backwards.I mean try to get (x,x,x) from (y,y,y). Here is my code : http://codeforces.net/contest/712/submission/20513444

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

    It can be solved simply by taking kinda Fibonacci nos. type of approach.Something Like

    arr[i]=arr[i-1]+arr[i-2]-1

    It's trivial that a+b<c for a valid triangle, at any time during the transition phase. And, trivially it's observable that whether I go from larger to smaller triangle or vice versa the answer is the same. Hence, if the input is

    28 3 The sequence shall be :

    3 3 5 7 11 17 28

    Rest, is here ..

    http://codeforces.net/contest/712/submission/20508329

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

I think problem E can be solve by SegmentTree. Each node[L, R] consider x is probability dominate [L, R], y is probability to start at R finish by winning at R and never lose at L, then the formula we need to merge two nodes a, b is: result.x = a.x * b.x / (1 - a.y + a.y * b.x), result.y = b.y + (1 - b.y) * a.y * b.x / (1 - a.y + a.y * b.x).

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

    I can confirm for result.x:

    _result.x = ax*bx * (1 + (1-bx)*ay + [(1-bx)*ay]^2 + ...)_

    which is

    _result.x = ax*bx * Lim(k-->+inf){ [1-((1-bx)*ay)^(k+1)] / (1-ay+bx*ay) }_

    which simplyfies to precisely your formula.

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

    I can confirm for result.y too, since it is based on the same reasoning for result.x. Nice idea!

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

bop turad.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the problems are very nice,but Unfortunately.it's unrated..what a pity...anyway,thanks for prepare the problems

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve 712D - Memory and Scores using Irwin-Hall distribution?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will pending system testing end ?

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

    If you click on the "problems" tab, the testing progression will show on the right — that should give you some gauge. Generally it also hangs up for a bit when it reaches 100%.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was about to finish writing Sqrt Decomposition solution for E, but I didn't make it. ;(

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I was a bit delayed with DIV2-D because I don't understand the behavior of MOD very well. I initially applied it in cases where it should not be (in some of the intermediate calculations).

Can someone share any resources (or explain themselves) briefly how we should think about MOD-ding results? If there are some clear rules, e.g. "MOD-ding in cases X, Y, Z will affect the final result (e.g. if you just MOD-ded the final result after doing all the calculations, it would be different), so don't do it, but in cases A, B, C it's fine" — those would be helpful to know.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can Div2. D be solved using a top-down dp?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty interesting problems where I have learned a lot. Maybe it will be more funny when it's rated? :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain, how's number of games played will be (2*k+1)^(2*t) ??

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

    It's (2*k+1) choices for every player in every turn. Hence that number.

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

      2t because t is for each player. Therefore, at the end of the game, the number of ways to choose will be like this:

      [ (2k+1)*(2k+1) ] * [ (2k+1)*(2k+1) ] * ...... t times

      *2k + 1 * because we must separately count 0.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

such fucky

→ Reply