IceKnight1093's blog

Invitation to CodeChef Starters 161 (Rated for All) — 20th November
By IceKnight1093, 5 weeks ago, In English

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:

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!

  1. potato167

  2. noimi

  3. SSerxhs

  4. risujiroh (only participant to solve "Easy Constructive Problem"!)

  5. RNS_JK

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

»
5 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

My problem was proposed on 21 Jan 2022.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally,

Is It RATED ?!
→ Reply
»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Hopefully not a Math Chef today:)

→ Reply
»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Reminder: The contest starts in 30 minutes.

→ Reply
»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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
→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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 😭

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

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

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

    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)

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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";
}
→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I assume you're doing "memset" for each case?

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

    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.

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was nice and tricky contest..

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

those who solved the minmaxsubarray problem what were their ideas for proving answer at max can be min/max(P1,PN) depending on parity ?

→ Reply