JeevanJyot's blog

Invitation to CodeChef October Starters 60 (Rated for Div. 2, 3 & 4) — 12th October
By JeevanJyot, 18 months ago, In English

We invite you to participate in CodeChef’s Starters 60, this Wednesday, 12th October, rated for Div 2, 3 & 4 Coders.

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all users 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 for all users for 1 day as soon as the contest ends, after which they will be available only to pro users.

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
  • +34
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
18 months ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Sir your rating system is broken. Currently the rating changes are almost negligible. Do something about it. And its very high for new people. Why do you consider number of participation in rounds a thing. It doesn't make sense.

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

    Lmao so true my rating was bumped up from 1898 to 5 stars after the rating mechanism changed without doing a single contest

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

Its Also Rated For Div2 According To The Website Poster.

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

    and according to the title of this blog as well XD

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

    Yeah its also rated for div2. Sorry there is a typo in the first line of blog. Will be corrected soon

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

Is Red-green grids dp / comb ?

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

    It's simply c(n+m-2, n-1) * c(n+m-1, (n+m-1)/2) * 2^(nm-(n+m-1)), where c(n, k) denotes n choose k. Choose a path, choose red cells in the path, and fill the rest.

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

      I used dp to precompute the number of paths from (1, 1) to (n, m). Can you explain the logic behind $$${n + m - 2}\choose{n - 1}$$$ ?

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

        We have to make an array of length n+m-2 and choose n-1 indices of 'D.' This is actually one of standard example problems for combinations.

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

        look if you want to go to (n,m) from (1,1) you always go in (n-1)+(m-1)=n+m-2 moves

        Suppose you go 3 moves for 2*3 Grid then you go right 2 times and down 1 time ,

        One possible arrangement :

        D R R

        now think how many ways you can arrange 1 D & 2 R ,and you will get to the equation

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

        You need to go n-1 steps right and m-1 steps downward which means total of m+n-2 move. So we can just choose any n-1 moves from these m+n-2 steps and move rightwards on these n-1 moves.

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

        What is your dp approach?

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

          I used a 2d-dp, where $$$dp[i][j]$$$ denotes number of paths from $$$(1, 1)$$$ to $$$(i, j)$$$.

          Transition: We can come to $$$(i, j)$$$ from $$$(i, j - 1)$$$ or $$$(i - 1, j)$$$. So, $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$

          Implementation

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

            Oh no no. I thought you calculated the final answer using some dp + combinatorics. Thanks for replying tho!

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

      bro !! I misread the problem the whole time!! I read in my mind that a valid path is a path from (1,1) to (n,m) where red & green cells will be equal in number + every cell is of different color than the previous in the path !! I made a simple problem complicated just by misunderstanding the statement

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

Red Green Grids was a great question. Nice one Utkarsh.25dec ;)
I had the non-dp solution in pen but could not implement it (so bad T-T). Great contest overall.

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

In MAXIMUM_SUM, does anyone knows why sorting vectors by their sizes gives TLE ?

I used something like,

sort(all(v), [&](auto& x, auto& y) {
    return sz(x) > sz(y);
});

Though, I managed to pass it with some workarounds.

→ Reply