Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
long long sum = 0;
for (int & x : a) {
scanf("%d", &x);
sum += x;
}
if (sum != 0) {
puts("YES");
puts("1");
printf("%d %d\n", 1, n);
exit(0);
}
sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
if (sum != 0) {
puts("YES");
puts("2");
printf("%d %d\n", 1, i + 1);
printf("%d %d\n", i + 2, n);
exit(0);
}
}
puts("NO");
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
char str[4][4 + 1];
// cells are '.', 'o', 'x'
for (int i = 0; i < 4; i++) {
cin >> str[i];
}
auto check = [&]() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx == 0 && dy == 0) continue;
if (i + dx * 3 > 4 || j + dy * 3 > 4 || i + dx * 3 < -1 || j + dy * 3 < -1) continue;
bool ok = true;
for (int p = 0; p < 3; p++) {
ok &= str[i + p * dx][j + p * dy] == 'x';
}
if (ok) return true;
}
}
}
}
return false;
};
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (str[i][j] == '.') {
str[i][j] = 'x';
if (check()) {
puts("YES");
exit(0);
}
str[i][j] = '.';
}
}
}
puts("NO");
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
void solve() {
int n;
cin >> n;
vector<string> names(n);
for (string& name : names) {
cin >> name;
}
sort(all(names));
auto getIdx = [&](const string& s) {
int pos = lower_bound(all(names), s) - names.begin();
if (pos == (int)names.size() || names[pos] != s) return -1;
return pos;
};
auto splitIntoUserMessage = [](const string& s) {
size_t pos = s.find(':');
assert(pos != string::npos);
return make_pair(s.substr(0, pos), s.substr(pos + 1));
};
auto splitIntoTokensOfLatinLetters = [](const string& s) {
vector<string> result;
string token;
for (char c : s) {
if (isalpha(c) || isdigit(c)) {
token += c;
}
else {
if (!token.empty()) {
result.push_back(token);
}
token.clear();
}
}
if (!token.empty()) {
result.push_back(token);
}
return result;
};
int m;
cin >> m;
vector<int> who(m);
vector<vector<char>> can(m, vector<char>(n, true));
vector<string> messages(m);
string tmp;
getline(cin, tmp);
for (int i = 0; i < m; i++) {
string cur;
getline(cin, cur);
pair<string, string> p = splitIntoUserMessage(cur);
const string& user = p.first;
const string& message = p.second;
who[i] = getIdx(user);
if (who[i] != -1) {
fill(all(can[i]), false);
can[i][who[i]] = true;
}
messages[i] = message;
vector<string> tokens = splitIntoTokensOfLatinLetters(message);
for (const string& z : tokens) {
int idx = getIdx(z);
if (idx != -1) {
can[i][idx] = false;
}
}
}
vector<vector<int>> par(m, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
if (can[0][i]) par[0][i] = 0;
}
for (int msg = 0; msg + 1 < m; msg++) {
for (int i = 0; i < n; i++) {
if (par[msg][i] == -1) continue;
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (can[msg + 1][j]) {
par[msg + 1][j] = i;
}
}
}
}
int msg = m - 1, pos = -1;
for (int i = 0; i < n; i++) {
if (par[msg][i] != -1) {
pos = i;
break;
}
}
if (pos == -1) {
cout << "Impossible\n";
return;
}
while (msg >= 0) {
who[msg] = pos;
pos = par[msg][pos];
msg--;
}
for (int i = 0; i < m; i++) {
cout << names[who[i]] << ":" << messages[i] << "\n";
}
return;
}
int main() {
//freopen("input.txt", "r", stdin);
int t;
cin >> t; // number of tests
while (t--) {
solve();
}
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int nextInt() {
int x = 0, p = 1;
char c;
do {
c = getchar();
} while (c <= 32);
if (c == '-') {
p = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * p;
}
#define all(x) (x).begin(), (x).end()
const int N = (int)3e5 + 5;
const int MAX_VAL = (int)1e9;
int n;
ll l[N], r[N];
struct event {
ll x;
int c;
event() {}
event(ll x, int c) : x(x), c(c) {}
};
pair<ll, int> check(ll len) {
if (len == 0) return make_pair(0LL, n);
static vector<event> evs;
evs.resize(0);
for (int i = 1; i <= n; i++) {
if (r[i] - len > l[i]) {
evs.push_back(event(l[i], 1));
evs.push_back(event(r[i] - len, -1));
}
}
sort(all(evs), [](const event & a, const event & b) { return a.x < b.x; });
reverse(all(evs));
int cnt = 0, maxiCnt = 0;
ll bestPos = 0;
while (evs.size() > 0) {
ll x = evs.back().x;
while (evs.size() > 0 && evs.back().x == x) {
cnt += evs.back().c;
evs.pop_back();
}
if (cnt > maxiCnt) {
maxiCnt = cnt;
bestPos = x;
}
}
return make_pair(bestPos, maxiCnt);
}
vector<int> getAns(ll len) {
if (len == 0) {
vector<int> res(n);
iota(all(res), 1);
return res;
}
ll pos = check(len).first;
vector<int> res;
for (int i = 1; i <= n; i++) {
if (pos >= l[i] && pos < r[i] - len) {
res.push_back(i);
}
}
return res;
}
int main() {
n = nextInt();
int k = nextInt();
for (int i = 1; i <= n; i++) {
l[i] = nextInt();
r[i] = nextInt() + 2;
}
ll l = 0, r = MAX_VAL + MAX_VAL + 5;
while (r - l > 1) {
ll mid = (l + r) >> 1;
if (check(mid).second >= k) l = mid;
else r = mid;
}
vector<int> ans = getAns(l);
cout << l << endl;
assert((int)ans.size() >= k);
ans.resize(k);
for (int i : ans) {
printf("%d ", i);
}
puts("");
}
Tutorial is loading...
C++ code
#include <bits/stdc++.h>
using namespace std;
const int N = (int)404;
const int ALPHA = 26;
bitset<N> b[ALPHA][N];
char patt[N][N];
bitset<N> result[N];
bitset<N> getShifted(const bitset<N>& b, int len, int shift) {
assert(0 <= shift && shift < len);
return (b >> shift) | (b << (len - shift));
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n, m, r, c;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
static char str[N];
scanf("%s", str);
for (int j = 0; j < m; j++) {
b[(int)(str[j] - 'a')][i][j] = true;
}
}
scanf("%d%d", &r, &c);
for (int i = 0; i < n; i++) {
result[i] = ~result[i];
}
for (int i = 0; i < r; i++) {
scanf("%s", patt[i]);
for (int j = 0; j < c; j++) {
if (patt[i][j] == '?') continue;
int c = patt[i][j] - 'a';
int shiftByX = (((-i) % n) + n) % n;
int shiftByY = (((j) % m) + m) % m;
for (int x = 0; x < n; x++) {
int nx = (x + shiftByX);
if (nx >= n) nx -= n;
result[nx] &= getShifted(b[c][x], m, shiftByY);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
putchar(result[i][j] ? '1' : '0');
}
puts("");
}
}
Java code
import java.io.*;
import java.util.*;
public class Main {
static class InputReader {
BufferedReader bufferedReader;
StringTokenizer stringTokenizer;
InputReader(InputStream inputStream) {
bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768);
stringTokenizer = null;
}
String next() {
while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
try {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
} catch (IOException ex) {
ex.printStackTrace();
throw new RuntimeException(ex);
}
}
return stringTokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
static int[] newBitSet(int n) {
return new int[(n + 31) / 32];
}
static void setBit(int[] a, int pos) {
a[pos >>> 5] |= (1 << (pos & 31));
}
static boolean getBit(int[] a, int pos) {
return ((a[pos >>> 5]) & (1 << (pos & 31))) != 0;
}
static void setAll(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = ~0;
}
}
static void resetAll(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = 0;
}
}
static void andXYtoX(int[] x, int[] y) {
for (int i = 0; i < x.length; i++) {
x[i] &= y[i];
}
}
static void leftShiftAndOr(int ch, int shift, int x, int[][][][] shl, int[] to) {
int[] z = shl[ch][shift & 31][x];
int delta = (shift >>> 5);
for (int i = delta; i < to.length; i++) {
to[i - delta] |= z[i];
}
}
static void rightShiftAndOr(int ch, int shift, int x, int[][][][] shr, int[] to) {
int[] z = shr[ch][shift & 31][x];
int delta = (shift >>> 5);
for (int i = 0; i + delta < to.length; i++) {
to[i + delta] |= z[i];
}
}
static void printBitset(int a[], int l, int r) {
for (int i = l; i <= r; i++) {
System.err.print(getBit(a, i) ? '1' : '0');
}
System.err.println();
}
static final int ALPHA = 26;
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = in.nextInt();
int m = in.nextInt();
int[][][][] shl = new int[ALPHA][32][n][];
int[][][][] shr = new int[ALPHA][32][n][];
for (int c = 0; c < ALPHA; c++) {
for (int sh = 0; sh < 32; sh++) {
for (int i = 0; i < n; i++) {
shl[c][sh][i] = newBitSet(m);
shr[c][sh][i] = newBitSet(m);
}
}
}
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = in.next();
for (int j = 0; j < m; j++) {
int c = s[i].charAt(j) - 'a';
for (int sh = 0; sh < 32; sh++) {
if (j - sh >= 0) {
setBit(shl[c][sh][i], j - sh);
}
if (j + sh < m) {
setBit(shr[c][sh][i], j + sh);
}
}
}
}
int r = in.nextInt();
int c = in.nextInt();
String[] patt = new String[r];
int[][] res = new int[n][];
for (int i = 0; i < n; i++) {
res[i] = newBitSet(m);
setAll(res[i]);
}
int[] tmp = newBitSet(m);
for (int i = 0; i < r; i++) {
patt[i] = in.next();
for (int j = 0; j < c; j++) {
if (patt[i].charAt(j) == '?') continue;
int cur = patt[i].charAt(j) - 'a';
int shiftByX = (((-i) % n) + n) % n;
int shiftByY = (((j) % m) + m) % m;
for (int x = 0; x < n; x++) {
int nx = x + shiftByX;
if (nx >= n) nx -= n;
resetAll(tmp);
leftShiftAndOr(cur, shiftByY, x, shl, tmp);
rightShiftAndOr(cur, m - shiftByY, x, shr, tmp);
andXYtoX(res[nx], tmp);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
out.print(getBit(res[i], j) ? '1' : '0');
}
out.println();
}
out.close();
}
}
Auto comment: topic has been translated by netman (original revision, translated revision, compare)
The fastest editorial in 2017
Another solution of problem D. We use sweep line with events {segment_start, segment_end}. When segment starts we increase arr[pos_l]++, and when segment ends we decrease arr[pos_l]--. To find the answer, we need to check the k-th left-started segment in our array, each time for every event. If we are in pos and have segments_cnt >= k, we know that each of them has end-point >= pos, so our goal is to find k longest segments and answer is pos — po_l[k-th segment]+1. To implement arr[] we can use sparse segment tree. Code
Complexity is O(NlogN + Nlog109)
PS. Is it right complexity in editorial? Should it be O(NlogN + NlogR)?
Solution in editorial has such complexity, because I sort events in every iteration of binary search. I know how to improve complexity, but it's not so important :)
better solution for D, which is too simpler and also much more straight to code. We know the period we want is min(ri)-max(li) between all of k periods we chose. So I sort all of the periods as {li,ri} and just for li I want k-1 periods before it which the min(ri) of them should be maximal possible. I have a set in which I keep k-1 maximum ri of previous periods. And the ans is for any i(1<i<=n) ans = max(ans, min(l[i].secon ,st.begin()->first ) — l[i].firs + 1); Complexity is O(NlogN) 23597706 thank you netman.
Nice :)) the best solution !
Can u elaborate on how are you going to save indexes of coupons after every iteration.
As I coded, I apply the algorithm twice. At the first one, I save the maximum intersection and then at the second one, when the answer is equal to the maximum I output the i(we are at it, now) and the elements in the set.
Wow,That was simple. I was trying to update the ans in one pass and that was giving TLE. Thanks for the answer. Good solution
It is amazing. Thank you
Can you elaborate your approach using seg. tree? I am unabble to get it.
Could you explain more about binary_search in D ?
Я решил E за O(nmr + nrc).
Для каждой клетки предподсчитаем, какие строки шаблона можно приложить начиная с этой клетки: Зафиксируем строку таблицы и строку шаблона. Возьмем конкатенацию строки шаблона и строку таблицы (последнюю возможно придется повторить насколько раз, но длина будет все равно O(m + c)). Посчитаем на ней z-функцию, только при сравнении элементов на равенство будем использовать
s[i + z[i]] == s[z[i]] || s[z[i]] == '?'. С помощью этих значений мы можем выполнить нужный предподсчет. Для всех пар это отработает за O(nr(m + c)Теперь можно перебрать все клетки и пробовать к каждой из них прикладывать начало шаблона за O(nmr)
c++
Словил вчера wa4 с той же идеей, но префикс функцией... 23605543
Строку из таблицы иногда нужно добавить больше 2-х раз. Чтобы была достаточная длина. Например, у таблицы длина 2, у шаблона 100.
z-функция работает, потому что равенство транзитивно. У вас равенство нетранзитивно.
Например, на строчке a?b вы насчитаете 0 2 1, что не является правдой.
у меня там просто 0 0 0. '?' прикладывается только к '?'. Я на контесте не вдавался в док-во корректности, так что все может быть. Это просто не первое место, где такая вещь с шаблонами проходила, а подумать над этим все время забывал.
Да, это корректный алгоритм, я точно также сдал. Но только вот есть одна проблема.
Из-за того, что z-функция может считаться неправильно для позиций, в которых записаны знаки вопроса, можно придумать тест, на котором она будет считаться за O(n2). Например, для такой строки :
a?????...?aaaaaa...a (399 вопросов, потом 800 букв a)
z-функция будет такой : 0, 0, 0, ..., 0, 800, 799, 798, ..., 1.
Т.е. во всех позициях, где записана буква a, цикл будет полностью проходить до конца строки, следовательно суммарное время работы будет как-раз O(n2).
Ну тогда на строчке a???...???aaa...aaa это квадрат?
В теории да, это квадрат. И в теории это TL. Но это работает, т.к. нужно было делать специальные тесты против решения. Т.е. в данном контесте это рабочее решение.
То, что оно получает OK, я и так вижу. Это не делает решение правильным. Такой тест сделать можно.
Уметь сдавать медленные решения — это замечательный скилл. Но это же послеконтестовая дискуссия, сейчас мы заинтересованы не в получении OK, а в красивых решениях. Вы предложили интересный метод, но он оказался плохим. Странно оправдываться словами "ну тесты же плохие, значит решение норм".
Сама z-функция может считаться неверно для подстрок с вопросами (меньше, чем нужно), но когда знаков вопроса уже нет, она считается верно (а нам это и нужно). Т.е. после последнего вопроса будут корректные значения ф-ции.
thanks for realy good problems
в Д можно еще по-другому. Отсортируем отрезки по левому концу. Переберем отрезок, левая граница которого и будет являться левой границей пересечения. Теперь из всех отрезков, левые концы к-ых не правее нас нам хочется выбрать К — 1 с наибольшими правыми концами. Корректность левых границ автоматически поддержано сортировкой(т.е. все хорошие отрезки уже рассмотрены), а чтобы выбрать максимальные К — 1 можно поддерживать сет из (К — 1) максимальных правых концов.
wrong solution!
How do you handle the wildcard character in the KMP algorithm?
Can you explain it please, because I don't think you can do this with just a KMP.
PS: Obviously one can solve the problem in O(n2 * C) where C is the cost of solving the 1D version of the problem. So it's enough if you tell your solution for the 1D problem.
so do you find the answer!? or I explain it?!
Please explain it, or provide a submission of an implementation code of it. :)
wrong solution!!!
Much clearer, please :(
wrong solution!
What is KMP for strings with '?' ?
Oh, I make a mistake about the statement....!!! sorry every one! thank you Um_nik
Loved the first problem, had to think a bit out of the box.
I don't wanna be a hater, but at problem A, by "dividing" I understood that the array should be divided in 2 or more arrays. "1.Array sum is not zero. In this case we can divide array into one subarray A[1... n]." That's not called dividing, because you are left with one single array. If I'm wrong, please correct me. Thanks for reading this and I hope I didn't waste your time.
Yes, you are wrong. As the problem statement point the dividing all of array into one array is correct.
I had some trouble debugging my implementation of Div2E editorial's solution, so I'll give some hints.
std::bitset, shifting is reversed! This means that shift(Gz, x, y) should be implemented withb>>yinstead ofb<<y. This makes sense, because the "left" shift defined in the solution brings elements from positions with larger y indexes to positions with smaller y indexes. Usingstd::bitset, or any native integral types, this is actually a right shift!b>>yis not enough. Use(b<<(m-y))|(b>>y)instead.My implementation: 23653130
How would one go about solving D if the question was the union of all of the segments instead of the intersection?
I think a bit about it!!! And I don't think it can be solved better than O(nk). Anyone else have an idea?!
Can you share your method? The best I could think of its an O(kn^2) solution.
Sure! First, we sort segments and remove the segments that are inside another segments. We can simply prove they are useless. Now if li > lj then ri > rj. We arrange the segments with their li. Define dp[i][j] equal to the maximum union of j segments from 1 to ith! We consider two condition for ith segment to fill dp[i][j]: If the previous picked segment have any share range with this, then we choose the leftmost segment that have share range with this as k and simply dp[i][j] = dp[k][j-1]+(ri-li+1)-(rk-li+1). and If not we can update dp[i][j] from maximum of dp[k][j-1](k from 1 to k-1) and then dp[i][j] = mx[k-1][j-1]+(ri-li+1). Am I wrong?!
Ah, I missed out the dp transit optimization part, that's a neat observation.
Could persistent data structure help improve the algorithm? The dp transition is always going to be shift one step to the right and add the same variable if a segment is "profitable".
To be honest, I don't know about persistent data structure well! As I was thinking about it, actually, the updating is good enough to be much more optimizer! I will think about it tonight and I'll share the result(if I have any results)!
Now I think more about it I don't think persistent data structure is a feasible data structure, as there is no way to update the next state merely from the latest state. As we have to update from both the just overlapping position and the just not overlapping position it is very hard to maintain the data structure that supports update function at every version.
Another greedy solution for D code.
My O(nlog(n)) solution using Sort and Heap for problem D (div2). 23736804
To sum up sorting takes O(nlog(n)) traversing with heap operations also O(nlog(n)). Total time complexity is also O(nlog(n)).
Problem E tags contains "fft". Could someone give me a hint about that approach?
http://codeforces.com/blog/entry/49613?#comment-335977
Thanks, it helped me a lot