T1duS's blog

Invitation to CodeChef April Cook-Off 2019 sponsored by ShareChat!
By T1duS, history, 6 years ago, In English

Greetings Codeforces community!

You all are invited to participate in CodeChef’s April Cook-Off sponsored by ShareChat. This is a short contest with 7 problems on offer. The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

ShareChat — our contest sponsor is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Setters: T1duS (Udit Sanghi), Farhod (Farhod Khakimiyon), Kerim.K (Kerim Kochekov)
- Tester: teja349 (Teja Vardhan Reddy)
- Editorialist: adamant (Alexander Kulkov)
- Statement Verifier: Xellos (Jakub Safin)
- 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:

  • Start Date & Time: 21st April 2019 (2130 hrs) to 22nd April 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
  • Contest link: https://www.codechef.com/COOK105
  • 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/t/how-do-i-win-a-codechef-goodie/7344

(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
  • +79
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Nice and balanced problemset for Div 2. How to solve Random Game and Doubly Increasing Path ?

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

    Random Game- If n%2 == 0: n /= 2,if n%4 == 3 or n == 1: n -- else n++
    You can prove this by induction. My code —
    https://www.codechef.com/viewsolution/24063596

    DINCPATH- In edge u-v, if a[u]>a[v]: make it edge u->v with weight a[u]-a[v] and vice versa.
    Sort all the edges. Now, you can use DP[i] = max length of path ending at .
    My code

    https://www.codechef.com/viewsolution/24063652

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

      For hooli and Pied piper question, i was storing all the possible contributions values in a vector and then sorting the vector and doing binary search on the cumulative sum vector to find how many contributers we need. But this gave TLE. The storing part's time complexity is N*log(10^9). And sorting vector of above size again Nlogn. Where did i go wrong? And, if we simulate the problem using priority queue what will be the time complexity?

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

        knighthood I got AC using priority queues.

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

        I used a heap created by make_heap() The complexity is N*logn*log(10^9). In my understanding the heap operation is faster than the sorting of the array. implementation

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

        If you have a test where $$$N = 10^5$$$ and every $$$C_i = 10^9$$$, then you have $$$O(NlogC)$$$ contribution values, which is around 30 million. That's not a very friendly array size to be sorting.

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

          The question is: Is the sorting of that array slower than the 30 million insert/delete from the heap? I think it is, because the heap holds not more than N values at any time. Which means that the sorting is N log (N * 10^9). So, the array sorting is in worst case aprox 9 times slower.

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

      Thank you :)

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

      I am making an unweighted DAG from the edges and DP[i][f] denotes the longest length of sequence staring at ith node and includes the parent of ith node if f = 1 otherwise if f = 0 it does not include the parent of ith node. Can you please tell why my solution is wrong? My code

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

        Use long long maybe

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

          I have converted int to long long using typedef already.

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

        hackerwizard I don't think there will be only one parent of a node. There can be multiple parent nodes. And you will be needing all those values. I applied the same idea, First, make DAG, apply topological sorting, Iterate over all nodes in it, store the values of dp for all parent and then applying binary search and using prefix max, find the value for current children of a node. Refer to here : Solution

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

        There can be multiple parents as well as multiple children, using dp on edges makes it much easier.

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

Why does this TLE, (for DINCPATH), my soln's complexity is O((n + m)logN) .

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

    Time complexity for this problem is a bit strict IMHO. I had to get rid of the TreeMap to get it passed in the contest. You can check my submission.

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

any hints on how to solve mystery tree ?

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

    Disclaimer: I didn't solve it during the contest, I had bugs with the third problem and wasted almost 2 hour only on it D:

    Solution: It's a centroid problem.

    Insight 1: If a node is the largest in his neighborhood he is good for you. Insight 2: After querying some node, let's say U, and receiving the verdict that he has a bad neighbor (which is bigger then him), let's say V, then in the subtree of V and all his children (except U), the there exist some "good" node (the maximal one for example). Explanation for the insight: The worst case is that all node in the subtree have some neighbor which is bigger than them, but as we know that U is smaller then V, this mean that the maximum value in the subtree of V is also bigger then U, and this mean that he is bigger then all his neighbor, which mean he is "good".

    As such the algorithm is as follow: find some node in the graph, such that all his children's subtree's size are smaller then n/2. After querying him, you will either find that he is good — you win, or you might find some neighbor of his which is bigger: which mean that you can start looking only at the subtree of this node, which you know from insight 2 that contain a valid "good" node.

    As such for each step you get the size of the graph reduced by half, and by that you get that after 20 queries the size of the graph either turn 1 (which mean the node that remain is our solution), or you found along the way a good node.

    for some good explanation of the centroid method, you can read here: https://www.geeksforgeeks.org/centroid-decomposition-of-tree/

    Hope this helps :)

    → Reply