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

Автор TooDumbToWin, 6 лет назад, По-английски

Hello, Codeforces!

I would like to invite you all to the International Coding Marathon 2018, under the banner of Technex'18, IIT (BHU) Varanasi. It will take place on Thursday 15th February 2018, 20:05 IST. The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions.

The problemset has been prepared by me (TooDumbToWin), DeshiBasara, hitman623, dhirajfx3, karansiwach360 and Enigma27. We would like to express our heartiest thanks to vintage_Vlad_Makeev and KAN for their constant help in preparing the contest and MikeMirzayanov for the amazing Codeforces and Polygon platforms. We also thank AlexFetisov and winger for their invaluable help in testing the problems.

Prizes

  • Overall 1st place: INR 35,000
  • Overall 2nd place: INR 25,000
  • Overall 3rd place: INR 15,000
  • 1st place in India: INR 10,000
  • 2nd place in India: INR 8,000
  • 3rd place in India: INR 6,000
  • 1st place among IIT (BHU) Varanasi freshmen: INR 1,000

Participants will have 2 hours to solve 7 problems. The scoring distribution will be announced soon.

Good luck everyone! Hope to see you on the leaderboard.

Update: Scoring is 500 — 1000 — 1500 — 2000 — 2500 — 2500 — 3000

Update 2: Thanks to all participants and congratulations to all the winners. The winners, who are eligible for prizes, will soon be contacted regarding the same.

Overall top 10

  1. Radewoosh
  2. fateice
  3. Um_nik
  4. laofudasuan
  5. dotorya
  6. 300iq
  7. LHiC
  8. ksun48
  9. wxh010910
  10. chemthan

Indian top 5

  1. PrashantM
  2. rajat1603
  3. Baba
  4. jtnydv25
  5. adkroxx

Some problem statements were not clear. We deeply regret the inconvenience caused.

The editorial has been posted here. This was first contest set by most of us, so please help us do better next time by filling this form.

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

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

Is this like IIT BHU's contest — Manthan ?

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

    The only difference is Manthan is an event of Codefest, the annual coding festival of Computer Science and Eng. Dept. of IIT BHU while ICM is an event of Technex, the annual techno-management fest of our Institute.

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

What is INR?

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

2nd rated contest in 2 days, YaY

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

Can I say that happy Lunar New Year ……

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

Will it be a hackforces?

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

After the disaster yesterday where I failed systest on two problems (the pretests are really too weak), I decided to skip the Chinese New Year celebration and try to get my rating back on this one. Good luck everyone.

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

In my timezone, the contest will end at 23:35, so I could enjoy both of them :D.

a_1_1

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

deleted

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

Atleast 2 hours 30 min contest would have been better since there are 7 questions to solve.

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

    On the bright side, if you get stuck on a question, there will be another one of roughly the same difficulty.

    If you take a look at last year's contest, it was 7 problems in 130 minutes. I did a virtual of it and it seemed pretty appropriate.

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

I have one question TooDumbToWin. If Indian user get 1'st place at Overall, so it says that he(she) is 1'st plase in India. He(She) get INR 35,000 + INR 15,000?

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

    Every winner will get only one prize. If he's first overall and first in India, he will get the first overall prize and the second place in India will get the first and so on.

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

Предсказываю , раунд будет плохой

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

I can't de-register myself from the contest. I get a pop-up saying that I've at least made one action in the contest. (I really don't know whats this suppose to mean). I just hope it's not rated for me!

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

Feels like tourist is coming, cause of Um_nik's danger *_*

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

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

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

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

Contest prepared by Indians means, It's going to be Mathematical .

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

rating-=INF;

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

Jai Hind!

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

One of problemsetters is enigma27, contest will be with hacks (-_-)

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

rating predictor started working

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

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

A confirmed cheater — .Ali. and his clone Ali_Pi. Shame on you!

UPD: Disqualified — only in 3 minutes. Thanks (anyone) for being so incredibly responsive.

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

How to solve E?

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

As I cannot participate, because I'm at school, I decided to write a short editorial to some of the problems (and also the current class is really boring and I don't have anything better to do).

Lets begin with D.

The main idea is that we will use binary lifting. Twice. Let's consider the following algorithm — for every vertex u (when inserted) find the closest vertex v above it with w[v] ≥ w[u]. Lets have an array nxt[], such that nxt[u] = v. Then the query will be done by simply jumping to the vertex in nxt[], until our sum becomes larger than X. Obviously this is = .

To speed it up, we will have 2 binary liftings. The first on will be for finding the nxt[] and the second one will be for answering the queries. For the first one we will store the 2i-th parent and the maximum weight on the path and for the second one, we will store the 2i-th nxt[] vertex and the sum of the weights on the path. Well that's all and in such a way you can achieve .

