Блог пользователя send_nodes

Автор send_nodes, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +264
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +257 Проголосовать: не нравится

Hope you prepare problems better than solve them

»
8 лет назад, # |
  Проголосовать: нравится -58 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Не расстраивайся... порешаешь собственный контест и станешь фиолетовым.

»
8 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I love you, minimario :)

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

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Best of luck to all

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

hope I can solve problem A & B this time

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

strongly advised to read all the problems :) :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whats the time duration for the contest?

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

excited for the round

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Delayed 10 Minutes

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Я думал, обычно, после серьезных изменений в системе проводится Testing Round, дабы все проверить. Что же в этот раз случилось? Тем более, что раунд должен был быть рейтинговым.

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

CF issues aside, the problems were quite nice and interesting

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain B?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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;

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! Awesome solution

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Комментарий скрыт по причине большого числа негативных отзывов о нем, нажмите здесь для его просмотра

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    use partial sum

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится -9 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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!

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

    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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It was a nice round.

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem A is harder then usually

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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

20512612

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    can u please explain it?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

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

      but it is amazing!

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Cool proof !

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is there ever going to be a -1?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have added explanation below if you are interested.

»
8 лет назад, # |
  Проголосовать: нравится +81 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you send_nodes! I like it!

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I feel that pretest for C is weak.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How much time system testing takes ?

»
8 лет назад, # |
  Проголосовать: нравится +227 Проголосовать: не нравится

Codeforces servers

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 .

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

bop turad.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will pending system testing end ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему я не могу посмотреть тесты на посылку на дорешивании? http://codeforces.net/contest/712/submission/20514680

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

such fucky