T1duS399's blog

By T1duS399, history, 5 weeks 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: T1duS399 (Udit Sanghi), Farhod_Farmon (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: Fedosik (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  

»
5 weeks 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 ?

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        knighthood I got AC using priority queues.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I also used priority queues when i was getting TLE using array of Ci. But then it gave WA xD look at my code pls https://www.codechef.com/viewsolution/24061341

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You are using sort(c , c+n) in while loop. Suppose ci for all i in 109 then your code's complexity will be 30*n*nlon(n) = n2log(n).

            I hope you get it why it is getting TLE

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              sorry bro wrong code. The code is — https://www.codechef.com/viewsolution/24070549

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I didn't go in deeper but Try out that case --
                1
                2 10 10 10 10 10
                10 10
                it should be "RIP" but your codes gives 0.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  The constraints explicitly specify $$$A, B < Z$$$. So your Test Case is wrong!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  WTF :(
                  my bad i'd tried to submit during the contest and It gave WA until I included this TC. I'll try to find it why it was so

      • »
        »
        »
        »
        5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank you :)

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Use long long maybe

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I have converted int to long long using typedef already.

      • »
        »
        »
        »
        5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

»
5 weeks 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) .

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

any hints on how to solve mystery tree ?

  • »
    »
    5 weeks 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 :)