Now let's continue with F (idk why this problem is F...) .

The main idea is to use CHT. Lets have dp[u] — answer for vertex u. Obviously dp[u] = min(dp[v] + a[u] * b[v]) for every . From here we get the straightforward solution. To get a normal solution, we simply notice that dp[v] + a[u] * b[v] is a linear function for a[u]. Well then we need to simply maintain a Convex hull trick, for every subtree. For this we will have DSU on tree. We can either use dynamic CHT or LiChao segment tree for maintaining the lines (LiChao will be much faster, as all X's on which we query are small integers). The overall complexity is .

It also can be solved by doing DFS order, and then segment tree of CHTs in each node on it. The complexity again is .

Well the round just ended I won't explain my idea for E, and it will be only F and D.

PS: How to solve G?

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

    I didn't solve it but I think the idea is let and calculate the number of ways to partition s into even-length palindromes, and then use some propogation on palindromic tree (which unfortunately I'm not familiar with).

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

      I had the same initial observation, but I have no idea how to do the part with finding the number of palindromic partitions. I would really appreciate if someone explains it.

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

    Problem D i did a solution using persitents + dynamic segment tree (one tree for calculating sum, another for calculating maximum). Mine seem correct although i didn't finish it in time

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

      Yes, this was the solution when problem was made but intended solution uses binary lifting which is much easier.

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

    for D, query type 2: number of nodes weight[R] >= weight [ (R -> parent[R] -> parent[parent[R]] -> .... -> 1) ], did i understand correctly?

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

    D: why is it optimal to take closest v above with w[v] ≥ w[u], when there could be many more nodes xi above with lower weight w[v] > w[xi] ≥ w[u] that we can now not take anymore because of weight constraint?

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

    Let weights of nodes be [5,4,3,7,2] So nxt[5] = 4 because node 4 is closest to 5 and w[4] > w[5](7>2) but isn't the optimal ans is sequence {5,3,2,1} so shouldn't nxt[5] = 3?

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

E
Observe answer is 2n - k·f(n) where f(n) is a polynomial of degree k.
Calculate answer for small values of n and Lagrange interpolate.
Is this expected solution?

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

    No

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

    I think u just need to differentiate and multiply by x the generating function (1 + x)N K times, and then just evaluate at x = 1.

    For example, for K = 2, we differentiate , then multiply by x, then differentiate again and then multiply by x again.

    I think if ur a math guy, this problem is really basic.

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

      I came to this, too. Couldn't manage to implement it though.

      How would one go about doing the differentiation and storing the combination of polynomials and exponentials?

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

        All the intermediate polynomials u will get can be expressed as xa(1 + x)b. One can use dynamic programming to calculate the answer.

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

          Aaah ok, dp[a][b] stores the coefficient of xa(1 + x)b, and go from there.

          Was this the intended solution, or was the one with the Stirling numbers the intended solution (or both)? Either way, nice problem!

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

      it'd be nice if you could share some links about these methods.

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

    Well, as it said in oeis.org: "The closed form comes from starting with (1+x)^n and repeatedly differentiating and multiplying by x", And finally replace x by 1. I could't finished the implementation in time.

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

    It is possible to write ik as the sum of binomial coefficients for j ≤ k. (see here for explicit formula).

    Then, we just need to solve the problem for when ik is replaced by , which is doable with a simple combinatorial argument.

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

    The other solutions seem too ugly for such an obvious problem so I'll share mine as well. The answer is number of ways to choose some subset of {1, .., n} and write a string of length k with elements of it. Let's first choose a string of length k and then choose some subset containing all characters of it.

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

    I have another approach and I think it's beautiful!

    The answer is . It's the number of ways to choose a non-empty team out of n participants, and then distribute k different marbles between the team members.

    This could be done in another order: First, choose the participants who get marble and add them to the team, then distribute the marbles between them and then choose an arbitrary subset of other participants and add them to the team. Counting the number of ways to do that in this order is easy, you can find the details in my submission: 35312404

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

      Can you please explain what does f[n][j] stand for in your code?

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

        It is the number of ways to distribute n different marbles between j participants such that every participant gets at least one marble.

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

    The problem is to find:

    Break into two sums and use the binomial expansion of (r + 1)^(k - 1) to show that

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

    I solved it using a recurrence which is:

    f(n,k)=n*(f(n,k-1)-f(n-1,k-1))

    Its pretty easy to derive this. :)

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

