Dominater069's blog

Invitation to CodeChef Starters 156 (Rated upto 6 stars) — 16th October
By Dominater069, 2 months ago, In English

We invite you to participate in CodeChef’s Starters 156, this Wednesday, 16th October, rated upto 6 stars (i.e. for users with rating < 2500)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

The following is the number of problems in each division :

  • Division 1 : 5 problems
  • Division 2 : 7 problems
  • Division 3 : 7 problems
  • Division 4 : 8 problems

There are no subtasks this time.

Good Luck!

Congratulations to Top 5!

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

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

As a tester with a smol brain, I can guarantee that participating in this contest increases your brain size by $$$10$$$%

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dominater069 contests are cooked well !!

→ Reply
»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Contest starts in ~20 Minutes

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you please make someone manage the clarification tab, please?

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

I spent 30 mins in contest and solved a variation of D1B (when we want to minimize $$$\Sigma^{n}_{i=1} |B_i-C_i|$$$)...

Solution
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you sure your solution is correct?

    Let's take an example: x = 2, b = 1, 3, 6, 7, 10, 12, 14

    You d array will be -INF, 2, 3, 1, 3, 2, 2, -INF

    If you process the first 3 first, then closest one is the 1 right to it.

    The d array become -INF, 2, 2, 2, 3, 2, 2, -INF.

    Then for the other 3, you need to match with the right -INF and takes 3 operations. 4 in total. The final original array is 1, 3, 5, 7, 9, 11, 13

    But actually, if you process the second 3 first, it only takes 3 operations in total. The final original array is 2, 4, 6, 8, 10, 12, 14

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

      My bad. Now I think we can use the network flow model to solve it.

      Using your example, let's set nodes $$$0$$$ to $$$8$$$, as well as source point $$$S$$$ and sink point $$$T$$$.

      For nodes $$$i$$$ and $$$i+1 (0 \le i<8)$$$, add bidirectional edges with infinite capacity between them. Then connect edges $$$S \overset{\text{capacity=1}}{\rightarrow} 2$$$, $$$S \overset{\text{capacity=1}}{\rightarrow} 4$$$, $$$0 \overset{\text{capacity=INF}}{\rightarrow} T$$$, $$$3 \overset{\text{capacity=1}}{\rightarrow} T$$$ and $$$8 \overset{\text{capacity=INF}}{\rightarrow} T$$$. The cost of all edges is $$$1$$$. This allows us to find the MCMF.

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

    You were not supposed to minimize the sum of differences. rather you had to minimize the maximum difference.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the answer for this test case in Task Balance Difficulty

3 2

5 9 10

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Run time error on test 5: Submission. Help please.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Count Triplets

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

    Imagine that you have two fixed indexes $$$i$$$ and $$$k$$$, such that $$$i<k$$$, and you must choose $$$j$$$.

    • If $$$|a_i-a_k| < |i-k|$$$ its impossible to choose $$$j$$$, because $$$|i-k| \leq |i-j|+|j-k|$$$.
    • If $$$|a_i-a_k| = |i-k|$$$ we can choose any $$$j$$$ such that $$$i\leq j \leq k$$$.
    • Finally, if $$$|a_i-a_k| > |i-k|$$$ we have two options, $$$j<i$$$ or $$$k<j$$$. The values of the $$$j$$$'s can be found with a simple equation, checking if they can exist, because they can be a real number or out-of-bounds.

    Then we have an $$$O(n^2)$$$ solution, iterate for every pair $$$(i,k)$$$ and add the count of the possible $$$j$$$'s to the answer. For reducing the complexity remember that $$$1\leq a_i \leq 100$$$, so $$$|a_i-a_k| < 100$$$. We can iterate with $$$k$$$ being between $$$i-100$$$ and $$$i+100$$$, making the complexity $$$O(200n)$$$.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone! Can someone please help me debug why my code is wrong for the problem Balance Difficulties?

The Codechef "debug my code" feature seems to be buggy, it is showing the sample test cases as the testcases where my code is failing, which is incorrect.

Here is my submission.

Thanks for your help.

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Hi, The editorialist's PYPY code for problem Count Triplets keeps TLEing when I submit it(it checks 200 options for k). I only check for 100 options for k and mine is consistently getting accepted even though it is sometimes very close to the time limit. Maybe next time, will you consider setting a more relaxed time limit for such problems? I think this is the second time recently that something like this has happened the other one being starters 153-(XSQR problem) where someone could possibly figure out all the interesting ideas of a problem and get TLE because of slightly imperfect implementation. I and many others don't want to not be able to solve problems because of reasons like this in future.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    first time i submitted : https://www.codechef.com/viewsolution/1098982208 passes in 1.45 seconds, and the TL is 4s (2x multiplier for pypy i think)

    Please do not spread misinformation.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      also do note our c++ codes are 0.1-0.2s

      Did you know 2x TL used to be standard for quite a long time? and we gave you 10x TL here and you still complain....

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

      I am sorry, by mistake I have been submitting all my solutions in python3 instead of PYPY3 lol. Thanks for helping me figure this out. My solution passes in 0.64 seconds. But My point still stands if I try to submit in python3(Any idea why such huge difference?) but python users should always use pypy, so I guess its fine.

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

        pypy use JIT (Just-in-Time) compilation, so I guess it is faster. In general pypy performs well with a large number of arithmetic operations.

        → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My alternative, simpler solution for the MAGNET problem:

First, find a chain of length 4 (let's assume it's 1-2-3-4). We only track M1 and M2. Perform the operations in the order 3, 4, 2, 1. After that, use node 1 as the root and perform the operations in non-decreasing order of depth. We can see M1 and M2 will never be merged.

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

    Submission

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

    My alternative, more complicated solution for the MAGNET problem :

    Root at centroid, alternate between different subtrees, way of arranging elements exists because all sizes <= n / 2. Insert the centroid after the 1st element (otherwise you run into issues on very small depth graphs). Drawing and visualizing can help understand why it works

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

      My solution was pretty similar but simpler. Print all nodes in BFS order from the centroid. Resolve ties between nodes that have the same distance from centroid using their subtree sizes. That is root at centroid and if two nodes are equidistant, then print the one with lower subtree size first.

      Here's the sub : https://www.codechef.com/viewsolution/1098937685

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

    My solution for the MAGNET problem: For trees with diameter less than 3, traversal is not possible. Otherwise take any leaf node (1) and pick the node adjacent to it (2). Now do a dfs traversal from node (2) pushing all the visited nodes in order of visiting, except node (1) and node (2). At the end, push (1) and (2) to the result. It can be shown that the magnets initially at node (1) and node (2) will always be adjacent.

    Submision Link

    → Reply