Auto comment: topic has been updated by natalina (previous revision, new revision, compare).

Auto comment: topic has been updated by natalina (previous revision, new revision, compare).

RAMADAN contest starts 15:35UTC+2. Please

do not have a point of 1900 or higher in the rating. So div 2 or div 3 ?

Auto comment: topic has been updated by natalina (previous revision, new revision, compare).

why is there such a big gap (20 days) between 2 contests?? Will more contests be added in between?

UPD: Another contest added

Hopefully more contests gets added up in between.

First contest during Ramadan!

I hope the tasks will be interesting

And Good Luck for every parcipicant!

Sorry Codeforces, I have to attend night-prayer at that time. so, No contest for me for the next 30 days.

I hope to become specialist after this round.

"adventures of a restless mathematician"

Mathforces Incoming. Brace yourselves

In the last few days, why Div3 contest has been hosted so frequently than before?

exciting to become an Expert!

GL everybody :)))

I hope to solve as many problems as possible :DD

Hope reach pupil after this round

Good luck for everyone !!!!

Excited to give this contest on my birthday!!!

Expert please

I wish this contest i could improve the score ！ because i have lose four times till now

Problem E is one of the worst problems i have ever read

E has an unusual distance definition and it has not been presented in the russian version for more than half an hour

I spent more time in B than problems E and F due to my stupid mistake.

bad B, C, D, E, F, G!!!!

Binary search doesn't work for F ?

My private Screencast.. A,B,C,D,E Video Solutions here: https://www.youtube.com/watch?v=hSNp4xnn9lc

Screencast with commentary (set video quality to HD to be able to read my code)

Problem G is nice.

E seem very hard (at least for me) are there other simple solutions not involving dp with segment tree or sparse table?

Can someone explain the 4th test case in problem D.

Like how is it 2 3 5 and not 1 2 3 5?

RIP all who got WA on test 2 in F :(

I don't know which case I was missing. Can anyone debug my submission : https://mirror.codeforces.com/contest/1941/submission/250809941

Got trolled by problem F (2 wrong submissions) because (a[i] + a[i+1]) / 2 overflows int :(

Let this be a lesson to use std::midpoint... (or in Java, a[i] + (a[i+1] - a[i]) / 2)

I could only get TLA on test 3 for F, which trick was needed to reduce complexity ? FFT ?

For problem G I made a simple Dijkstra where the cost is determined by the size of a std::set which contains all the colors of the edges I've been through. Does anyone have an idea why it doesn't pass Test 3?

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

#define el '\n'
#define int int

struct edge {
    int dst{0}, c{0};
};

struct pqel {
    set<int> cost{};
    int node{0};

    bool operator<(const pqel& i) const {
        return this->cost.size() > i.cost.size();
    }
};

inline void solve()
{
    int n, m; cin >> n >> m;
    vector<edge> adj[n + 1];

    for (int i = 1; i <= m; i++) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    int b, e; cin >> b >> e;

    vector<bool> visited(n + 1);
    priority_queue<pqel> pq;
    pq.push({{}, b});

    while (!pq.empty()) {
        auto t = pq.top(); pq.pop();
        if (t.node == e) {
            cout << t.cost.size() << el;
            break;
        }
        visited[t.node] = 1;

        for (auto child : adj[t.node]) if (!visited[child.dst]) {
            set<int> s = t.cost; s.insert(child.c);
            pq.push({s, child.dst});
        }
    }
}

int32_t main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}

Excuse me guys, but who can help me find mistake in D?

My answer is different with correct answer in only one number, and I coulnd't find mistake.

Here is my code:

void solve() {
	int n, m, x;
	cin >> n >> m >> x;
	vector<int> ans;
	int r; char c;
	cin >> r >> c;
	if (c == '0') {
		ans.push_back((x + r)%n + 1);
	} else if (c == '1') {
		int frm = (x-r+n)%n;
		ans.push_back(frm + 1);
	} else if (c == '?') {
		ans.push_back((x + r)%n + 1);
		int frm = (x-r+n)%n;
		ans.push_back(frm + 1);
	}
	for (int i = 0; i < m-1; i ++) {
		cin >> r >> c;
		if (c == '0') {
			for (auto el : ans) {
				el = (el + r)%n + 1;
			}
		} else if (c == '1') {
			for (auto el : ans) {
				int frm = (el-r+n)%n + 1;
				el = frm;
			}
		} else if (c == '?') {
			vector<int> v;
			for (auto el : ans) {
				v.push_back((el + r)%n + 1);
				int frm = (el-r+n)%n + 1;
				v.push_back(frm);
			}
			ans = v;
		}
	}
	set<int> res;
	for (auto i : ans) {
		i --;
		if (i == 0) {
			res.insert(n);
		} else {
			res.insert(i);
		}
	}
	cout << len(res) << nl;
	for (auto i : res) {
		cout << i << " ";
	}
}

I will be very grateful to anyone who offers a helping hand

Can anyone give me some insights over the Solution of Problem — F Rudolf and Imbalance

Is there anyone ignore the "consecutive" in problem E like me ._.

G was a nice problem

Can't help but point out that C has more ACs than B tho..

Can't wait to become Expert!

I couldn't implement it in time, but I just wanted to make sure my strategy is correct for E.

Let row_ans[r] represent the minimum cost for some row. We can use prefix sums to calculate some contiguous row_ans and choose the minimum in O(n-k) time. The minimum will be the answer.

As for calculating row_ans[r], we use dp to calculate the minimum cost from dp[r][c] to dp[r][m]. row_ans[r] = dp[r][1].

Simmply apply dfs over dp[r][c] and check the minimum cost between dp[r][c] and dp[r][c+1], dp[r][c+2], ..., dp[r][c+d+1].

Is there anything more/wrong?

someone tell the approach of PROBLEM D

I tried F instead of E as seemed easier but failed on test2.

here's the submission (code is clean)
any help is appreciated.