What is pretest 6 in F?

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

    There is an overflow issue in your code. B * M would overflow long long and you should convert to double for comparison. This is in the standard Dynamic CHT implementation.

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

Another math contest...

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

I'm only 1min away from getting F correct. I found the mistake when there was only 42sec left. I'm so pissed now. I am trying really hard not to cuss.

PS: I literally threw my mouse in rage.

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

    I was clicking on submit on E with 2 seconds left. Tell me about it.

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

I literally was submitting (probably) correct E at the last second ... and didn't make it!

EDIT: Luckily I got TLE at test 19. Everything's fine.

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

It took me 30 minutes and 3 clarification to understand D. Am I the only one who have trouble with statement of this problem?

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

    no

    I've your problem too :(

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

    Same bro. After the second public clarification, I gave up all hopes of solving D. Started to look for E, but not enough Math knowledge to break it.

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

    Codeforces is now a place to practice our reading and googling skills.

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

i don't like this contest at all ...

feel stupid for participating in the round ...

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

Any corner cases in C?

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

    i was checking whether gcd of a,b divides n.. if it does answer always exist.. this is where i was wrong.. in ax+by=n x and y can be negative but they cannot be here.. costed me 6 wrong submissions :(

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

      I was also stuck to find non-negative solution to ax+by=n.It was very late to realise that n is 1e6 and we can find it in O(n)

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

Someone please explain me problem C.

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

    In c we have to first check if any non negative integral solution exists to the equation ax+by=n;
    if not then print -1;
    else lets say a*x1+b*y1=n;
    you have to x1 cycles of length a and y1 cycles of length b.That's all i think.
    In the cycle edges will be between i to p[i]

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

      I solved it that way, and got a TLE in pretest 8.

      Is the usual way of outputting each integer one-by-one (by cout/printf) not fast enough?

      EDIT: If anyone still cares, turns out the problem with the code I submitted during the contest was quite subtle: there's an integer overflow I did not notice, i.e. probably not related to speed of output.

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

        Printf should be fast enough.

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

        I guess in c++ people usually two lines of code in starting of their main function.

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can make a small draft on the 1st pretest based on what the problem gave you. You will figure out: if g(i) = A, the i-th number of the permutation is within a loop of A element(s).

    Like, in the permutation [2, 3, 4, 5, 1], surely g(i) = 5 for all members, as:

    f(2, 1) = 3

    f(2, 2) = f(3, 1) = 4

    f(2, 3) = f(3, 2) = f(4, 1) = 5

    f(2, 4) = f(3, 3) = f(4, 2) = f(5, 1) = 1

    f(2, 5) = f(3, 4) = f(4, 3) = f(5, 2) = f(1, 1) = 2

    Similar to all other numbers.

    So, all N members must be divided in a way that there are x cycles of size A, and y cycles of size B (x and y are non-negative integers, and x*A + y*B must equals exactly N).

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

      i figured that out during the contest, but i didn't know how to check that N=x*A+y*B has a solution where x,y are non negative integers

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

        At first, initialize x and y with the value of -1.

        You can run a loop of integer i from 0 to N div A:

        If N - i * A is divisible to B, then a solution is found. Set x = i and y = (N - i * A) / B and break the loop.

        After the loop, if no solution is found (x and y are still equals to -1, that means there is no solution), output "-1" and terminate the program.

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

    Think about it like this. The problem asks you to choose a permutation P so that if you do i=P[i] A/B times i gets its initial value. For instance if A is 3, and P={2,3,1} if you apply the operation 3 times for i=1, it becomes 1 again. If you think about it, if you apply that operation on i A/B times and it becomes i in the end, then so will applying the operation A/B times on P[i], or P[P[i]]. You can think of it as a graph, with an edge from i to P[i]. So in the end you have to make cycles of length either A or B.

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

      It came to my mind during the contest, corrrect me please: I thought that the answer will be always P=[1 2 3 ... n] . Suppose x = min(A,B), so in x moves this permutation will always satisfy both function f and g.

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

Is G kind of similar to this problem: http://codeforces.com/contest/906/problem/E ? (Here, we want to count rather than find min).

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

Anyone else got TLE in pretest 8 of problem C? How to solve it fast enough, and do we need an output method faster than outputting each integer one-by-one by cout/printf?

EDIT: If anyone still cares, turns out the problem with the code I submitted during the contest was quite subtle: there's an integer overflow I did not notice, i.e. probably not related to speed of output.

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

    Hey man I saw your code and it looked fine. Maybe add the space and integer within a single printf? that might be faster.

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

    I think it might due to the gcd, but I don't know why.

    I use the same method and get RE on pretest 8.

    Finally, I found that it doesn't need to use gcd to solve something like ax+by=gcd(a, b), we could just enumerate x, then I got AC.

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

What the problem number C said,i didn't understand.Anyone please explain .

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

    You can make a small draft on the 1st pretest based on what the problem gave you. You will figure out: if g(i) = A, the i-th number of the permutation is within a loop of A element(s).

    Like, in the permutation [2, 3, 4, 5, 1], surely g(i) = 5 for all members, as:

    f(2, 1) = 3

    f(2, 2) = f(3, 1) = 4

    f(2, 3) = f(3, 2) = f(4, 1) = 5

    f(2, 4) = f(3, 3) = f(4, 2) = f(5, 1) = 1

    f(2, 5) = f(3, 4) = f(4, 3) = f(5, 2) = f(1, 1) = 2

    Similar to all other numbers.

    So, all N members must be divided in a way that there are x cycles of size A, and y cycles of size B (x and y are non-negative integers, and x*A + y*B must equals exactly N).

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

Баги курильщика

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

Unable to enter the Contest.Is any one facing the same problem

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

    Strangely enough, the standings site works quite fine. All other sections of the contest site failed to load.

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

nice contest and good problems:)

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

