Alpha_Ashwin007's blog

Invitation to participate in CodeChef Starters 110 (Rated till 5-stars) — 29th November
By Alpha_Ashwin007, history, 7 months ago, In English

Invitation to CodeChef Starters 110 (Rated till 5-stars) — 29th November

We invite you to participate in CodeChef’s Starters 110, aka Shaastra Programming Contest , conducted by Shaastra IIT Madras and sponsored by KLA+, this Wednesday, 29th November, rated till 5-stars (ie. for users with rating < 2200).

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

Register here to be eligible for the offline finals where there are prizes worth 60000 INR.

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.

Good Luck!

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is error in this https://www.codechef.com/viewsolution/1032623090 for Tom and jerry problem

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

In the problem "World Cup", any pointers as to why the following idea doesn't work?

  • Consider I take some set $$$S$$$ ($$$|S| \lt n$$$) of matches such that the shortest unused match has length $$$y$$$. Then it is clearly optimal to distribute the matches in $$$S$$$ with a gap of $$$y - \epsilon$$$ between them. Practically this means I can cover a period of $$$(|S| + 1) \cdot y - 1 + \sum_{x \in S}{h_x}$$$ days without being able to fit any match.

Since:

  1. $$$y$$$ clearly depends on selecting all matches with length $$$\lt y$$$.

  2. For a fixed $$$y$$$ and |S|, we want to maximize $$$\sum_{x \in S}{h_x}$$$ by picking the largest remaining possible values.

  • From (1) and (2), any optimal set of matches consists of a combination of the $$$i$$$ shortest matches and the $$$j$$$ longest matches.

  • So we can just iterate over the values of $$$i$$$ and $$$j$$$ and find the minimum value of $$$i + j$$$ which satisfies $$$(i + j + 1) \cdot a_{i + 1} - 1 + \sum_{x = 1}^{i}{h_i} + \sum_{x = 0}^{j - 1}{h_{n - j}} \geq H$$$.

I feel like I'm misunderstanding something key about the problem or approach.

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

    For a short while, this was the intended solution. But it doesn't work since "the j largest matches" have to satisfy another constraint, which is that the sum of all the chosen h_i should be <= H. Surprisingly, this throws a huge spanner in the works, and it is actually not true that the optimal set is a combination of some shortest and some longest matches.

    Also, why the "- 1" in the LHS?

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

      Ah, got it. If I have h = [1, 1, 3, 9, 10] and H = 15, the only optimal choice of matches is $$$[3, 10]$$$.

      Regarding the "-1", when considering the $$$|S| + 1$$$ gaps around the $$$S$$$ elements, keep in mind we can only make the gap as large as $$$y - \epsilon$$$, so the total integer length we can cover is $$$(|S| + 1 \cdot y) - 1$$$, right?

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

        The answer to this given test case should be $$$2$$$, my Greedy solution is also giving $$$2$$$ as the answer, but I am getting WA.
        Can you please tell the test case where I am getting wrong, or could point out mistake in my code.

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

        Yup, precisely. In fact, slightly generalizing the example you've given, if you have a bunch of 1s, then the problem effectively becomes a Subset Sum problem on the other elements (hand-waving a lot), which is of course NP-Complete.

        Regarding the -1. Yeah, my bad. Misread your inequality as strict.

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

        i was also doing the same now I realised why it would not work. Can u explain the sol for this problem?

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

Why in the world a $$$dp[N][2][2]$$$ solution gives TLE in tetris?

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

    You must be re-evaluating the $$$dp$$$ array inside every test case. But the answers from previous test cases can also be used.
    So just don't make the $$$dp$$$ array filled with $$$-1$$$ for every test case.
    My Submission

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

      I tried that , but instead of last as 1 to 4 , i took it as boolean if last = 4 or not,there not re-initializing my dp gave WA.

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

    There is no constraint on $$$\sum {N}$$$ over all test cases.

    At least for my $$$dp[N][2]$$$ state (lines filled, cur player), the answer is just the sum of the states $$${[L - 4][0], [L - 3][0], [L - 2][0], [L - 1][0]}$$$. So just precalculating up to $$$10^5$$$ (the max possible value of $$$k$$$) solves the issue.

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

Cant understand why this is wrong . please help ! https://www.codechef.com/viewsolution/1032506038

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

    for a = 9 and b = 5 you will output 3 but the answer is 2 9 — 2 -> 7 5 + 2 -> 7 The transfer can take both ways.

    → Reply