Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

chemthan's blog

Invitation to CodeChef June Lunchtime 2020

By chemthan, history, 4 years ago, In English

We invite you to participate in CodeChef’s June Lunchtime, this Saturday, 27th June, from 7:30 pm to 10:30 pm IST.

3 hours, 5 problems.

We will also be hosting a live problem discussion sessions where our panelist, RestingRajarshi will discuss the Lunchtime problems on 28th June 4 pm to 6 pm IST. Find more details here.

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. Joining me on the problem setting panel are:

Setters: Shubham Codebuddy1903 Khandelwal, Nghia Pham ngfam
Admin : Teja teja349 Vardhan Reddy
Tester: Nguyen Ngoc chemthan Trung
Editorialist: Taranpreet taran_1407 Singh
Post-Contest Streaming: Rajarshi RestingRajarshi Basu
Statement Verifier: Jakub Xellos Safin
Mandarin Translator: Gedi gediiiiiii Zheng
Vietnamese Translator: Team VNOI
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Mohammad solaimanope Solaiman
Hindi Translator: Akash Shrivastava

Prizes:

Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

Full text and comments »

chemthan
4 years ago
0

Codeforces Round #604 Editorial

By chemthan, history, 5 years ago, In English

Tutorial is loading...

Python Solution

T = int(input())
for tc in range(T):
    s = [c for c in input()]
    n = len(s)
    i = 0
    while (i < n):
        if (s[i] == '?'):
            prv = 'd' if i == 0 else s[i - 1]
            nxt = 'e' if i + 1 >= n else s[i + 1]
            for x in ['a', 'b', 'c']:
                if (x != prv) and (x != nxt):
                    s[i] = x
                    break
        else:
            i += 1
           
    ok = True 
    for i in range(n - 1):
        if (s[i] == s[i + 1]):
            print("-1")
            ok = False
            break
    if (ok == True):  
        print("".join(s))

Author: isaf27, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 239;

int n, p[M], x;

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        p[x - 1] = i;
    }
    int l = n;
    int r = 0;
    string ans = "";
    for (int i = 0; i < n; i++)
    {
        l = min(l, p[i]);
        r = max(r, p[i]);
        if (r - l == i)
            ans += '1';
        else
            ans += '0';
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Author: isaf27, prepare isaf27

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        map<int,int> c;
        forn(i, n) {
            int pi;
            cin >> pi;
            c[-pi]++;
        }
        vector<int> pp;
        for (auto p: c)
            pp.push_back(p.second);
        bool ok = false;
        int g = pp[0];
        int i = 1;
        int s = 0;
        while (s <= g && i < pp.size())
            s += pp[i++];
        if (g < s) {
           int b = 0;
           while (b <= g && i < pp.size())
               b += pp[i++];
           while (i < pp.size() && g + s + b + pp[i] <= n / 2)
               b += pp[i++];
           if (g < b && g + s + b <= n / 2) {
               ok = true;
               cout << g << " " << s << " " << b << endl;
           }
        }
        if (!ok)
            cout << 0 << " " << 0 << " " << 0 << endl;
    }
}

Author: MikeMirzayanov, prepare MikeMirzayanov

Tutorial is loading...

C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    map<int, int> hs;
    cin >> hs[0] >> hs[1] >> hs[2] >> hs[3];
    int total = hs[0] + hs[1] + hs[2] + hs[3];
    for (int st = 0; st < 4; st++) if (hs[st]) {
        vector<int> res;
        auto ths = hs;
        ths[st]--;
        res.push_back(st);
        int last = st;
        for (int i = 0; i < total - 1; i++) {
            if (ths[last - 1]) {
                ths[last - 1]--;
                res.push_back(last - 1);
                last--;
            }
            else if (ths[last + 1]) {
                ths[last + 1]--;
                res.push_back(last + 1);
                last++;
            }
            else {
                break;
            }
        }
        if ((int) res.size() == total) {
            cout << "YES\n";
            for (int i = 0; i < (int) res.size(); i++) {
                cout << res[i] << " \n"[i == (int) res.size() - 1];
            }
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}

Author: laoriu, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...

C++ Solution

#include <bits/stdc++.h>
using namespace std;

const int MOD = 119 << 23 | 1;

int inv(int a) {
    int r = 1, t = a, k = MOD - 2;
    while (k) {
        if (k & 1) r = (long long) r * t % MOD;
        t = (long long) t * t % MOD;
        k >>= 1;
    }
    return r;
}

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD;
    int a = 1, b = 0;
    for (int i = 0; i < n; i++) {
        a = (long long) a * inv(p[i]) % MOD;
        b = (long long) b * inv(p[i]) % MOD;
        a = (a + (long long) (p[i] - 1) * inv(p[i])) % MOD;
        b = (b - inv(p[i]) + MOD) % MOD;
    }
    cout <<  (long long) (MOD - b) * inv(a) % MOD << "\n";
    return 0;
}

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...