I love clear and concise statements. Great contest!

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

Can E be solved in O(k*log^2(k)) with some FFTs?

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

I've seen lots of DP approaches for problem E (I didn't understand it yet). However I want to share my approach heavily based on math.

It's not so hard to see that we want to calculate smth like:

Let's start from well known formula:

Now we know it's polynomial of x. Let's differentiate it:

. Let's denote it as (1).

Substituting x = 1 gives us:

. Let's denote it as (2).

Let's differentiate (1) one more time and set x = 1. We'll get:

. Let's call this equality as (3).

Summing (2) and (3) we'll get:

and so on and so on.

The only thing we are left with is to code :) Link to submission: link

P.S. I would be pleased if someone could explain DP approach.

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

    BTW, discussing this approach with Ancient_mage he gave another hint.

    We now know that our answer is in form 2n - k * P(x) where deg of P(x) is exactly k. So we can easily interpolate it in runtime calculating values of P(x) at k points straightforward.

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

    how did you get the idea of differentiating and substituting x = 1?

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

      I feel like it's standard thing when you want to crack some combinatoric formulas :)

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

    mentioned above, but my comment seems to be helpful for you.

    I'm not good at coding this part : 'and so on and so on'

    So I used more mathematical technique.

    Let's denote 2n = B[0]

    n × 2n - 1 = B[1]

    n(n - 1) × 2n - 2 = B[2]

    ...

    so that B[i] = 2n - i × n × (n - 1) × ... × (n - i + 1)

    Now, i calculated stirling numbers using dp, since it has the recurrence relation : S(n + 1, k) = k × S(n, k) + S(n, k - 1)

    And then, to calculate , we just need to calculate , because of famous formula of stirling number (of course second kind).

    I hope my comment helped you. Sorry for my bad english. Have a nice day!

    UPD: thanks for your help! Now I get to know how to type cleaner :)

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

      Thank you, now I got dp approach:) You can use TeX format embracing text with dollar sign.

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

I am very curious about why did i_love_you_bangladesh’s attempts on F and G were ignored. P.S. I have seen during the contest that his G passed pretests

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

TFW in D I have an if for the case to output 0 and I do not update the last...

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

All I did in Problem E was to google whether there exists some formula to compute the obvious summation. Within a couple of minutes I found this link and directly copied the Using Stirling Numbers summation mentioned in the second answer.
It is sad to see that such (very easily) googlable problems are present as hard problems. I wonder how the testers did not think about checking whether such a thing is easily available online or not.

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

    How to make a contest?

    Leave first 3 problems.

    Make an ok D problem, but make it harder by twisting the statements so that it is difficult to parse.

    Copy problem E.

    Make an obvious problem F.

    Again copy idea of problem G from Div1 E (atleast you accepted it above).

    Best part give less time to participants for the problem so that it looks less people were able to solve your harder problems and your contest looks good. Huh!, when will you make good contest? I generally give up seeing contest like this.

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

      It takes a lot of hardwork to create problems, so we should praise their hardwork. That is what I think.

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

        Yeah, it takes a lot of hardwork to create problems, but it doesn't take so much to copy them.

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

    I also was amazed after seeing that because kevinsogo discussed it in the IPC camp. And with two setters in the camp,then I thought may be it was intendedly made around the concept of that formula.

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

    F just combining convex-hull-trick and smaller to large (very innovative idea) and G some observation from another problem and its reduction to a discussed problem several times (also very innovative).

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

    This problem was my idea and I agree I should have checked the problem on Google before adding it. Apologies.

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

