kingvarun's blog

By kingvarun, history, 7 days 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

»
7 days 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).

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

All the best for the contest !!

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

All the best

»
7 days ago, # |
  Vote: I like it -14 Vote: I do not like it

Legen... wait for it... DARY!

»
7 days ago, # |
  Vote: I like it -13 Vote: I do not like it

all the best bro

»
7 days 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).

»
7 days ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

.

»
7 days 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).

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

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

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

All the best !!

»
7 days 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?

  • »
    »
    7 days 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.

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

    DSA problems for all users on Codechef. All the best!!

»
7 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Looking forward to it bro . It will be a great contest as it is from one of the best colleges — IIITs .

Btw ,Is it relevant for div2 people ?

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

    Yes, it is relevant for div2 Codechef users. All the best!!

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

All the Best

»
7 days 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!)

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest rated for participants of div 2?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Contest Folks!

»
5 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Will an editorial be posted?

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

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

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

    how to implement this solution ???

»
5 days 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.

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

    In question it is clearly given that graph cannot be disconnected

    • »
      »
      »
      5 days 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 :(

    • »
      »
      »
      5 days ago, # ^ |
      Rev. 2   Vote: I like it +21 Vote: I do not like it
      • »
        »
        »
        »
        5 days 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

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

»
5 days 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.

»
5 days 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
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Its much easier to solve using PBDS.

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

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

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

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

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

    The square matrix can be considered as a square chessboard with cells of black and white colour. Initially for N being odd answer is zero as remaining n*n-2 cells will be odd which can't be covered by 1x2 tile in anyway. For N equal to even we can observe that whenever we place a tile of 1x2 on chessboard it always cover a black cell and a white cell. There is no possibility that a tile covers two black or two white cells, so we can say that if one pair of cell with opposite colours are removed then it is always possible to cover the remaining cells of chessboard by 1x2 tiles , which will cover an equal numbers of squares of each colour(black and white). Now when we know the above property we can find the pairs with colour A-B , B-C and A-C simply by counting frequency of colour A,B and C on black and white cells.

»
5 days 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.

  • »
    »
    5 days 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 )$$$

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

      Thank you very much. I got quite of insights.

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

»
4 days 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).