Invitation to CodeChef Starters 161 (Rated for All)

№	Пользователь	Рейтинг
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

№	Пользователь	Вклад
1	Qingyu	157
2	maspy	150
3	nik_exists	147
4	Um_nik	145
5	Errichto	139
6	adamant	136
7	maroonrk	134
8	DNR	132
8	AmShZ	132
8	BledDest	132

We invite you to participate in CodeChef’s Starters 161, this Wednesday, 20th November, rated for all. The contest duration will be 2.5 hours.

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

Joining us on the problem setting panel are:

Contest Admin, Statement Verifier and Text Editorialist: Nishank IceKnight1093 Suresh
Tester: Takuki tabr Kurokawa
Setters: Nishank IceKnight1093 Suresh, Cozma tibinyte2006 Tiberiu-Stefan, KaiSuoShuTong.

Special thanks to satyam343 for discussing several problem ideas with me.

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.

Problem Distribution:

Division 1: 7 problems, one is a subtask
Division 2: 7 problems
Division 3: 8 problems
Division 4: 8 problems

Hope to see you participating.
Good luck!

Congrats to the top 5 in Div. 1!

potato167
noimi
SSerxhs
risujiroh (only participant to solve "Easy Constructive Problem"!)
RNS_JK

int n; vector<int> a; int N = 3*1e5+1; int dp[4][300005]; int rec(int prev, int i){ if(i >= n - 1) return a[n - 1]; if(dp[prev][i] != -1) return dp[prev][i]; int ans = INF; if(prev + a[i + 1] == 4){ ans = min(ans, 4 - a[i] + rec(4 - a[i], i + 1)); } ans = min(ans, a[i] + rec(a[i], i + 1)); // dbg(ans); return dp[prev][i] = ans; } void solve() { cin >> n; a.resize(n); for (int i = 0; i < n; ++i) cin >> a[i]; memset(dp, -1, sizeof(dp)); cout << a[0] + rec(a[0], 1) << "\n"; }

Комментарии (17)

Показать архивные | Написать комментарий?

tibinyte2006

22 месяца назад, скрыть # |

+51

My problem was proposed on 21 Jan 2022.

→ Ответить

drexdelta

Finally,

Is It RATED ?!

SanathK

Hopefully not a Math Chef today:)

nilesh8757

+13

Reminder: The contest starts in 30 minutes.

physics0523

+10

I struggled with ONETOTHREE during the contest and wondered why so many participants get AC with this problem, but after the contest, I noticed and was amazed that the following scheme is valid.

Spoiler

for(int i=2;i<n;i++){
  if(a[i-1]+a[i+1]==4){
    a[i]=min(a[i],4-a[i]);
  }
}
for(int i=n-1;i>=2;i--){
  if(a[i-1]+a[i+1]==4){
    a[i]=min(a[i],4-a[i]);
  }
}

RoomTemperatureIQ

22 месяца назад, скрыть # ^ |

← Rev. 2 →

We can actually prove it by proving that we can never merge islands of 3's. (2's are fixed). I got 1e9+7 WAs before noticing that we have to run the loop backwards as well for smth like 233312 😭

itsraajjjuuuu

damn I almost thought something like this going forward then backward but didnt try

IceKnight1093

+20

When I came up with the problem, I had a more complicated casework-y solution, and only later realized that the simple greedy implementation is actually correct.

I was not sure how guessable this was so I briefly considered modifying the problem to ask for the answer for every prefix or something like that, but after discussing with the tester we decided it's fine to keep it as-is, since for the most part I feel like if you're able to think of this algorithm then it's not too hard to prove it either. (Also it makes for a simple implementation which is always nice.)

I did make sure to modify the samples so that just iterating forward would pass them though :) (you're welcome RoomTemperatureIQ)

What is the time Complexity of this ? I got TLE , is it (4*N)?

DeadMan69

You are reinitializing it to dp[4][300005] in each testcase , which prolly gives the TLE, even if you don't get TLE , you will get WA, since this would not consider the cases that the backward iteration considers in the AC solution.

Ramen

It was nice and tricky contest..

hxu10

Good to see that I finally get 7 stars after this contest. My profile

MathModel

Congrats hxu10 on being red !

LearningMachine

+17

Thanks for the contest. QUICKEXIT was such a beautiful problem!

The Constraints of QUICKEXIT made me think that I had to do it in O(N2) and my O(N) solution was missing something. ;-;

beaaaan

same, i thought that my greedy solution was missing something and did not end up implementing it

Krrishchanchal

Codechef taught me to see constraints and reject solutions not accept it. Actually the harder version had an O(n^2) solution so they didnt change the constraints here too.

PS: It will be weird to have light constraints in harder version lol

Блог пользователя IceKnight1093