Invitation to CodeChef Starters 134 (Rated till 6-Stars)

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	158
2	adamant	152
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

We invite you to participate in CodeChef’s Starters134, this Wednesday, 15th May, rated for till 6-Stars(ie. for users with rating < 2500).

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

One of the problems of this contest was also used in Code Mania Blitz, ancc IITD contest, so if you participated in that contest, please refrain from participating.

Joining us on the problem setting panel are:

Setters: Yash yash_daga Daga, Sezal sezal Mittal, Ronit ro27 Bhatt, Ram Gopal grayhathacker Pandey, Abid chroot_ Hasan, Harsh harsh__h, Sayantan das_sayantan Das.

Tester: Mridul MridulAhi Ahi.
Text Editorialists:Nishank IceKnight1093 Suresh.
Statement Verifier: Nishank IceKnight1093 Suresh.
Contest Admin : Yash yash_daga Daga.

Note: Some problems have subtasks

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. Hope to see you participating.

Good Luck!

Comments (15)

Write comment?

Little_Bunny

2 years ago, hide # |

-8

C++23 when

→ Reply

aryanc403

+22

My post contest discussion stream where I will discuss all the problems

nika-skybytska

+18

How on earth have so many people solved COUNTRBS? My solution is to notice that at most one good RBS starts at each position (namely, it ends at the next occurrence of the same prefix sum if all prefix sums in between are greater) and hash all O(n) substrings, but I think the observation part is too hard for most 5* coders.

jeroenodb

2 years ago, hide # ^ |

I think it's scoreboard effect and the fact that you don't need to think about prefix sums. Simply find matching brackets in the string (as the string itself is a regular bracket sequence), and use your favourite way to compare two substrings.

alpha1215

why WA in 3in1out

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

struct fenwick {
    vector<i64> bit;
    int n;
    fenwick(int sz) {
        n = sz;
        bit.resize(sz);
    }
    void upd(int i, i64 d) {
        while(i < n) {
            bit[i] += d;
            i |= (i + 1);
        }
    }
    void build(vector<i64>& A) {
        for(int i = 0; i < n; i++) {
            upd(i, A[i]);
        }
    }
    i64 sum(int r) {
        i64 ans = 0;
        while(r >= 0) {
            ans += bit[r];
            r = (r & (r + 1)) - 1;
        }
        return ans;
    }
    i64 get_sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

void solve(int t) {
    // cout << "test #" << t << << nl;
    int n, q; cin >> n >> q;
    vector<i64> A(n);
    i64 tot = 0;
    for(auto& a : A) cin >> a, tot += a;
    map<i64, vector<int>> idx;
    vector<i64> aux = A;
    sort(aux.begin(), aux.end());
    for(int i = 0; i < n; i++) {
        idx[aux[i]].push_back(i);
    }
    fenwick fen(n), cnt(n);
    for(int i = 0; i < n; i++) fen.upd(i, aux[i]);
    for(int i = 0; i < n; i++) cnt.upd(i, 1);
    auto ask = [&](int x) -> int {
        int s = 0, e = n - 1;
        int ans = 0;
        while(s <= e) {
            int mid = (s + e) >> 1;
            int cur = cnt.sum(mid);
            if(cur <= x) {
                ans = mid; s = mid + 1;
            } else e = mid - 1;
        }
        return ans;
    };
    vector<i64> ans(n);
    for(int i = n - 1; i >= 0; i--) {
        if(i % 2 == 0) {
            int j = ask(i / 2);
            ans[i] = tot - (2LL * fen.sum(j));
        }
        tot -= A[i];
        cnt.upd(idx[A[i]].back(), -1);
        fen.upd(idx[A[i]].back(), -A[i]);
        idx[A[i]].pop_back();
    }
    while(q--) {
        int k; cin >> k; 
        cout << ans[--k] << " ";
    }
    cout << nl;
} 

int main() {
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

AshnuB

Boring Contest ever

pikachu1010

Very bad contest, question were some variation of standard problems. ( div2B or div2C)

Also there is issue with cc contest timer, i had 7 minutes remaining acc. to timer but when i submit my code it displayed time over.

this happend multiple times, resulting in me losing rank.

please fix it :(

rainbowtable

why there is only one sample case. If you are so insecure of people guessing the solution by looking at test cases than why create such guessable problems

harsh__h

In case you are talking about Permutation Cycle Queries.

My Opinion

redcircle

In PRISON it should be made more clear what to output when there are no prisoners or guarenteed that there is at lease one prisoner. I chose some random negative values and got WA first.

kavorka

+21

Great Problemset. I learned alot.

IAWNMW

3outin1 had me..loved this one

Think_Only_Once

← Rev. 2 →

What a creativity in writing countRBS problem, really awesome. I mean doable with both string hashing and tree hashing

cod3_trav3ll3r

5 weeks ago, hide # |

are these both questions same?

https://mirror.codeforces.com/contest/1926/problem/C && https://www.codechef.com/problems/OG

this is accepted in codechef

ll n; cin>>n;
ll r = n%9;
ll ans = (n/9)*45;
ans+=(r*(r+1)/2);
cout<<ans<<"\n";

but same code is not working for 1st test case in CF.

yash_daga IceKnight1093

Wizardo29

5 weeks ago, hide # ^ |

those are different questions

in codechef u need to perform ops until its reduced to single digit

whereas in codeforces one u have to perform only once cause its asking sum

for eg: for 499

in cf u need to find 4+9+9=22 in cc one it will be 1+9+9=22=2+2=4

so yes they are diff questions

yash_daga's blog