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:
- Contest Admins: Jeevan JeevanJyot Jyot Singh, Utkarsh Utkarsh.25dec Gupta
- Setters: Jinlong wuhudsm Han, Utkarsh Utkarsh.25dec Gupta, Jeevan JeevanJyot Jyot Singh, Abhinav abhi_inav Gupta
- Testers: Tejas tejas10p Pandey
- Statement Verifier: Kanhaiya notsoloud1 Mohan
- Editorialists: Nishank IceKnight1093 Suresh
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!
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.
Lmao so true my rating was bumped up from 1898 to 5 stars after the rating mechanism changed without doing a single contest
Its Also Rated For Div2 According To The Website Poster.
and according to the title of this blog as well XD
Yeah its also rated for div2. Sorry there is a typo in the first line of blog. Will be corrected soon
Is Red-green grids dp / comb ?
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.
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}$$$ ?
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.
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
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.
What is your dp approach?
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
Oh no no. I thought you calculated the final answer using some dp + combinatorics. Thanks for replying tho!
You're welcome.
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
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.
In
MAXIMUM_SUM, does anyone knows why sorting vectors by their sizes gives TLE ?I used something like,
Though, I managed to pass it with some workarounds.