C++ Solution

#include <bits/stdc++.h>
using namespace std;

const int MOD = 119 << 23 | 1;

int fpow(int a, int k) {
    int r = 1, t = a;
    while (k) {
        if (k & 1) r = (long long) r * t % MOD;
        t = (long long) t * t % MOD;
        k >>= 1;
    }
    return r;
}

int main() {
    string s; cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n));
    vector<int> f(n + 1);
    for (int i = 0; i < n; i++) {
        f[i + 1] = f[i];
        f[i + 1] += s[i] == '?';
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] != '(') {
                dp[i][j] += dp[i + 1][j];
                dp[i][j] %= MOD;
            }
            if (s[j] != ')') {
                dp[i][j] += dp[i][j - 1];
                dp[i][j] %= MOD;
            }
            if (s[i] != '(' && s[j] != ')') {
                dp[i][j] -= dp[i + 1][j - 1];
                dp[i][j] += MOD;
                dp[i][j] %= MOD;
            }
            if (s[i] != ')' && s[j] != '(') {
                dp[i][j] += dp[i + 1][j - 1];
                dp[i][j] %= MOD;
                dp[i][j] += fpow(2, f[j] - f[i + 1]);
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[0][n - 1] << "\n";
    return 0;
}

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...

C++ Solution

#include <bits/stdc++.h>
using namespace std;

const int MOD = 119 << 23 | 1;

struct node_t {
    int prd;
    int val;
    node_t() {
        prd = val = 0;
    }
};

node_t operator + (node_t a, node_t b) {
    if (!a.prd) return b;
    if (!b.prd) return a;
    node_t c;
    c.prd = (long long) a.prd * b.prd % MOD;
    c.val = (long long) a.val * b.prd % MOD;
    c.val = (c.val + b.val) % MOD;
    return c;
}

int inv(int a) {
    int r = 1, t = a, k = MOD - 2;
    while (k) {
        if (k & 1) r = (long long) r * t % MOD;
        t = (long long) t * t % MOD;
        k >>= 1;
    }
    return r;
}

int main() {
    int n, q; cin >> n >> q;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD;
    vector<node_t> st(n << 2);
    auto upd = [&] (int p, node_t val) {
        for (st[p += n] = val; 1 < p; ) p >>= 1, st[p] = st[p << 1] + st[p << 1 | 1];
    };
    auto query = [&] (int l, int r) {
        node_t lres, rres;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                lres = lres + st[l++];
            }
            if (r & 1) {
                rres = st[--r] + rres;
            }
        }
        return (lres + rres).val;
    };
    for (int i = 0; i < n; i++) {
        node_t c;
        c.val = c.prd = inv(p[i]);
        upd(i, c);
    }
    set<int> ss;
    ss.insert(0);
    int res = query(0, n - 1);
    for (int i = 0; i < q; i++) {
        string op; int u; cin >> u; u--;
        auto it = ss.lower_bound(u);
        if (it == ss.end() || *it != u) {
            it = ss.insert(u).first;
            int lo = *(--it);
            it++;
            int hi = n;
            if (++it != ss.end()) {
                hi = *it;
            }
            res -= query(lo, hi - 1);
            res += MOD;
            res %= MOD;
            res += query(lo, u - 1);
            res %= MOD;
            res += query(u, hi - 1);
            res %= MOD;
        }
        else {
            int lo = *(--it);
            it++;
            int hi = n;
            if (++it != ss.end()) {
                hi = *it;
            }
            res += query(lo, hi - 1);
            res %= MOD;
            res -= query(lo, u - 1);
            res += MOD;
            res %= MOD;
            res -= query(u, hi - 1);
            res += MOD;
            res %= MOD;
            ss.erase(u);
        }
        cout << res << "\n";
    }
    return 0;
}

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...

C++ Solution

#include <bits/stdc++.h>
using namespace std;

const int MOD = 119 << 23 | 1;

int inv(int a) {
    int r = 1, t = a, k = MOD - 2;
    while (k) {
        if (k & 1) r = (long long) r * t % MOD;
        t = (long long) t * t % MOD;
        k >>= 1;
    }
    return r;
}

