RomaWhite's blog

Invitation to CodeChef December Lunchtime 2019
By RomaWhite, history, 4 years ago, In English

Greetings Codeforces Community! We invite you to experience the monthly CodeChef Lunchtime for December. The 3-hour contest will offer 5 challenging problems to solve. It will be a great way to close this year on a happy note with your increased ratings!

The problem statements of the contest will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here: www.codechef.com/problemsetting/new-ideas.

I hope you will participate with your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

Setters: Nguyen Ngoc Trung (chemthan), Rami Alssadaqa (i_love_islam), Hasan Jaddouh (kingofnumbers)
Tester: Roman Bilyi (RomaWhite)
Statement Verifier: Jakub Safin (Xellos)
Mandarin Translator: Gedi Zheng (gediiiiiii)
Vietnamese Translator: Team VNOI (Songuku95)
Russian Translator: Fedor Korobeinikov (Mediocrity)
Bengali Translator: Mohammad Solaiman (solaimanope)
Hindi Translator: Akash Srivastava (devils_code)

Contest Details:

  • Start Date & Time: 28th December 2019 (1730 hrs) to 28th December 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
  • Contest link: www.codechef.com/LTIME79
  • Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.
  • Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good Luck!
Hope to see you participating!!
Happy Programming!!

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

Comments Comments (19)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Probably you have wrong date on timezone link :)

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

Hoping for balanced problemset this time!!

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

How to solve tree query problem ?

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

    My $$$O(Q \log^3 {N})$$$ solution got AC, not sure if that's intended.

    Quick summary of solution
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      The intended solution is $$$O(Q \log^2N)$$$, but the idea is completely the same.

      Just part with the computing child could be done in $$$O(\log N)$$$. You can do descent in segment tree to find the node where the sum becomes greater that a half and then binary search in which subtree this node lies.

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

      Actually, yours is $$$O(Qlog^2N)$$$. Because first time you search on at most $$$N - 1$$$ children. Then next time you search on at most $$$\frac{N}{2}$$$ children, then $$$\frac{N}{4} + 1$$$ children, and so on. Also, you can try using Fenwick Tree and enjoy running time.

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

        But isn't the summation close to:

        $$$\sum\limits_{0 \le i} \log {\frac{N}{2^i}} = \sum\limits_{0 \le i \le \log{N}} \log {N} - \sum\limits_{0 \le i \le \log{N}} i = \log^2{N} + \log{N} - \frac{\log{N}(\log{N} + 1)}{2} \approx \frac{\log^2{N}}{2}$$$
        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes. You are right. I had a mistake in estimating it. :(

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

          It's a better constant, at least.

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

How to solve STICK2 partially ?

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

    Use dp with states as number of sides,sum of sides and maximum side taken. for it to be a polygon the condition sum_of_sides>2*max_side_taken mast be satisfied!!

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

      I was using dp with 4 states the position I am at,number of sides,sum of sides and maximum side taken. How can we optimise the first state.

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

        number of sides is not required because the condition sum_of_sides>2*max_side_taken will never be satisfied for n<=2!! So it is not required to take number of sides as states!!

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

How to solve STICK2?

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

    The problem reduces to "given n, how many subsets of {1, 2, ..., n-1} sum to > n".

    We can, instead, calculate how many subsets of {1, 2, ..., n-1} sum to <= n.

    That is actually just (the number of sets of increasing numbers with sum <= n)-1 since we subtract the set {n}.

    We can calculate the number of sets of increasing numbers with sum <= n with a standard dp[k][n] = number of k element sets having a sum of n. Note that k < sqrt(n).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      dp[0][0] = 1;
for(int i=0; i<499; ++i) {
  for(int j=i+1; j<=mxN; ++j) {
    dp[i+1][j]=(dp[i][j-i-1]+dp[i+1][j-i-1])%M;
  }
}

      (The above snippet is from your submission)

      While I can observe that the above loop computes dp[k][n] as mentioned in the last line of your comment, I still miss the intuitive for the recurrence in the code.

      What would it be in words? or intuitively?

      I tried putting it in words, but it does feel a little odd.

      (# of k element subsets having sum n) = (# of k-1 element subsets having sum n-k) + (# of k element subset having sum n-k)

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

        From $$$dp[i][j]$$$ you can either go to $$$dp[i][j + i]$$$ which means increase every element by 1, or you can go to $$$dp[i + 1][j + i + 1]$$$ which is add a new element that's equal to 0, then increase every element by 1

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

    http://mathworld.wolfram.com/PartitionFunctionQ.html

    Study here how to do distinct partition of any integer n in sqrt(n) time.... then the recursion is ans[n] = ans[n-1] + 2^(n-1) — (number of ways to write all numbers <=n as a sum of distinct integers)

    → Reply