1728A - Colored Balls: Revisited
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
cout << max_element(a.begin(), a.end()) - a.begin() + 1 << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> p(n);
iota(p.begin(), p.end(), 1);
for (int i = n & 1; i < n - 2; i += 2) swap(p[i], p[i + 1]);
for (int &x : p) cout << x << ' ';
cout << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
forn(i, n) scanf("%d", &a[i]);
forn(i, n) scanf("%d", &b[i]);
priority_queue<int> qa(a.begin(), a.end());
priority_queue<int> qb(b.begin(), b.end());
int ans = 0;
while (!qa.empty()){
if (qa.top() == qb.top()){
qa.pop();
qb.pop();
continue;
}
++ans;
if (qa.top() > qb.top()){
qa.push(to_string(qa.top()).size());
qa.pop();
}
else{
qb.push(to_string(qb.top()).size());
qb.pop();
}
}
printf("%d\n", ans);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int comp(char c, char d){
return c < d ? -1 : (c > d ? 1 : 0);
}
int main() {
int t;
cin >> t;
forn(_, t){
string s;
cin >> s;
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int len = 2; len <= n; len += 2) forn(l, n - len + 1){
int r = l + len;
dp[l][r] = 1;
{
int res = -1;
if (dp[l + 1][r - 1] != 0)
res = max(res, dp[l + 1][r - 1]);
else
res = max(res, comp(s[l], s[r - 1]));
if (dp[l + 2][r] != 0)
res = max(res, dp[l + 2][r]);
else
res = max(res, comp(s[l], s[l + 1]));
dp[l][r] = min(dp[l][r], res);
}
{
int res = -1;
if (dp[l + 1][r - 1] != 0)
res = max(res, dp[l + 1][r - 1]);
else
res = max(res, comp(s[r - 1], s[l]));
if (dp[l][r - 2] != 0)
res = max(res, dp[l][r - 2]);
else
res = max(res, comp(s[r - 1], s[r - 2]));
dp[l][r] = min(dp[l][r], res);
}
}
if (dp[0][n] == -1)
cout << "Alice\n";
else if (dp[0][n] == 0)
cout << "Draw\n";
else
cout << "Bob\n";
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(long long a, long long b, long long c, long long &x0, long long &y0, long long &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
int main() {
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
forn(i, n) scanf("%d%d", &a[i], &b[i]);
long long cur = accumulate(b.begin(), b.end(), 0ll);
vector<int> difs(n);
forn(i, n) difs[i] = a[i] - b[i];
sort(difs.begin(), difs.end(), greater<int>());
vector<long long> bst(n + 1);
forn(i, n + 1){
bst[i] = cur;
if (i < n)
cur += difs[i];
}
int mx = max_element(bst.begin(), bst.end()) - bst.begin();
int m;
scanf("%d", &m);
forn(_, m){
int x, y;
scanf("%d%d", &x, &y);
long long x0, y0, g;
if (!find_any_solution(x, y, n, x0, y0, g)){
puts("-1");
continue;
}
long long l = x * 1ll * y / g;
long long red = x0 * 1ll * x;
red = red + (max(0ll, mx - red) + l - 1) / l * l;
red = red - max(0ll, red - mx) / l * l;
long long ans = -1;
if (red <= n) ans = max(ans, bst[red]);
red -= l;
if (red >= 0) ans = max(ans, bst[red]);
printf("%lld\n", ans);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 1003;
int n;
int a[N];
vector<int> g[N * N];
int mt[N];
bool used[N * N];
vector<int> val;
bool kuhn(int x)
{
if(used[x]) return false;
used[x] = true;
for(auto y : g[x])
if(mt[y] == -1 || kuhn(mt[y]))
{
mt[y] = x;
return true;
}
return false;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++)
for(int j = 1; j <= n; j++)
val.push_back(a[i] * j);
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
int v = val.size();
long long ans = 0;
for(int i = 0; i < n; i++)
for(int j = 1; j <= n; j++)
{
int k = lower_bound(val.begin(), val.end(), a[i] * j) - val.begin();
g[k].push_back(i);
}
for(int i = 0; i < n; i++) mt[i] = -1;
for(int i = 0; i < v; i++)
{
if(kuhn(i))
{
ans += val[i];
for(int j = 0; j < v; j++) used[j] = false;
}
}
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
int D, n, m;
scanf("%d%d%d", &D, &n, &m);
vector<int> inv(D + 1);
forn(i, D + 1) inv[i] = binpow(i, MOD - 2);
vector<int> b(n);
forn(i, n) scanf("%d", &b[i]);
vector<int> a(m);
forn(i, m) scanf("%d", &a[i]);
sort(a.begin(), a.end());
int fl = (1 << m) - 1;
vector<int> ways(1 << m, 1);
forn(i, m) forn(j, n){
int d = abs(b[j] - a[i]);
int mask;
if (b[j] > a[i]){
int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin();
mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
}
else{
int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin();
mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
}
ways[mask] = mul(ways[mask], d);
mask ^= (1 << i);
ways[mask] = mul(ways[mask], inv[d]);
}
forn(i, m) for (int mask = fl; mask >= 0; --mask) if ((mask >> i) & 1){
ways[mask ^ (1 << i)] = mul(ways[mask ^ (1 << i)], ways[mask]);
}
ways[0] = binpow(D + 1, n);
forn(mask, 1 << m){
ways[mask] = mul(ways[mask], __builtin_popcount(mask) & 1 ? MOD - 1 : 1);
}
forn(i, m) forn(mask, 1 << m) if (!((mask >> i) & 1)){
ways[mask ^ (1 << i)] = add(ways[mask ^ (1 << i)], ways[mask]);
}
int q;
scanf("%d", &q);
forn(_, q){
int x;
scanf("%d", &x);
int ans = binpow(D + 1, n + 1);
forn(i, m){
int d = abs(x - a[i]);
int mask;
if (x > a[i]){
int r = lower_bound(a.begin(), a.end(), x + d) - a.begin();
mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
}
else{
int l = lower_bound(a.begin(), a.end(), x - d) - a.begin();
mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
}
ans = add(ans, mul(add(ways[mask], -ways[mask ^ (1 << i)]), d));
}
printf("%d\n", ans);
}
return 0;
}
Awesome problemset; I really liked Red-Black Pepper, even though I couldn't solve it on time!
As for problem D... somehow, my O(n) greedy-ish algorithm passed all pretests and didn't get yoinked out of existence after system testing..... I'll be confused for a while
Edit: Here is my source code if anyone wants to look at it:
It can be proven that Bob have no winning strategy for every string. And a draw can be if and only if string have form ABC, where C is reversed A and B consists of pairs of identical letters standing next to each other (i.e. have form aabbcc...)
I wanna know the intuition about your approach . Y does Bob never loose ?
Since Alice always goes first, she can just pick the most optimal letter which remains. If there is a letter that Bob can pick to beat Alice, Alice can just pick that letter instead of the last letter she chose.
This seems like a plausible explanation. But always going first doesn't guarantee a win(even though in this case it does). A good example would be of zugzwang in chess.
But Alice can not pick s[2], s[n — 1] before s[1] or s[n] be picked。
True, Alice can't pick s[2], s[n-1] in the first turn. But she can force Bob to not be able to pick one of them.
For example consider: "zazz"
Obviously if Alice picks s[1] then Bob will win by picking s[2]. So instead, Alice can force the game so that she will be the one to pick s[2]. If Alice picks s[n] on her first move then Bob has to pick one of s[1] or s[n-1] and Alice wins.
You can apply the same logic to larger strings:
"zabcaz" Alice picks s[1] Bob picks s[2] Alice picks s[3] Bob picks s[4] Alice picks s[5] Bob picks s[6]
Thank You! This greedy approach is cool
Will this approach work for "yabz"? Because for both the choices Alice has, she'll lose.
Yes it will. Remember, the chosen character needs to be prepended and not appended. So, the game can go as follows : Alice chooses z, Bob chooses b, Alice chooses a and Bob chooses y. Hence, Alice wins. You can try all possible combinations and you'll notice that Alice will win in all of them.
My approach to Problem D is an O(n) solution. Since Bob never wins(Can check using strings of length 2,4,6 and manually verifying cases), what we need is to find the condition for the conclusion when the game ends in a draw. Firstly let us modify the input string given from s->s' where s' is s after removing all consecutive letters from start and end such that s[i]=s[length-1-i] and break the loop when s[i]!=s[length-1-i]. The reason is that if Alice picks one such letter then Bob can pick the letter from the opposite end to get a string to be the same as Alice's. Next the string s' left after removing all such letters (even 0 letters can be removed) ought to be of the form AABBCC.....ZZ where A,B,C,Z represents any letter. Reason is that if the string was AABBCC.....YZ,then Alice can pick Z and Bob has no other option but to pick either A or Y....i.e. He can never Draw with Alice and hence can only lose.
I think the most important thing to note here is that the length of the string is even + the chosen letters are prepended in the string. If either of the above conditions were not true, then Bob could have had a chance to win.
please explain your approach
It was just like what magni93 described. I guessed heuristically (proof by lack of counterexample) that Bob can't win, so that he can at best force a Draw. Additionally, a Draw can be forced only if the string looks like this: ABC, where A is an arbitrary sequence of characters, C is its reverse, and B is a sequence of pairs of adjacent identical numbers. Example: abcgghhddcba. Thus, for the first part (palindromic part), if Alices chooses a side, Bob can choose the other and maintain the Draw, and for the second, Bob can always choose the same side as Alice.
this is outta my league.. for now.. thx for explaining though i need more experience with questions
If we already know that Bob can never win, then we can proof as below.
Proof: One necesary condition for a draw is "The occurence number of Every letter cnt[letter] is even".
Let's proof that s=ABC by induction (where C is reversed A and B consists of pairs of identical letters standing next to each other).
For len(s) == 2, it's obvious. Suppose len(s) > 2 and cnt[letter] is even for every letter.
In the first turn, if Alice's best choice is s[1], and Bob's is s[n], s[1] == s[n], then by induction, s must be s[1] ABC s[n] which is also a form of ABC.
If the first turn Alice's best choice is s[1], and Bob's is s[2],then s[n] = s[1] or s[n] = s[n — 1] or else Alice will win. If s[n] = s[n — 1],Alice can alway pick one from the same side before a letter equals s[n] is met,by the induction s is the form of B. If s[n] == s[1] and s[n] != s[n — 1], Alice can choose s[n], Bob can choose s[1], and the remains must be draw too, otherwise Alice have no reason to choose s[1]. By induction, s also has form B.
thank you
Me after seeing other's D codes after contest and finding everyone used the same 100+ line dp algorithm and that doesn't remotely resemble my code.
(Problem E)
Shouldn't it be $$$-a_i + b_i$$$?
UPD: Fixed now, thanks!
for C my approach is like first remove element if it is present in both the arrays. After that only distinct element remains then decrease all the elements > 9 to single digits and add 1 to ans. Then repeat step 1 to remove duplicates. now only one digit distinct element remains for each of these elements add 1 to ans(if it is != 1). I think that my approach is right but it is not working can anyone tell why https://codeforces.net/contest/1728/submission/171533183
Your greedy approach doesn't work. For instance, if the distinct elements are a = 11, b = 12345678901. In this case, you have f(b) = a. In your approach, you would need more steps.
not a valid testcase, ai,bj<10^9 is given in conditions
You were doing
ans++
instead ofans += i.second
on lines $$$296$$$ and $$$304$$$. Also, iterating and changing elements in map at the same time can cause bugs. For some reason, just usingmap
instead ofunordered_map
does the trick in this case, but I am not sure why. I used to think that changing values while iterating would always mess the map's pointers up. Anyway, avoid using the standardunordered_map
, you can get hacked in a contest. You can read more about it in this blog.AC solution
As pointed out by brenner1, there was a trivial error in the code. I was wondering if the algorithm can be deemed incorrect even if it passes the test cases. Because it doesn't solve a more general problem (with higher constraints).
For higher constraints, we can keep repeating the steps in a while loop until both arrays are equal (won't have much impact on time complexity aswell). Also I think this is more of a brute-force kind of approach.
A problem is a problem under the given constraints. If you make a problems constraints higher of course a lot of solutions won't pass. But this given problem is for this given constraint and he only has to solve for it.
I just find it convenient to believe that the correct algorithm is more important. A correct algorithm is correct independent of the constraints. That's the only difference between a problem and an algorithm ig. I now realize that it's futile to discuss/categorize this.
No algorithm is correct independent of constraints unless the algorithm works in constant time. Sieve of erastothenes is an algorithm in O(sqrtn), which would only work work upto n<10^18. So would you not call it an algorithm?
What does time complexity have to do anything with whether the algorithm is correct or not? Given any n, I can always find primes less than n using the Sieve of Eratosthenes. Hence, it's an algorithm. Just as a brute force check for prime is also an algorithm. However, some trick that would be able to calculate primes only less than a certain number 'm' would not be termed an algorithm.
Ah u were talking like that. In that case you just have to get used to the fact that in a contest its better so solve the problem with given constraints than not at all.
My solution is as same as you and I get accepted https://codeforces.net/contest/1728/submission/171984436
How to prove that Bob never wins in Problem D ?
One way would be to look dp transitions. Having dp[i][i + 1] being equal to "Alice" or "Draw" there's no way to build winning dp of longer length.
The other way would be the following: if Bob's string does not equal to Alice's, then it is no draw for sure. Consider there is some letter in result so Alice's string differ in that letter of Bob's string and all the other on prefix are the same. No matter how Bob plays Alice manages to take smallest letter when the left string is xSS...SSy. Regardless the step we encounter this configuration at. In fact Alice's strategy to take smallest letter at each step also leaves Bob no place to win.
Having the maximum values in C as $$$10^9$$$ actually allows for a simpler (imo) solution. A multi-digit number will always become a single-digit number by performing the operation. It's impossible for an operation to produce a multi-digit number.
So after you get rid of all the overlaps from the initial arrays, you can now safely perform the operation on every multi-digit number in both arrays (if a multi-digit number is present in one array but not the other, it's impossible for it to be generated on the latter, so you must apply the operation on it in the former). No sorting needed here.
Now everything is a 1-digit number. We can check for overlaps again, and get rid of them. When there are no overlaps remaining, we need to turn everything that isn't 1 into a 1, so we count how many non-1s we have, add that to our operation count, and get our final answer.
Even if the limit on C was larger, this algorithm would be fine if we just replace $$$9$$$ by the max digits that any of the array element can have.
I'm going to link this $$$O(n)$$$ solution for Problem D here: https://codeforces.net/blog/entry/106726?#comment-951491
I'll copy my approach for problem D from the annoucement :
First, because Alice play first and the length of the string is even, Alice can force Bob to take any particular character in the string by simply never take it. After Bob take this character either the string become empty and the game end, or it become a shorter string with even length, then we use this strategy again for the shorter string. By take advantage of this, when play optimally Alice will never lose.
The only way for Bob to draw is to always take the same character as Alice. Now we reverse the game from the end to begin to see what the original string would look like :
For each double turn of Alice + Bob, we add 2 identical character to the same side or different side of our string (for example : aa→aabb,bbaa or baab)
The critical point is that if we add to the different side, we can't add to same side anymore. Take the example baab→baabcc, here Alice can take b and Bob can't take any b so he will lose
So the form of our string is : half palindrome + some pairs + other half palindrome, the 1st and 3rd part form a palindrome
I have another solution for 1728E - Red-Black Pepper which runs in $$$O(N \log_2{(N)} + NK \log_2{(K)} + M \frac{N}{K})$$$ where $$$K$$$ is a constant. I have been able to obtain a runtime of $$$1606$$$ ms by setting $$$K = 150$$$ in this submission: 171530099.
My solution doesn't require the knowledge of diophantine equations and doesn't use some of the observations given in the editorial above. It relies on a square root idea.
Setting $$$K = \sqrt{N}$$$ results in a complexity of $$$O(N \sqrt{N} \log_2{(\sqrt{N})} + M \sqrt{N})$$$ which, I suspect due to poor constant factor, unfortunately TLEd for me.
Edit: Thanks to satyam343 for pointing out a flaw in my complexity analysis. I've fixed it.
If I am not wrong, your solution runs in $$$O(N \log{(N)} + N \cdot K \log{(K)} + M \frac{N}{K})$$$.
So on setting $$$K = \sqrt{N}$$$, your complexity is $$$O(N \cdot \sqrt{N} \cdot \log{(N)} + M \cdot \sqrt{N})$$$.
Now you can improve the part of your solution which is contributing $$$N \cdot K \cdot \log{(K)}$$$. Instead of iterating over all numbers from $$$1$$$ to $$$K$$$, just iterative over all factors of $$$N-j$$$ which are smaller than $$$K$$$. This improves the constant factor.
Here's my submission. I obtained a runtime around $$$1150$$$ ms by setting $$$K=500$$$.
Edit: On putting $$$K=1000$$$, my submission runs in $$$826$$$ ms.
You're right — thank you!
I thought the bottleneck was the query part of the program because I had analysed the complexity incorrectly. Constant factor optimising by iterating over smaller factors sounds like a good idea.
Also, I believe you you meant to write $$$O(N \sqrt{N} \log_2{(\sqrt{N})} + M \sqrt{N})$$$ instead of $$$O(N \sqrt{N} \log_2{(N)} + M \sqrt{N})$$$.
It was intentional as $$$O(log(\sqrt{N})=O(log{N})$$$ :p
Can you explain your approach folks ? I understand the concept that you use , but it's still kinda hard to read
I solved it in $$$O(N log_2(N) + NK)$$$ this is my solution
Very good round, hope more. -w-
In the editorial of E:
Shouldn't it be "Then everything to the left of it is non-decreasing"?
It's kinda non-increasing if you look at it from the maximum outwards. I meant to show that both parts behave the same.
I see. Thanks!
Can anyone please explain the solution to problem D? Why the question is of DP and not greedy?
I solve it greedy in O(n) : if string s writing as s1 + s2 + s3 and s1,s3 is palindrome and s2[i]==s2[i+1] for any i :i is even then it is a draw else Alice win example string s=abbcca ,s=abeerrba ,s=abccba ,s=aabbcc here it is a draw here my submission :https://codeforces.net/contest/1728/submission/171626668
but I suggest to solve it using DP suppose we have string of length n : s[l],s[l+1],,,,,,,,s[r-1],s[r] we have four cases : p1 : Alice choose s[l] and Bob choose s[l+1] ,p1=solve(l+2,r) if p1==0 then you need to compare s[l] , s[l+1]
p2 : Alice choose s[l] and Bob choose s[r] ,p2=solve(l+1,r-1) if p2==0 then you need to compare s[l] , s[r]
p3 : Alice choose s[r] and Bob choose s[l] ,p3=solve(l+1,r-1) if p3==0 then you need to compare s[r] , s[l]
p4 : Alice choose s[r] and Bob choose s[r-1] ,p4=solve(l,r-2) if p4==0 then you need to compare s[r] , s[r-1]
then the ans[l][r] = max(min(p1,p2),min(p3,p4)) you should calculate any substring with length 2 before here my submission using DP : https://codeforces.net/contest/1728/submission/171633331
Suppose Problem D also asked to print the two optimal strings that the players will select, how do we proceed then?
You can build the same dp table as before, except in each entry, you also write down which indices $$$\ell$$$ and $$$r$$$ the dp value was copied from. The implementation gets a lot more annoying, but it's ultimately doing the same thing.
After that, once the table is filled up, you can construct Alice's and Bob's strings by going backwards on the dp table. Start with $$$dp[0][n]$$$, check whether the value came from $$$dp[1][n]$$$ or $$$dp[0][n - 1]$$$, add the appropriate character to the Alice string, and then go to that corresponding entry. Use the same process to add the appropriate character to the Bob string, and so on, until the string has no characters left.
someone please make a video tutorial for D — Letter Picking... or if there is one then please point me towards it.
Video Solution for Problem D.
Could someone explaine a D problem case "baab": Alice can pick only "b", then Bob picks "a". So "a.." < "b.." anyway. So Bob wins, but the solution contradicts this?
Since the letters are being prepended to the player's strings, if Alice chooses 'b' and then Bob chooses 'a', Alice will chose the other 'a' forcing Bob to take 'b' resulting in these strings below which makes Alice win:
Alice : "ab"
Bob : "ba"
So Bob also chooses "b" in his first chance and in the end both have string "ab" which would result in a draw
My solution to the C problem was hacked 171387514. Next day I resubmited the same code 171579962 and it passed all the tests. How do I understand my solution basicaly is correct or not? I thought that the hachs are added to tests. Could someone clarify this please? (It's not neccesary to check my code, just explain how the system works)
Some clarifications on the tutorial for 1728G - Illumination
It may be easier to think of the submask multiplying step as first sorting the points-of-interest by distance from the current lantern, keeping indices and breaking ties arbitrarily. Then over the points of interest we are multiplying the mask patterns (bits shown in ascending distance from left to right) 1*****, 01****, 001***, etc.
A zero in the mask pattern doesn't mean "illuminated", it means "may or may not be illuminated", while a one means "definitely not illuminated". We use the zeros because we have already accounted for those masks when iterating over the previous points of interest. This also handily explains why the editorial and model solution uses $$$\lt d$$$ on one side but $$$\le d$$$ on the other to decide where to assign zeros, the important thing is that ties are broken somehow.
For question D:-171677046 simple o(n^2) solution using min-max We need to observe the fact that since Alice is going first therefore either Alice can win or it will be a draw. 1 means Alice wins and 0 means it is a draw. Also remember, (0|1)=1(bitwise or). I approached it considering all the possibilities when Alice is at [l,r]. It can follow with either Alice choosing s[l] or s[r]. dp[l][r] denotes who will win after considering substring s[l,l+1.....r].
If Alice chooses s[l] then Bob will choose either s[l+1] or s[r]. So, dp[l][r]=min((s[l]<s[l+1])|dp[l+2][r],ans3|(s[l]<s[r])).The first part of min function denotes the case when Bob chooses s[l+1] and the second part denotes the case when Bob chooses s[r]. The or operation is there to take the case that Alice has the advantage of going first. Similarly, if Alice chooses s[r] then dp[l][r]=min(dp[l|[r-2(s[r]<s[r-1]),dp[l+1]][r-1]|(s[r]<s[l])).
Why am I getting TLE in Problem C?It seems like a O(n) solution.
Use map instead of unordered_map
You are right. But, can you explain the reason?
Worst case Time Complexity of operations in case of unordered_map is O(n). For map, it is O(log n)
https://codeforces.net/blog/entry/62393 read this :)
@aggressor_ thank you very much. It was helpful
you're welcome!
In the solution for D. Letter Picking in the code inside the two for loops after these lines int r = l + len; dp[l][r] = 1; { why this brackets is used, these are used after for loop while loop if statements but what work these brackets are doing here in this code , I am unable to understand it
They do nothing except for separating parts of the code.
For problem G,why not DP?Dp from l1 to ln,only the leftmost unilluminated interest is useful,and we can do it similarly from ln to l1.
Alternate solution for G using binary search and inclusion-exlusion -
(POI = point of interest)
Accepted Solution
(eg. for mask 101001, POI 0, 2 and 5 should be unlit, rest can be whatever)
To do this, you binary search for leftmost lanterns which have each POI in the mask as their closest, if lanterns $$$l_a$$$ through $$$l_b$$$ have $$$p_i$$$ as the closest POI, then multiply number of ways for that mask by $$$|p_i - l_a|*|p_i - l_{a+1}|*...*|p_i - l_b|$$$, let's call this $$$ways_{mask}$$$
You can do this using inclusion-exclusion, let's call this $$$ways_{mask}'$$$, then $$$ways_{mask}' = [\Pi_m ways_m*(-1^{popcnt(m)+popcnt(mask)})]$$$ where $$$m$$$ & $$$mask = mask$$$
Let the new lantern be at $$$pos$$$ For each POI, calculate distance from $$$pos$$$ and sort them in decreasing order, let's say the distances are $$$[4, 2, 1]$$$ for POIs $$$[2,0,1]$$$, then we calculate the sum of $$$ways_{mask}'$$$ where mask contains bit no. 2, for all these masks, if the new lantern has a brightness of 3 or less, all POIs are still not lit. Next we calculate the sum for masks where mask contains bit no. 0 but not bit no. 2, for all these masks, if the new lantern has a brightness of 1 or less, all POIs are not lit. We continue this procedure m times, giving us the final number of ways in which the POIs are not fully illuminated
For sum of $$$ways_{mask}'$$$ and for calculating $$$ways_{mask}'$$$ in the first place, you would need to use SOS DP
Final time Complexity — $$$O(m*2^m*log(n) + q*m*log(m))$$$
For the tutorial on Problem E — since we're checking how many dishes with black peppers we are going to include in our answer, it should say "Then we would want to check the answer for
b*y black peppers
" Right ?Great problem and editorial btw. (y)
I found a simplier soution to problem E. It doesn't need any observations about the "non-strictly convex" property of tastiness and I didn't had to deal with diophantine equations. We can check all possibilities! There is not so much of them.
Sort the shops by their x_j values, (ans secondarily by their y_j values). For considering only the x_j values first, if x_j=1 you have N possibilities, if x_j=2 you have N/2... All in all you have (N+N/2+N/3+N/4+...N/N) possibilities, which is ~ NlogN,2022-12-06 posibbilities. For a fixed x_j, check all possibilities considering y_j too, that is (N/x_j)/(y_j) possibilities.
So all in all, u have to check NlogN+N/2log(N/2)+N/3log(N/3)... possibilities, which is
So this solution runs around O(Nlog^2N) and passes in 1 sec.
I noticed your solution here — https://codeforces.net/contest/1728/submission/184141199 . Can you make it more readable and add some comments ? Would be greatly appreciated.
For problem F, the tutorial mentions "there are some implementations of Kuhn's algorithm which can run on graphs of size about $$$10^5$$$". It suggests one optimizing strategy that works here (don't always reset visited markers) and one that would fail here (greedy initialization??).
Can someone suggest a source where I could read more about different possible optimizations of Kuhn's algorithm depending on which assumptions are valid about our input graph? I searched around a bit but was not able to quickly find a good source or library code.
1728G — Illumination can also be solved using dp in $$$(n + q) * m ^ 2$$$ complexity. Here's my submission.