int main() {
    string s; cin >> s;
    int k = s.size() + 1;
    int a = 0, b = 0, c = 0, d = 0;
    for (char e : s) {
        if (e == ')') {
            b++;
        }
        if (e == '?') {
            d++;
        }
    }
    map<int, vector<int>> dps;
    auto calc = [&] (int a, int b, int c, int d) {
        int x = b + d - a;
        if (x < 0) return 0;
        int k = c + d;
        if (k < x) x = k;
        if (dps.count(k)) return dps[k][x];
        auto& dp = dps[k];
        dp.resize(k + 1);
        int t = 0, w = 1;
        for (int i = 0; i <= k; i++) {
            t += w;
            t %= MOD;
            dp[i] = t;
            w = (long long) w * (c + d - i) % MOD;
            w = (long long) w * inv(i + 1) % MOD;
        }
        return dp[x];
    };
    int res = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        char e = s[i];
        if (e == '(') {
            a++;
        }
        if (e == ')') {
            b--;
        }
        if (e == '?') {
            c++;
            d--;
        }
        if (e == '(') {
            res += calc(a, b, c, d);
            res %= MOD;
        }
        else if (e == '?') {
            a++, c--;
            res += calc(a, b, c, d);
            res %= MOD;
            a--, c++;
        }
    }
    cout << res << "\n";
    return 0;
}

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...

C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<int> d(n);
    vector<vector<int>> g(n, vector<int>(n));
    vector<vector<int>> f(n, vector<int>(n, 1));
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--, v--;
        d[u]++;
        g[u][v] = 1, g[v][u] = 2;
        f[u][v] = f[v][u] = 0;
    }
    priority_queue<pair<int, int>> heap;
    for (int i = 0; i < n; i++) {
        if (d[i] < n - 1) {
            heap.push({-d[i], i});
        }
    }
    while (!heap.empty()) {
        int u = heap.top().second;
        heap.pop();
        queue<int> que;
        vector<int> vis(n), from(n);
        que.push(u), vis[u] = 1;
        int id = -1;
        while (!que.empty()) {
            int v = que.front(); que.pop();
            int found = 0;
            for (int w = 0; w < n; w++) if (w != v && !g[v][w]) {
                found = 1;
                break;
            }
            if (found) {
                id = v;
                break;
            }
            for (int w = 0; w < n; w++) if (!vis[w] && g[v][w] == 2 && f[v][w] == 1) {
                que.push(w), vis[w] = 1;
                from[w] = v;
            }
        }
        if (id == -1) {
            continue;
        }
        for (int v = 0; v < n; v++) if (v != id && !g[id][v]) {
            g[id][v] = 1, g[v][id] = 2;
            break;
        }
        while (id != u) {
            int nid = from[id];
            swap(g[id][nid], g[nid][id]);
            id = nid;
        }
        d[u]++;
        if (d[u] < n - 1) {
            heap.push({-d[u], u});
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                cout << 0;
            }
            else {
                cout << 2 - g[i][j];
            }
        }
        cout << "\n";
    }
    return 0;
}

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Another cool problem: WEICOM.

Tutorial is loading...

Python Solution

n,a,d=map(int,input().split())
print(368131125*a%10**9*12*10**9+1,368131125*d%10**9*12*10**9)

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Bonus: another beautiful problem.

Full text and comments »

Tutorial of Codeforces Round 604 (Div. 2)

chemthan
5 years ago
56

Codeforces Round #604 (div1 & div2)

By chemthan, 5 years ago, In English

Hello everyone!

I am glad to invite you to Codeforces Round #604, which will take place on 05.12.2019 17:35 (Московское время). The round will be rated for both divisions.

Exactly 300 Codeforces rounds passed since my first one (Round 304). I have learned a lot of things here and have much fun in participating in the competitions. Now, I want to contribute to this community by proposing some problems. I hope that you will find something interesting in solving them.

The contest is prepared by me, laoriu, I_love_Hoang_Yen, coordinator isaf27 and CF admin MikeMirzayanov. As usually, we must specially thank to below people who make contest possible:

MikeMirzayanov for the powerful Polygon and Codeforces system.
isaf27 for coordinating the round.
Um_nik, arsijo, _overrated_, kocko, UselessDev for testing the round.

There will be roughly 6 problems in each division. Scoring will be announced later.

GL & HF! See you on the scoreboard.

UPD 1: Scoring

D1: 500 1000 1500 (1000+1000) 2250 3000.
D2: 500 1000 1500 2000 2000 2500.

UPD 2: Thanks for participating! Congratulations to the winners!

Top 5 Div1:

jqdai0815 (unexpected solve all problems quickly)
tourist
Radewoosh
tzuyu_chou
ksun48

Top 5 Div2:

UPD 3: Sorry for delay, this is editorial.

Full text and comments »

Announcement of Codeforces Round 604 (Div. 1)

Announcement of Codeforces Round 604 (Div. 2)

+362

chemthan
5 years ago
290

