kingvarun's blog

By kingvarun, history, 3 years ago, In English

Greetings, Codeforces Community!

We invite you to participate in Logicode, this Friday, 16th October, 9:30pm on Codechef. This contest is hosted by DotSlash Community of Indian Institute of Information Technology, Nagpur.

The contest consists of 7 problems of varying difficulty and is 2.5hrs long. All problems in this round are prepared and tested by kingvarun, tejasdeore7, adarsh_sinhg, divyevilking, deo002, dracula28, ashok_karwa.

Huge thanks to : qazz625 initial review of problem ideas , mr_cruise for coordinating this round and Codechef Team for their invaluable help and great platform.

We hope you will enjoy the contest! Good Luck!

UPD : Editorials are uploaded on code chef, links are given below

MATMIN1

CHEFG999

FIZZA

FROD

AVGMED

THE SIEGE

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Problems are good. Guess,contest will also be good!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give a little more context about what do you exactly mean by "Real Life Problems". I mean aren't they usual DSA based problems? or are you talking about the background stories that are given usually in the problems?

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

    Yes,I am talking about background stories that are given in problems and also there are some DSA problems.

»
3 years ago, # |
Rev. 20   Vote: I like it 0 Vote: I do not like it

Is it at 9:30PM or 9:30AM? It may be clear for indian participants, but I guess there is no harm in being clear about time zone. (I am referring to the poster. It was the first thing I noticed on opening the blog!)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest rated for participants of div 2?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Contest Folks!

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

Will an editorial be posted?

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can someone give a proof that why pairs having different parity of (i + j) are a GoodPair?

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

    Color the grid, like a chessboard.

    Placing a domino is equivalent to mapping a black/white cell to its adjacent white/black cell.

    So, it must be clear that the count of white and black cells should be equal.

    Now, there are many constructive ways that tell us that it will always be possible to place the dominoes if we have only removed a pair of opposite-colored cells.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I am not very sure, but looking at the solutions from the leaderboard I think that the problem "SEIGE" has an incorrect solution.

It seems like all the passed solutions and even the model solution will fail on disconnected graphs.

This is the only possible reason I can think of right now as to why my assertions were failing during the contest.

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

    In question it is clearly given that graph cannot be disconnected

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hmm... I see. ̶I̶ ̶m̶u̶s̶t̶'̶v̶e̶ ̶m̶e̶s̶s̶e̶d̶ ̶u̶p̶ ̶s̶o̶m̶e̶t̶h̶i̶n̶g̶ ̶t̶h̶e̶n̶.̶

      EDIT You guys messed up :(

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +21 Vote: I do not like it
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I can explain. You actually don't check if the graph is connected, you check if you can go from some warlord to any node. But there can be $$$0$$$ warlords.

        Here are two my submissions: WA, RTE

        I got my WA during contest because of this

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

          Ohh I see, but I guess that logically $$$x = 0$$$ should imply $$$r = 0$$$, but RTE (also evident from my submission above)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak test cases as always, saw many incorrect solutions being accepted for MPOW.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem: Average Median Game

Verdict: WA

Also, the add function independetly has been tested(By getting AC in a different problem).I have tried out all possible assertions. Can someone spot the bug in the below code.

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

    Its much easier to solve using PBDS.

    AC_CODE
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I agree that the PBDS version is far easier. But I want to know why the above code failed.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problems were tough . Btw ,will editorials be published for this round, on codechef ??

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

how to implement this question solution CHEF MAKES GOOD PAIRS problem link —

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain their solution for last problem FROD ? Help Maksim1744 and others who solved it.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +9 Vote: I do not like it

    There seems to be a greedy solution, but I solved by DP because I could not handle following last type well. The complexity is $$$O(N\sqrt N)$$$.

    There are 4 types.

    • determined: e.g. NNNR, LNNNR. trivial for this case. number of 'N' with no cost.

    • unidirectional: e.g. RNNNR, LNNNNL. change first 'N' into 'L'. (number of 'N'-1) with cost 1.

    • squashed from both sides (odd): e.g. RNNNL, RNNNNNL. 1 with no cost (the middle), (number of 'N'-2) with cost 2 (e.g. RLNNRL).

    • squashed from both sides (even): e.g. RNNL, RNNNNL. 1 with cost 1 (e.g. RRNL), (number of 'N'-2) with cost 2.

    For each type, distinct values of "number of 'N'" is $$$O(\sqrt N)$$$ and each transition is represented simply.

    Transition for second type: $$$(0, c, 2c, 3c, \ldots )$$$ This translation can be handled by an deque.

    for third type is similar.

    for last type: $$$(0, 1, c, c+1, 2c, 2c+1, \ldots )$$$ This can be handled by splitting into $$$(0, -\infty, c, -\infty, 2c, \ldots )$$$ and $$$(-\infty, 1, -\infty, c+1, -\infty, 2c+1, \ldots )$$$

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

      Thank you very much. I got quite of insights.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      I did something similar, but I split last type into two more: either we have length two or more. If we have length two, then $$$(N-2)$$$ with cost 2 is useless, because it will be zero, so it's just $$$1$$$ with cost 1. If we have length at least 4, then it is indeed either 1 with cost 1, or $$$N-2$$$ with cost 2. And here is the idea: we don't need to use more than one of (1 with cost 1) of this type. This is because if we have at least two, we can instead use only one with cost 2, and we also will have one more unused segment. Also, if we use some (1 with cost 1), it should be the shortest one.

      So we will have to consider two cases: either we use one of that type or not. After that, we are left with some segments of cost 2 and some segments of cost 1. It's easy to count maximum now: sort values of each cost in descending order, calculate prefix sums and the result is $$$max(sum2[i] + sum1[k - i \cdot 2])$$$

      P.S.: In the third case it is 1 already and $$$N-3$$$ with cost 2, so there is no choice either

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).