991A - If at first you don't succeed...
There are 4 groups of students — those who visited only the first restaurant, who visited only the second, who visited both places and who stayed at home. One of the easiest ways to detect all the incorrect situations is to calculate number of students in each group. For the first group it is A - C, for the second: B - C, for the third: C and for the fourth: N - A - B + C. Now we must just to check that there are non-negative numbers in the first three groups and the positive number for the last group. If such conditions are met the answer is the number of students in the fourth group.
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;
In general you are recommended to view inclusion–exclusion principle.
Moreover the limitations allow to go over all possible numbers of students for each group (except for the third) in O(N3) and to check whether such numbers produce a correct solution. If no correct numbers found, just print - 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;
It is necessary to use the greedy approach: of course Vasya should redo the lowest grades firstly. So we have to sort the values in the ascending order and begin to replace the values by 5 until we get the desired result. In order to check whether the current state is suitable we may calculate the mean value after each iteration (O(N2) complexity in total), or just update sum of the grades and calculate the arithmetic mean in O(1) with O(N) total complexity (excluding sorting). For example:
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;
}
Of course, both approaches easily fit TL.
Finally, it is recommended to avoid floating-point operations while calculating the mean value.
It is easy to check that if for some value k the necessary condition is met (Vasya eats at least half of the candies), then it is met for each integer greater k.
Let's consider the number of candies remaining at the evening of each day for some selected k1 — let ai candies remain at day i. If Vasya will use another number k2 > k1 we will have less candies in the first day: b1 < a1. So Petya will eat no more candies than in the first case (for k1), but in the next day the number of candies will be not greater than in the first case (if n1 > n2 then n1 - n1 / 10 ≥ n2 - n2 / 10). The same way, including that k2 > k1 at the evening of the second day we get b2 < a2 and so on. In general, for each i we have bi < ai, so Petya will eat not more candies than in the first case in total. It means that Vasya will eat not less candies than in the first case.
So this problem can be solved using the binary search (answer) approach. In order to check whether selected k is applicable it necessary just to implement the process described in the problem statement.
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;
}
Since Petya eats 10% of candies, its amount decreases exponentially, so there will be only few days before all the candies will be eaten. In the worst case it is necessary 378 days. Formally the complexity of the solution is O(log(n)2).
Like in the previous problem it is recommended to avoid floating operations and to use only integer types.
In this problem we may use the greedy approach. Let's go through columns from left to right. If we are currently considering column i and we may place a figure occupying only cells at columns i and i + 1, we have to place this figure. Really if the optimal solution doesn't contain a bishwock at column i then column i + 1 may be occupied by at most one bishwock. So we can remove this figure and place it at columns i and i + 1, the result will be at least the same.
A bit harder question is — how exactly we should place the figure if all 4 cells of columns i and i + 1 are empty (in other cases there will be only one way to place a bishwock)? Of course, we should occupy both cells of column i. Moreover it does not matter which cell we will occupy at column i + 1 in this case. The cells of i + 1 may be used only for placing a bishwock in columns i + 1,i + 2. If column i + 2 has at most one empty cell we are unable to place such figure and the remaining empty cells of column i + 1 are useless at all. If both cells of column i + 2 are empty we may place a bishwock regardless of the position of the remaining empty cell at column i + 1.
It means that we don't have to place the figures actually — we have to calculate and update number of empty cells in columns. According to the described algorithm we may write such code:
... // 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;
}
}
Moreover this implementation can be simplified to just two cases:
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;
}
Formally such algorithm may be considered as the dynamic programming. Of course it is not necessary to have a deep understanding of DP to write such implementation and solve the problem.
This problem also can be solved by more ''obvious'' DP approach (for example we may consider index of current column and state of the cells of the previous column as a state of DP). In this case the implementation will be a bit more complicated but it won't be necessary to prove described solution.
According to the statement, digits of original bus number form a subset of digits of the number seen by Vasya. It is possible to iterate through all the subsets in 2k operations (where k is length of n). For each subset we need to check whether it is correct (contains all necessary digits) and transform it to ''normal'' state (sort the digits for example), in order to avoid conflicts with another subsets which differ only at the digits order. We have to keep only unique subsets.
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);
}
Now for each subset of digits we have to calculate amount of corresponding correct bus numbers. It can be calculated in O(k) operations using permutations of multisets formula (see ''Permutations of multisets'' at the article about permutations and multinomial coefficients)
C = k! / (c0! * c1! * ... * c9!),
where k — total number of digits in the subset and ci — number of digits 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;
}
Now, we have to subtract amount of bus numbers with leading zeroes from the result for this subset if it contains digit 0. This can be done in the very same way: if we place digit 0 at the first position of the number, we have to decrease k by 1 and decrease c0 by 1; the formula described above will calculate amount of ways to place remaining digits of the subset and this number should be subtract from the answer:
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;
}
In total, even with such rough evaluation of complexity and naive implementation we get O(2k * k) operations, where k ≤ 19 — amount of digits in n. It is easy to check that the answer doesn't exceed 1018 so the standard 64-bit integer type will be enough.
All the problem numbers (except for 1010, which is given in the samples) contain at most 10 digits. It means that we have to use at most 9 digits if we want to find a shorter representation. Notice that the length of sum of two integers is not greater than sum of the lengths of these integers, so in the optimal representation at most one term is a number while other terms are expressions containing * and/or ^. Each expression (not a number) contains at least 3 symbols, so the optimal representation can contain at most 3 terms. The maximal integer that can be represented in such manner is 9^9+9^9+9, but it contains only 9 digits while expressions with 3 terms always contain at least 9 symbols. So we proved that there always exists an optimal representation which is a sum of at most two terms.
So there exist only 3 types of representation of the original number:
n = a^bn = x+yn = x*y
where x and y — some expressions (in the first case a and b are numbers), which doesn't contain +. Moreover in all the cases such expressions should contain at most 7 digits.
Let's find for each x ≤ n a shortest valid representation m[x], containing at most 7 symbols (if it exists and contains less digits than simple number x), and for each length d — set of integers s[d] which can be represented by an expression of length d. The standard containers (std::map and std::set в C++) are suitable for that:
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);
}
Firstly let's add all expressions a^b, there are about sqrt(n) such expressions.
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++;
}
}
}
Now lets consider the expressions containing several multipliers. The same way (as for addition) in such representation at most one multiplier is a number. Including that the expression can contain at most 7 digits we have only 2 possible ways:
x = a^b*c^dx = a^b*c
where a, b, c and d are some numbers. Lets iterate through i — the length of the representation of the first multiplier and go over all values stored in s[i]. The second multiplier can have length at most d = 7 - i - 1 and the total number of ways to choose two multipliers will be small enough. The second multiplier should be selected from containers s[j] for length at most d (in the first case), or we should iterate from 1 to 10d (in the second case). After that we will have about k = 150000 numbers in m in total:
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);
}
Now lets go back to the representation of the original number. For the first case — a^b — we have already stored such values in m. For the cases x+y and x*y we may assume that the length of expression of x is not greater than 4. Now lets iterate through x among found representations of length up to 4, and among integers from 1 to 104. For each such x and for each of 2 cases we determine value of y uniquely, and the optimal representation of y is already stored in m or it is just a number. So, for each such x we can find optimal answer for n by at most two addressing to m i.e. in log(k) operations.
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;
}
Finally, the total algorithm complexity is 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