991A - If at first you don't succeed...
Всего студенты разбились на 4 группы — те кто посетил только первый ресторан, кто только второй, кто посетил оба ресторана и кто не сдал экзамен. Один из наиболее простых вариантов отсечь все некорректные случаи — посчитать, сколько студентов оказалось в каждой группе. Для первой группы это значение равно A - C, для второй: B - C, для третьей: C, для четвертой: N - A - B + C. Теперь достаточно проверить, что в первых трех группах неотрицательное число студентов, а в последней — положительное. Если это так, то количество студентов в последней группе и есть ответ на задачу.
int n1 = a - c;
int n2 = b - c;
int n3 = c;
int n4 = n - n1 - n2 - n3;
if (n1 >= 0 && n2 >= 0 && n3 >= 0 && n4 > 0)
cout << n4;
else
cout << -1;
В общем случае, рекомендуется ознакомиться с методом включений-исключений.
Кроме того, ограничения в задаче позволяют перебрать значения количества студентов в каждой группе (кроме третьей) за O(N3) и проверить, соответствует ли такое разбиение условию. Если ни одно разбиение не подошло — вывести - 1:
int n3 = c;
for (int n1 = 0; n1 <= n; n1++)
for (int n2 = 0; n2 <= n; n2++)
for (int n4 = 1; n4 <= n; n4++)
if (n1 + n3 == a && n2 + n3 == b && n1 + n2 + n3 + n4 == n) {
cout << n4;
return 0;
}
cout << -1;
В этой задаче применим жадный алгоритм. Действительно, Васе выгодно сначала исправлять наиболее низкие оценки. Поэтому можно отсортировать полученные оценки в порядке возрастания и начать заменять их на 5, пока не получим желаемый результат. Для проверки результата можно после каждой операции вычислять среднее арифметическое заново (итого, сложность будет O(N2)) или поддерживать текущую сумму оценок, пересчитывая среднее арифметическое за O(1) с общей сложностью O(N), без учета сортировки, например, так:
bool check(int sum, int n) {
// integer representation of sum / n >= 4.5
return sum * 10 >= n * 45;
}
int main() {
... // read integers to vector v and calculate sum
sort(v.begin(), v.end());
int ans = 0;
while (!check(sum, n)) {
sum += 5 - v[ans];
ans++;
}
cout << ans;
}
Разумеется, оба подхода легко укладываются в ограничение по времени. Кроме того, рекомендуется избежать вычисление среднего арифметического значения с использованием вещественных чисел.
Несложно проверить, что для некоторого k условие выполняется (Вася съест не менее половины эклеров), то и для любого большего k это условие выполнится.
Действительно, рассмотрим количество эклеров, которое останется вечером каждого дня при некотором выбранном k1 — пусть в день i останется ai эклеров. Если мы возьмем для Васи другое число k2 > k1, то в первый вечер останется меньше эклеров: b1 < a1. Но тогда Петя вечером съест эклеров не больше, чем в первом случае, однако на следующий день их будет все равно не больше, чем в первом случае (если n1 > n2, то n1 - n1 / 10 ≥ n2 - n2 / 10). Аналогично с учетом k2 > k1 и к вечеру второго дня b2 < a2 и так далее. Таким образом, для любого i получаем bi < ai, а значит и Петя каждый день будет есть не больше эклеров, чем в первом случае. Значит, Петя в сумме съест не больше эклеров, чем в первом случае, а Вася — не меньше.
Значит, эту задачу можно решать при помощи бинарного поиска по ответу. Для проверки конкретного выбранного k можно использовать простую симуляцию процесса, описанного в условии.
bool check(long long k, long long n) {
long long sum = 0;
long long cur = n;
while (cur > 0) {
long long o = min(cur, k);
sum += o;
cur -= o;
cur -= cur / 10;
}
return sum * 2 >= n;
}
Поскольку Петя съедает 10% от количества оставшихся эклеров, то это количество убывает экспоненциально, значит, пройдет достаточно мало дней прежде чем будут съедены все эклеры. В худшем случае ребятам потребуется 378 дней. Формально же асимптотика этого решения есть O(log(n)2).
Как и в предыдущей задаче рекомендуется избежать работы с вещественными числами и все вычисления производить в целых типах.
В этой задаче применим следующий жадный алгоритм. Будем идти по столбцам слева-направо, если мы сейчас рассматриваем столбец i и мы можем поставить фигуру, занимающую клетки столбцов i и i + 1, то нужно ее поставить. Действительно, если в оптимальном решении столбец i не занят ни одной фигурой, то в столбце i + 1 клетки заняты максимум одним слонопотамом. Значит, его можно убрать и поставить в столбцы i и i + 1, от этого ответ станет не хуже.
Немного более сложный вопрос — как именно поставить фигуру, если все 4 клетки столбцов i и i + 1 свободны (в других случаях фигуру можно поставить только одним способом)? Разумеется, в столбце i выгодно занять обе клетки. Оказывается, при этом неважно, какую именно клетку столбца i + 1 займет слонопотам. Действительно, клетки столбца i + 1 могут пригодиться только при размещении фигуры в столбцах i + 1,i + 2. Если в столбце i + 2 свободно не более одной клетки, то разместить фигуру не получится и клетки столбца i + 1 ни на что не влияют. Если же в столбце i + 2 свободны обе клетки, то мы можем разместить слонопотама при любом выборе занятой клетки столбца i + 1.
Из этого следует, что нам вообще можно не расставлять фигуры, а лишь пересчитывать количество свободных клеток в столбцах. В соответствии с описанным алгоритмом, получаем такой код:
... // read strings s[0] and s[1]
int ans = 0;
int previous = 0;
for (int i = 0; i < n; i++) {
int current = (s[0][i] == '0') + (s[1][i] == '0');
if (current == 0)
previous = 0;
if (current == 1) {
if (previous == 2) {
ans++;
previous = 0;
}
else
previous = 1;
}
if (current == 2) {
if (previous > 0) {
ans++;
if (previous == 2)
previous = 1;
else
previous = 0;
}
else
previous = 2;
}
}
Более того, эту реализацию можно заметно упростить, сведя решение всего к двум случаям:
int ans = 0;
int empty = 0;
for (int i = 0; i < n; i++) {
int current = (s[0][i] == '0') + (s[1][i] == '0');
empty += current;
if (empty >= 3) {
empty -= 3;
ans++;
}
else
empty = current;
}
Формально данную реализацию можно отнести к динамическому программированию. Разумеется, ее можно написать и не обладая глубокими знаниями этого метода.
Кроме того, задачу можно решать более ''явной'' динамикой (например в качестве состояния использовать номер текущего столбца и состояние предыдущего). В этом случае реализация будет чуть более сложной, но не будет необходимости доказывать описанные выше утверждения.
Из условия следует, что цифры оригинального номера автобуса представляют собой некоторое подмножество цифр номера, увиденного Васей. Перебрать подмножество цифр можно стандартным алгоритмом за 2k операций (где k — длина числа n). При этом каждое подмножество нужно проверить на корректность (содержит ли оно все нужные цифры) и привести к ''каноническому'' виду (например, отсортировать), чтобы избежать повторений с подмножествами, отличающимися лишь порядком цифр. Среди корректных наборов нужно оставить только уникальные.
long long ans = 0;
for (int i = 1; i <= (1 << k); i++) {
string c;
for (int j = 0; j < k; j++)
if (i & (1 << j))
c += n[j];
ans += getans(c);
}
Теперь для выбранного набора цифр нужно посчитать количество вариантов номера автобуса. Это можно сделать за O(k), использовав стандартную формулу числа перестановок мультимножества (см. секцию ''Permutations of multisets'' в статье про перестановки и мультиномиальные коэффициенты)
C = k! / (c0! * c1! * ... * c9!),
где k — общее количество цифр в наборе, а ci — количество цифр i в наборе:
long long fact[20];
int c[10];
void split(string s, int *c) {
for (int i = 0; i < 10; i++)
c[i] = 0;
for (char ch : s)
c[ch - 48]++;
}
long long getCount() {
long long ans = fact[accumulate(c, c + 10, 0)];
for (int i = 0; i < 10; i++)
ans /= fact[c[i]];
return ans;
}
Из этого числа нужно вычесть количество номеров, начинающихся на 0, если 0 присутствует в наборе. Сделать это достаточно просто: если мы поставим на первое место 0, то достаточно уменьшить k на 1 и c0 на 1, после чего применить формулу выше — она посчитает количество способов разместить остальные цифры набора.
long long getans(string s) {
split(s, c);
// check whether the string contains all digits
for (int i = 0; i < 10; i++)
if (c0[i] && !c[i])
return 0;
// check whether we already processed such string
sort(s.begin(), s.end());
if (was.count(s))
return 0;
was.insert(s);
long long ans = getCount();
if (c[0] > 0) {
c[0]--;
ans -= getCount();
}
return ans;
}
Итого, даже при грубой оценке сложности и простой реализации получаем асимптотику O(2k * k), где k ≤ 19 — количество цифр числа n. Легко проверить, что ответ всегда не превосходит 1018, поэтому для его вычисления достаточно ограничиться стандартным 64-битовым типом.
Все числа в задаче (кроме числа 1010, которое дано в примере) содержат максимум 10 цифр. Значит, если мы хотим найти более короткое представление, оно должно содержать максимум 9 цифр. Заметим, что длина суммы двух чисел не превосходит суммы длин чисел, поэтому в оптимальном представлении максимум одно слагаемое является числом, а остальные слагаемые — выражения содержащие *
или ^
. Каждое выражение имеет длину хотя бы 3 символа, значит, в представлении может быть максимум 3 слагаемых. Максимальное число, которое можно представить 3 слагаемыми: 9^9+9^9+9
, но это число содержит лишь 9 знаков, а выражения с 3 слагаемыми всегда содержит минимум 9 знаков. Значит, всегда существует оптимальное представление, содержащее максимум два слагаемых.
Тогда существует 3 варианта, как можно представить исходное число:
n = a^b
n = x+y
n = x*y
где x и y — выражения (в первом случае a и b — числа), не содержащие знаков +
. Причем, во всех случаях эти выражения содержат максимум 7 символов.
Давайте найдем для каждого x, не превосходящего n, эквивалентное выражение m[x], содержащие не более 7 символов (если оно короче, чем само число), а так же для каждой длины d — список чисел s[d], которые можно представить выражением длины d. Для этого удобно использовать, например, стандартные контейнеры map и set в C++:
map<long long, string> m;
set<long long> s[10];
string get(long long x) {
if (m.count(x))
return m[x];
return toString(x);
}
void relax(long long x, string str) {
// obviously not optimal
if (x > n || str.length() >= getlen(x))
return;
// already have better
if (m.count(x) && m[x].length() <= str.length())
return;
s[m[x].length()].erase(x);
m[x] = str;
s[str.length()].insert(x);
}
Сначала добавим все возможные выражения вида a^b
— их будет порядка sqrt(n)
.
void generatePowers() {
for (long long x = 2; x * x <= n; x++) {
long long c = x * x;
int p = 2;
while (c <= n) {
string tmp = toString(x) + "^" + toString(p);
relax(c, tmp);
c *= x;
p++;
}
}
}
Теперь рассмотрим выражения, состоящие из нескольких множителей. Заметим, что аналогично со сложением, в выражении максимум один множитель является числом. Тогда выражение может иметь только вид:
x = a^b*c^d
x = a^b*c
где a, b, c и d — некоторые числа. Давайте переберем длину i первого множителя и пройдем по всем значениям контейнера s[i]. Тогда второй множитель может иметь длину максимум d = 7 - i - 1 и вариантов выбрать этот множитель будет достаточно мало. Второй множитель можно перебрать, пройдя по контейнерам длины до d в первом случае, либо перебрать числа от 1 до 10d во втором случае. Всего при этом мы добавим в m порядка k = 150000 чисел:
void generatePowerAndPower(int maxlen) {
for (int i = 1; i <= maxlen; i++)
for (int j = i; i + j + 1 <= maxlen; j++)
for (auto x : s[i])
for (auto y : s[j])
relax(x * y, get(x) + "*" + get(y));
}
void generateSimpleAndPower(int maxlen) {
for (int i = 1; i + 2 <= maxlen; i++)
for (long long x = 1; x < p10[maxlen - 1 - i]; x++)
for (long long y : s[i])
relax(x * y, toString(x) + "*" + get(y));
}
void precalc() {
generatePowers();
generatePowerAndPower(7);
generateSimpleAndPower(7);
}
Теперь вернемся к представлению исходного числа. Для случая a^b
мы уже добавили выражения в m. Для случаев x+y
и x*y
заметим, что можно считать, что длина выражения x не больше 4. Давайте переберем x среди найденных выражений длины до 4, а так же среди чисел от 1 до 104. Для каждого x и для каждого из двух вариантов мы однозначно определяем значение y, оптимальное представление которого уже записано в m или просто равняется числу. Таким образом, для каждого x мы сможем найти оптимальный ответ за два обращения к m, то есть за log(k) операций.
string ans;
void relaxAns(string s) {
if (ans.length() > s.length())
ans = s;
}
void check2() {
for (int i = 1; i * 2 + 1 < ans.length(); i++) {
for (long long x = 1; x <= p10[i]; x++) {
relaxAns(get(n - x) + "+" + get(x));
if (n % x == 0)
relaxAns(get(n / x) + "*" + get(x));
}
for (auto x : s[i]) {
relaxAns(get(n - x) + "+" + get(x));
if (n % x == 0)
relaxAns(get(n / x) + "*" + get(x));
}
}
}
int main() {
... // read n, calculate powers of 10
precalc();
ans = get(n);
check2();
cout << ans;
}
Итого, общая сложность алгоритма есть O((sqrt(n) + k + 104) * log(k)).
I like it when you publish solution with code inside! Thanks ashmelev!
Ps: would it be greater if you post pseudocode instead of real source code? So that non-C++ people can appreciate it too. :P (That said your code snippet is clear enough even for people with minimal exposure to C++, I think)
Nice , clear & descriptive editorial.
can anyone explain what is the difference between k-=k/10 and k-=(int)(0.1*k) where k is an integer
with reference to C problem k must be taken as long long, k/10 will also be long long but you are converting what is supposed to be long long to int creates the problem
i was it in general.in the problem submission i have used long long
i am specifically talking about k-=(int)(0.1*k) this expression even though k is long long this conversion to (int) just kills it
It is worth noting that k -= 0.1*k is also incorrect because it causes a conversion from long long to double and doubles can only represent integers precisely up to 10^16. Since k can be up to 10^18, you will get precision errors when converting k to a double.
I m genuinely asking this question.... Does anybody has good material to solve binary search problems???
I have already read about and understood the idea and concept binary search but in many question i have been missing all the answers in a test case by 1 digit and its really frustrating investing time in it during a contest.....
Plz help!!!!!!!!
You can always refer to A2OJ ....Binary Search Problems
Rather post it as a blog post. Might even help as an archive if you post there.
Will do.... Thanks
For integers you can just memorize two workable forms
int mid = (lo+hi)/2;
either search(lo, mid) // hi = mid\
or search(mid+1, hi) // lo = mid+1
int mid = (lo+hi+1)/2;
either search(lo, mid-1) // hi = mid-1
or search(mid, hi) //lo = mid
which will help you for most problems.
Nice tip thanks
most epic and crystal clear explanation of binary search is following.
first: notice that any complex binary search task can be transformed into following task: in array of zeroes and ones find border between 0 and 1. for example.
In first case b[i] = 1 is when a[i] > 5, in second case b[i] = 1 when a[i] >= 5.
Now, how to find border? We will have two indexes: l and r. We will use invariants: l always point to 0, and r always point to 1 (invariants are awesome). Now, if some index c points to 1 then set r to c, else set l to c. Invariants still holds. One invariant missing: to prove that binary search will complete in finite time, you need to reduce r-l each step. So, we need one more invariant: c should be between l and r. And c should not coincide with l or r. Easy to show that formula $$$c = \left\lfloor\frac{l+r}{2}\right\rfloor$$$ has this property. Also it is reducing range into half.
Now, we know that after seach l is pointing to zero right next to border, and r is pointing to r right next to border.
So, in first case we should return l, and in second case we should return r. In the end, don't forget to check before running binary search that in the beginning invariants holds. r indeed points to 1 and l indeed points to 0. Otherwise our prove is not legit. And also, you don't need to have this array of zeroes and ones. You can make element of it on the fly.
I didn't get which array is a and which array is b . Could you please explain again thanks in advance :)
Array A is "array", arrays B are arrays "find last/first 5"
The recursive solution for E is nicer and simpler.
So could you please explain it to me?
I'm kinda bad at explaining recursion..
In my solution I recur from 9 to 0 and iterate (from 1 to the number of times that digit appears) = j. To calculate the number of ways to add the digit do the current string with length = m, I do (j + m)! / (j! * m!). Then I continue recursion passing this result.
I divide by j! because the digit is repeated j times and I divide by m! because I can't change the order of the current string.
In problem C, I checked the condition for binary search as if(sum>=(long)(ceil((double)n/2))) return true and it gave WA in system test. Now after changing it to sum*2>=n, it gives correct answer. Why is first one wrong ? @ashmelev
I think it should be floor instead.
suppose we are checking x>=n/2 if n=5 then x>=3 not x>=2
ceil(5/2) will give 2 as it is not float value
https://ideone.com/Yt5Zkh
I think ceil is correct. If sum=8 and n=15. Then sum*2>=n is true as 16>=15. Now if we take floor then 8>=floor(15/2), 8>=7 is false, so its not correct. So ceil will give correct answer.
dude check my code again!!
In my code actually it is sum>=(ceil((double)n/2)). So I have casted it to double before dividing.So its proper.
actually using double creates the problem here. We have to note the capacity range of double..we should use long double for it. So when I did declared n as long double and did ceil(n / 2), it gave correct answer then.
You should have used long double instead of double
Because double/float may cause precison error. e.g. (double)1000/2 can become 500.00000001. and ceil(500.00000001) is 501 (but actually it should be 500), so it can give wrong answer.
I understand what you are trying to say. But can you give a proper example where it will fail. I tried your example and it works properly.
I don't know any exact testcase. But you may find the accepted answer of this stackoverflow question useful.
Good editorial !
Here are all my solutions to the contest and here is my editorial to C for beginners who have never seen binary search used for anything other than finding an element of an array.
+1. You are doing a great job by writing explanations. Please, keep up the good work.
Thank you for the encouragement :)
F's solution states the following:
How can one show that?
For example, let’s take an expression x*y. If at least one of the expressions x, y contains at least 8 digits then the whole expression contains at least 8+1+1=10 digits, which is greater or equal to the length of every number in problem.
Can anyone explain what this loop does? for (int j = 0; j < k; j++) if (i & (1 << j)) c += n[j];
Read this tutorial : https://www.hackerearth.com/practice/notes/bit-manipulation/
ashmelev In Div2 C, what would be the time complexity for checking function? wouldn't it be O(n/k)?
We multiply the number of candies by 0.9 every day, so it decreases fast — it will be enough about log(n) / log(1 / 0.9) days, 378 days in the worst case.
While 0.9365 is about 2e-17 :)
In E what is c0 and what do you mean by "check whether the string contains all digits". Please explain.
In the solution c0[i] — amount of digits i in the original (input) number. ''contains all digits'' — a meant ''contains all digits which the input number contains'' i.e. if c0[i] > 0, c[i] should be > 0 too.
If anyone is confused with editorial about problem E, check my submission it has comments and explanation, and I tried to cover whole solution, I hope it helps you understand the solution
Does 991C — Candies have an O(1) solution?
In 991C editorial prove of same count of days is missing. If with larger k there are shorter amount of days, then Vasya may eat less amount of candies.
If the k is bigger Vaysa will eat more,
Let's Compare both situations:
K1>K2 (K on the first day and K on the second day)
So Vaysa will eat more in her steps.
As the Result Petya will eat less because the result after eating Vaysa in the first situation will be less than the result in the second situation so:
n2 < n1(after eating Vaysa)==> n2/10 < n1/10(Because this are 2-digits) ==> So Petya in the second situation will eat less.
If it's not clear write it on paper.
K is fixed. And Vasya is him. your formula is repeating of editorial. yes, petya will eat not bigger in each corresponding day, but who said that count of days is same? who said that they will eat same count of days? something is missing. proof should take into consideration count of days.
Vasya is eating in the morning and Petya in the evening, how days for Vasya will be shorter ?
Do you have any such test case?
I don't compare Vasya vs Petya. I compare number of days they eat with different k. Proof in editorial talks about certain days, and for fixed index of day it looks legit. But nowhere mentioned that number of days until they eat everything may change.
How to solve problem D using DP approach. I solved it using greedy approach but i'm learning DP. Could you give me a detailed explanation for DP problem D? Thanks in advance.
Hd7 63735860
this is my solution if you are interested. just consider the previous orientation of the piece placed and the possible orientation to be place at column i and maximize with the case that you go the next cell without placing anything. 0 is there is no placed piece to the left 1, 2, 3, 4 the 4 orientations
Thank you.
please can you explain DP approach i am not able to think of transitions