Invitation to HackerEarth February Circuits '19

By chemthan, history, 6 years ago, In English

Hello everyone!

I would like to invite you to participate in February Circuits '19. It's a long contest that will start on Feb 15, 9:00 PM IST (check you timezone). Contest will run for 9 days.

The problem set consists of 7 traditional algorithmic tasks of various difficulties and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm the tester and Alpha_Q, aminul, Apptica is the setters. I would like to thank HackerEarth admin panel, without them we do not have such contests. Below is the detail of problem set:

Day-0: Easy, Easy-medium, Approximate.
Day-2: Easy-Medium, Medium.
Day-4: Medium, Medium-hard.
Day-6: Hard.

As usual, there will be some nice prizes for the top five competitors:

First place: $100 Amazon gift card + HE t-shirt.
Second place: $75 Amazon gift card + HE t-shirt.
Third place: $50 Amazon gift card + HE t-shirt.
Fourth place: HE t-shirt.
Fifth place: HE t-shirt.

Hope to see you at the scoreboard! GL & HF.

UPD: Congratulations to the winners

Full text and comments »

chemthan
6 years ago
4

Invitation to January Easy '19 on HackerEarth

By chemthan, history, 6 years ago, In English

Hello Codeforces community,

Since my contribution is gradually decreasing, it is time to stop it :)

I would like to invite you to join HackerEarth's January Easy '19 which will start at 15:30 UTC, January 6, 2019.

The problems are prepared by aashrayagarwal, kingofbugs and me and tested by zscoder. I hope you'll find the problemset to be interesting.

You will be given 5 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners (i.e. programmers with a rating of 1600 or less before the challenge starts).

First place: $75 Amazon gift card.
Second place: $50 Amazon gift card.
Third place: $25 Amazon gift card.

Good luck & have fun!

Full text and comments »

jan, easy, hackerearth

chemthan
6 years ago
0

Invitation to HackerEarth July Circuits '18

By chemthan, history, 6 years ago, In English

Hello everyone!

I would like to invite you to participate in July Circuits '18. It's a long contest that will start on Jul 20, 9:00 PM IST (check you timezone). Contest will run for 9 days.

I'm the setter and Lewin is the tester. I would like to thank HackerEarth admin panel, without them we do not have such contests. Below is the detail of problem set:

Day-0: Very-Easy, Easy-medium, Approximate.
Day-2: Medium, Medium-hard.
Day-4: Medium-hard, Hard.
Day-6: Hard.

As usual, there will be some nice prizes for the top five competitors:

First place: $100 Amazon gift card + HE t-shirt.
Second place: $75 Amazon gift card + HE t-shirt.
Third place: $50 Amazon gift card + HE t-shirt.
Fourth place: HE t-shirt.
Fifth place: HE t-shirt.

Hope to see you at the scoreboard! GL & HF.

Full text and comments »

chemthan
6 years ago
0

Invitation to HackerEarth April Circuits '18

By chemthan, history, 7 years ago, In English

Hello everyone!

I would like to invite you to participate in April Circuits '18. It's a long contest that will start on Apr 21, 9:00 PM IST (check you timezone). Contest will run for 9 days.

I'm the tester and webmaster is the setter. I would like to thank HackerEarth admin panel, without them we do not have such contests. Below is the detail of problem set:

Day-0: Easy, Easy-medium, Approximate.
Day-2: Easy-Medium, Medium.
Day-4: Medium, Medium-hard.
Day-6: Hard.

As usual, there will be some nice prizes for the top five competitors:

First place: $100 Amazon gift card + HE t-shirt.
Second place: $75 Amazon gift card + HE t-shirt.
Third place: $50 Amazon gift card + HE t-shirt.
Fourth place: HE t-shirt.
Fifth place: HE t-shirt.

Hope to see you at the scoreboard! GL & HF.

Full text and comments »

chemthan
7 years ago
2

Invitation to CodeChef December Cook-Off 2017!

By chemthan, history, 7 years ago, In English

Hello CodeForces Community!

To keep the coding clock ticking, we have some interesting challenges in the upcoming December Cook-Off. Joining me on the problem setting panel are:

Problem Setter: chemthan (Trung Nguyen)
Tester: kingofnumbers (Hasan Jaddouh)
Editorialist: likecs (Bhuvnesh Jain)
Admin: kingofnumbers (Hasan Jaddouh)
Statement Verifier: Xellos (Jakub Safin)
Russian Translator: CherryTree (Sergey Kulik)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team

All statements are short and clear. I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 24th December 2017 (2130 hrs) to 25th December 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/COOK89

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:

Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

Full text and comments »

codechef, cook-off, dec 17

chemthan
7 years ago
17