932E - Team Work So now I have to search over research papers for combinatoric summation formulas over the internet to solve a problem in CF ! I bet that 80% of the users solving this problem either knew this formula from before or found it searching over the internet during the contest and very few actually derived this formula in contest time. That's ridiculous ! Our programming skills should be tested in CF, not our googling skills !!!

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

    I thought the problem was really good, and deriving the formula was not that tough(Though I could not get AC in contest time due to a silly mistake :P) but it is disheartening to see so many AC's, courtesy of google. Nevertheless, interesting problem.

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

      I derived it in the contest time also, got WA and sadly it took so much time that I couldn't debug :( And after the contest I noticed that I just forgot to add MOD in a line and in another line an index of an array was mistaken. Other than this, my code was OK and got AC. And there are so many people who knew the trick beforehand and got AC within moments. But again, knowing is a plus point here. I'm just sad that I was so close...

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

finally !! i made it in the last moments =)))

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

Can anyone help me understand why that submission: http://codeforces.com/contest/932/submission/35308268 takes RTE ? Thank you !

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

i guess the answer for problem E is: sum(n!/(n-i)! * S(k,i) * 2^(n-i) ) with 1<=i<=k and S(k,i) is the stirling number of the second kind if we have k integer(distinct integers) and n sets (with distinct index) so we have C(n,i) ways to choose i sets . Also we have i^k ways to puts k integers into these sets. But also there are always some ways are the same. So I think how to count the repeated ways. For chosen i sets, we have S(k,i) ways to puts k integers into these sets and there are no set without any elements. But the indexs of sets are distinct so we have i! permutations for these sets. For n-i remained sets. We have 2^(n-i) ways to choose the set of these set. This step make the repeated ways to put elements I said before. So the answer is sum(C(n,i)*i!*S(k,i)*2^(n-i) ). with 1<=i<=n. But S(n,k)=0 for any k>n so: result=sum(n!/(n-i)!*S(k,i)*2^(n-i) ) with 1<=i<=k

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

sorry for my bad english. #Lovecommunity

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

I have a question. Why I'm not get point on this round?. Firstly I solved 6 problems and get 4th position then my gained point go to zero but why? I didn't understand Enigma27,[user:paran26] , DeshiBasara?

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

Teams was a nice problem, but it's mostly math.

The problem basically wants us to find:

$$$\sum_{i = 1}^N i^K \cdot \binom{N}{i}.$$$

One common trick in dealing with exponentiation is to use the following identity for Stirling Numbers of 2nd Kind:

$$$\sum_{k = 0}^n S(n, k) \binom{x}{k} k! = x^n.$$$

You can prove this using induction if you're not convinced. Anyways, returning to the problem at hand:

$$$\sum_{i = 1}^N i^K \cdot \binom{N}{i} = \sum_{i = 1}^N \binom{N}{i} \sum_{j = 0}^K S(K, j) j! \binom{i}{j} = \sum_{j = 0}^K \sum_{i = 1}^N \frac{N!}{(N - i)!i!} S(K, j) \frac{i!}{j! (i - j)!} \cdot j! = \sum_{j = 0}^K \sum_{i = 1}^N \frac{N!}{(N - i)! (i - j)!} S(K, j).$$$ Now it may seem as if we haven't gotten anywhere because calculating this expression naively is $$$\mathcal{O} (K^2 + NK)$$$ but this is actually pretty useful, mostly because we can play around a bit more. It's equal to:

$$$\sum_{j = 0}^K \sum_{i = 1}^N \frac{(N - j)!}{(N - i)! (i - j)!} \cdot \frac{N!}{(N - j)!} S(K, j) = N!\sum_{j = 0}^K \frac{1}{(N - j)!} \sum_{i = 1}^N \binom{N - j}{N - i}$$$.

Anyways, this gives a final result of: $$$\sum_{j = 0}^k S(K, j) \frac{N!}{(N - j)!} \cdot 2^{N - j}$$$.

This is messier than the first expression, but it is very easy to calculate. We can do the exponentiation using fast binary exponentiation. We can precalculate Stirling numbers in $$$\mathcal{O}(K^2)$$$ using dynamic programming (Stirling numbers have nice recurrence relations). And the rest is easy.

Total complexity is $$$\mathcal{O}(K^2 + \log N)$$$.

NOTE: I remember reading somewhere that Stirling numbers can be computed in better than $$$\mathcal{O}(K^2)$$$ using Lagrange interpolation. However, I can't seem to find where I read that, and I haven't studied interpolation. If this is true, we can make the complexity a little better.