teja349's blog

Invitation to the CodeChef November Cook-Off 2018!
By teja349, history, 6 years ago, In English

Hello CodeForces Community!

We are happy to extend our invitation to the November Cook-Off 2018 sponsored by ShareChat, a 2.5 hour test of your coding skills. As this is the 100th iteration of the contest, we have some additional exciting rewards for the contestants, which you can check out on the contest page.

There’s another reason to compete. ShareChat, the sponsor of November Cook-Off, is offering full-time job opportunities for programmers across the globe. More details about the additional rewards and job opportunities can be found on the contest page.

The contest problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese. Joining me this time on the problem setting panel are:

Setter: PraveenDhinwa (Praveen Dhinwa)

Tester: teja349 (Teja Vardhan Reddy)

Statement verifier: Xellos (Jakub Safin)

Editorialist: taran_1407 (Taranpreet Singh)

Mandarin Translator: huzecong (Hu Zecong)

Vietnamese Translator: Team VNOI

Russian Translator: Mediocrity (Fedor Korobeinikov)

Bengali Translator: solaimanope (Mohammad Solaiman)

Hindi Translator: Akash Shrivastava

Contest Details:

Time: 18th November 2018 (2130 hrs) to 19th November 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

Contest link: https://www.codechef.com/COOK100

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 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

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

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

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

It should be 18th November in contest details.

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

Clashing with Technocup :(

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

CodeChef:- We're giving laddus to top 100 performers.

Me:-

cccc

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

Good thing I choose cook off instead of cf round xd

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

How to solve ABGAME?

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

    First notice that it's basically a NIM game plus you have some heaps that are either A's or B's, let's denote |A| and |B| as the number of stones in heaps that are owned by only A and B respectively. If |A| > |B| A can always win, if |A| < |B| B can always win (these are easy to see), otherwise if |A| = |B| it's a standard NIM game.

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

      Ohh..got my mistake..thanks for the explanation. :)

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

How to solve 4th and 5th problem?

for 5th I was trying to make minimum vertex cover, but there were O(n^2) edges and O(n) vertices, was it using segment tree like structure to reduce edges to O(nlogn)? like in bubble cup

For 4th, I did something without much proving, but couldn't find a counter case,

basically, I observed a pattern in the continuous ranges

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

    Here's my solution for 4th:

    If we try to parse the statement, it means counting the number of s, 1 ≤ s ≤ M such that and . Using the definition of ceiling function, such s needs to satisfy:

    (k - 1)oe + 1 ≤ s ≤ k × oe

    k(of - 1) + 1 ≤ s ≤ k × of.

    Note that for each k it's trivial to compute the number of satisfying s, and each such k gives a disjoint range of values. However, trying all possible k is not possible (there could be up to 109 of them) so we need to be more clever.

    There are three cases to consider here:

    1. If oe < of, then k(of - 1) + 1 ≥ k × oe + 1 > k × oe hence there are no solutions.

    2. If oe > of, then k × of < (k - 1)oe + 1 iff oe - 1 < k(oe - of), so we only need to try for k up to (oe - 1) / (oe - of) ≤ oe. Furthermore, when oe is large () we only need to try at most values of k since afterward m < (k - 1)oe + 1, so in total we need to try values of k.

    3. If oe = of, we can collapse the two inequalities into max ((k - 1)oe + 1, k(oe - 1) + 1) ≤ s ≤ k × oe or k × oe - min(k, oe) + 1 ≤ s ≤ k × oe. With that there are naturally two smaller cases: k ≤ oe where you just need to sum over all possible ranges (and using the above argument there are at most ranges), and k > oe where all possible values for s work.

    Total time complexity is per test case.

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

      You wrote two segments that you should intersect to get the answer for the chosen k. You can note that their borders are linear functions on k, so you can consider different relative positions of these segments, and for each one find the answer by formula.

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

    My solution is in . Here n = oe.

    Let f(x) = ceil(x / ceil(x / n)). The question is how many x from [1..M] satisfies f(x) = V.

    When n is big, then observe that on each of the intervals [1, n], [n + 1, 2n], ... function f is increasing. So bin-search in each of the intervals. Time: .

    When n is small, then write x = an + r and iterate over r. When r = 0 then f(x) = n. When r > 0 then we have f(x) = ceil(x / (a + 1)) and f(x) = V is giving you lower and upper bound on a.

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

For ELEPPOND, I got accepted after swapping west side with east side.

Doesn't east side mean (*,n) and west side mean (*,1)?

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

    You are right. This is such a shame. Sincere apologies from my side. Each of setter, tester, and editorialist in the panel missed it. Lesson learned, don't use directions like north, south, east, west, rather left, right, top and down would be better. The problem will be rejudged and your score will be reset to 5. Congrats on solving all the problems :)

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

In problem TREEUNAT, i was going through the solutions, and i found:

if(count of markers with value 1 > 1) ans = 1;

Can someone help me with this part ?

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

    It just means test cases are weak, i generated one such test case with 63 nodes complete binary tree having 19 markers numbered 0, 2 markets numbered 1 and 42 markers numbered 2.

    Code for generating the above test case.

    At least top 3 solutions (including mine) are failing on this test case.

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

      Thanks for clearing this.. we were trying really hard but weren't able to prove it. Thanks again :)

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

Can someone explain his approach to TREEUNAT?

→ Reply