Idea: Roms
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
a = input()
b = input()
c = input()
print("YES" if any([a[i] != c[i] and b[i] != c[i] for i in range(n)]) else "NO")
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
int t;
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
map<int, int> numOfLens;
for (int i = 0; i < n; ++i){
int x;
cin >> x;
++numOfLens[x];
}
long long res = 0;
int sum = 0;
for (auto it : numOfLens) {
long long cnt = it.second;
if(cnt >= 3)
res += cnt * (cnt - 1) * (cnt - 2) / 6;
if(cnt >= 2)
res += cnt * (cnt - 1) / 2 * sum;
sum += cnt;
}
cout << res << endl;
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 200'000;
const int INF = 1'000'000'009;
int t;
char type(const vector <int>& a, int id) {
int distL = (id == 0? INF : a[id] - a[id - 1]);
int distR = (id + 1 == a.size()? INF : a[id + 1] - a[id]);
if(distL < distR) return 'L';
if(distL > distR) return 'R';
assert(false);
}
int main() {
ios::sync_with_stdio(false);
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
vector <int> l(n), r(n);
for (int i = 1; i < n; ++i)
r[i] = r[i - 1] + (type(a, i - 1) == 'R'? 1 : a[i] - a[i - 1]);
for (int i = n - 2; i >= 0; --i)
l[i] = l[i + 1] + (type(a, i + 1) == 'L'? 1 : a[i + 1] - a[i]);
int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
if (x < y)
cout << r[y] - r[x] << endl;
else
cout << l[y] - l[x] << endl;
}
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n + 2), d(n + 2, INT_MAX);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> d[i];
set<int> lft, cur;
for (int i = 0; i < n + 2; ++i) {
lft.insert(i);
cur.insert(i);
}
for (int z = 0; z < n; ++z) {
set<int> del, ncur;
for (int i : cur) {
auto it = lft.find(i);
if (it == lft.end()) continue;
int prv = *prev(it);
int nxt = *next(it);
if (a[prv] + a[nxt] > d[i]) {
del.insert(i);
ncur.insert(prv);
ncur.insert(nxt);
}
}
cout << del.size() << ' ';
for (auto it : del) lft.erase(it);
cur = ncur;
}
cout << '\n';
}
}
1922E - Increasing Subsequences
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
vector<int> f(long long x) {
vector<int> res;
if (x == 2) {
res.push_back(0);
} else if (x & 1) {
res = f(x - 1);
res.push_back(*min_element(res.begin(), res.end()) - 1);
} else {
res = f(x / 2);
res.push_back(*max_element(res.begin(), res.end()) + 1);
}
return res;
}
int main() {
int t;
cin >> t;
while (t--) {
long long x;
cin >> x;
auto ans = f(x);
cout << ans.size() << '\n';
for (int i : ans) cout << i << ' ';
cout << '\n';
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 111;
int n, k;
int a[N];
int nxtx[N][N], prvx[N][N];
int nxtnx[N][N], prvnx[N][N];
int dp1[N][N][N], dp2[N][N][N];
int calc2(int, int, int);
int calc1(int l, int r, int x) {
l = nxtnx[l][x], r = prvnx[r][x];
if (l > r) return 0;
if (dp1[l][r][x] != -1) return dp1[l][r][x];
dp1[l][r][x] = calc2(l, r, x) + 1;
for (int i = l; i < r; ++i) dp1[l][r][x] = min(dp1[l][r][x], calc1(l, i, x) + calc1(i + 1, r, x));
return dp1[l][r][x];
}
int calc2(int l, int r, int x) {
l = nxtx[l][x], r = prvx[r][x];
if (l > r) return 0;
if (dp2[l][r][x] != -1) return dp2[l][r][x];
dp2[l][r][x] = n;
for (int i = l; i < r; ++i) dp2[l][r][x] = min(dp2[l][r][x], calc2(l, i, x) + calc2(i + 1, r, x));
for (int y = 0; y < k; ++y) if (x != y) dp2[l][r][x] = min(dp2[l][r][x], calc1(l, r, y));
return dp2[l][r][x];
}
void solve() {
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i], --a[i];
for (int x = 0; x < k; ++x) prvx[0][x] = prvnx[0][x] = -1;
for (int i = 0; i < n; ++i) {
prvx[i][a[i]] = i;
for (int x = 0; x < k; ++x) prvx[i + 1][x] = prvx[i][x];
for (int x = 0; x < k; ++x) if (x != a[i]) prvnx[i][x] = i;
for (int x = 0; x < k; ++x) prvnx[i + 1][x] = prvnx[i][x];
}
for (int x = 0; x < k; ++x) nxtx[n][x] = nxtnx[n][x] = n;
for (int i = n - 1; i >= 0; --i) {
for (int x = 0; x < k; ++x) nxtx[i][x] = nxtx[i + 1][x];
nxtx[i][a[i]] = i;
for (int x = 0; x < k; ++x) nxtnx[i][x] = nxtnx[i + 1][x];
for (int x = 0; x < k; ++x) if (x != a[i]) nxtnx[i][x] = i;
}
memset(dp1, -1, sizeof(dp1));
memset(dp2, -1, sizeof(dp2));
int ans = n;
for (int x = 0; x < k; ++x) ans = min(ans, calc1(0, n - 1, x));
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
If using a double linked list to implement 1922D, we can get a solution of O(n) time.
I created array for storing right & left alive monster
I wrote a similar solution but using sets was so elegant!
Bro I messed up and used both set and double linked list. Can you tag your solution for me to view. I just wrote a bunch of code and somehow got AC.
D.Berserk Monsters Code
check it out, may be helpful.
Why is my code giving 'Wrong answer on Test 1' ? Literally copied the editorial , but still getting this . 290517792
We can do 1922B - Forming Triangles without binomial coefficient. 242267553 We can assume that the three sides chosen by us are (2^x,2^(x+d1),2^(x+d1+d2)) d1, d2 ≥ 0. Our triangle must meet these conditions 2^x + 2^(x+d1) > 2^(x+d1+d2). In the other way, sum of two minimum must be greater than maximum one.
nice
Can you explain more about your code? I was unable to understand it.
that is almost same idea with the idea in editorial but it's like dp observation form of it
In problem E we could also construct an increasing sequence
1, 2, 3, ..., N
. We could easily see that it hasS = 2^N
increasing subsequences (including the empty one).If
S*2
equalsX
, we just need to addN+1
at the end, else we need to add some values to getX-S
more increasing subsequences.Notice that if we add a value
1 <= v <= N
to the end of the sequence, we would get2^(v-1)
more increasing subsequences, so we just need to check each bit from MSB to LSB.Submission: 242459743
Thanks!!!.
I used this method in the contest
This was very helpful. Thank you
I thought of the same approach. But, I am getting first test case wrong on system test 6.
For 905093722480139348, your code returns:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 56 52 51 50 49 48 44 41 40 39 38 37 33 32 31 30 29 28 24 23 21 20 19 17 15 13 12 11 7 5 3
The largest number is 59, so according to your logic it should be 2^59. The remaining numbers:
59 56 52 51 50 49 48 44 41 40 39 38 37 33 32 31 30 29 28 24 23 21 20 19 17 15 13 12 11 7 5 3
Should be 2^(v-1), which when I calculate turns out to sum with 2^59 as 905093722480139264. What am I doing wrong?
This is the code I used to test:
My submission num (Java): 242767859
Change the line
sm += pow(2LL, ar[i]-1);
tosm += (ll)pow(2LL, ar[i]-1);
and it should produce the correct result. In C++ thepow
function returndouble
typed value, addingdouble
in that range may give some miscalculation, I don't know much about Java but it could also be the same issue.For problem B, I got accepted in the contest, but then I woke up this morning and got Time Limit Exceeded on Test case 6? I'm so confused why did this happen. I was supposed to hit expert.
That's because someone made this test case to hack some code and succeeded during the hack phase, and these successful hacks were added to the system tests, which were used to judge the final results.
Such rules are described in this blog: https://codeforces.me/blog/entry/21496
oh ok, my same solution translated to java (as opposed to my original python) somehow gets accepted. i'm very confused
In general,C++ is faster than java,and java is faster than Python.It has to do with the feature of each languages.
hell it s*cks man same happened to me! I think its about time that codeforces set different time limits for python and c++ for questions otherwise it seems like there's no point in having multiple languages
oh yea sorry to hear! I ended up passing in python after the contest by simply not using a dictionary and instead using an array. i think it is because dictionary is only O(1) access on average so i guess that adversarial test case made all the values in the array hash to the same slot or smth. that's evil haha
yeah true
Problem F can also be solved in $$$O((n^3 \cdot x)/64))$$$ using bitsets: link
Note that since $$$x$$$ is at most $$$100$$$, we can simply use 128 bit integers instead of bitsets for an even better constant factor.
I'm very confused by the editorial for E, so I feel like sharing my own (AC) approach:
First, observe that a strictly increasing array with $$$k$$$ elements will have $$$2^k$$$ increasing subsequences (including the empty subsequence), the elements to be removed can be any subset of all the elements. So for input $$$n$$$, we can find the largest power of 2 which is $$$\leq n$$$, e.g., for integer $$$p$$$ such that $$$2^p \leq n < 2^{p + 1}$$$, we can form an increasing array of $$$p$$$ elements to create $$$2^p$$$ subsequences (including the empty subsequence).
But what about the remaining $$$n - 2^p$$$ subsequences? Let's say the largest power of 2 you can fit in the remaining value is $$$2^q$$$, i.e., $$$2^q \leq n - 2^p < 2^{q + 1}$$$. Initially, I considered creating a separate subarray of $$$q$$$ elements, but having to do this with every power in the worst-case (e.g., if $$$n = 2^{59} - 1$$$) would exceed the 200-length limit (and we also have to avoid double-counting the empty subsequences).
Instead, however, we can generate $$$2^q$$$ new increasing subsequences by adding only one element to the end of the array: an element which is greater than the first $$$q$$$ elements of the original sequence (of $$$p$$$ elements) but smaller than the rest. The new subsequences generated involve the new element with any subset of the first $$$q$$$ elements, resulting in $$$2^q$$$ new subsequences (there are no empty subsequences here, since the new element is always included in these new subsequences).
This leads to the following algorithm: for the highest power $$$p$$$ of 2 that fits (i.e., leftmost 1 bit), prepare $$$p$$$ elements in strictly increasing order. This is the primary reference sequence. Then for the next power $$$q$$$ of 2 that fits, e.g., we simply add one extra element to the end whose value is between the $$$q$$$-th and the $$$(q + 1)$$$-th element of the primary reference sequence. Repeat for each power of $$$q$$$ that fits from the remnants of the previous step.
My submission: 242314370. The variable
prm
denotes $$$p$$$, the length of the primary sequence. I used multiples of 1000 for the primary sequence. Some of the code details overcomplicated this by considering when we might have multiple instances of the same $$$q$$$ value, but this is unnecessary with clear-headed hindsight, since we're basically just going through all the 1-bits in the binary representation from left to right. The__builtin_clz(n)
function (count leading 0s) would likely have improved this, to quickly find the leftmost 1-bit each time.I was able to come up with something similar, but I thought there would be cases where overlaps would occur and didn't manage to come up with any way to resolve them. Your explanation provides oversight in my eyesight.
Thanks I am stuck with the part of compressing the length of array. I might be able to do it now.
My submission to E 242474581. I got long long overflow when I had (1ll<<i) for calculating power of 2s (Specifically at i=59). However, it did not overflow when I calculated poweroftwos by arithmetic (as in submission, the dp array).
Any suggestions why there was an overflow for (1<<i) case? 242470568
use (1LL<<i)
Yep, I've used 1ll in my wrong submission
Maybe your program may let
i
bigger than $$$64$$$ then it will cause an overflow. Check the variablei
to fix this.I checked it on a debugger and i=59 is where it overflowed. Also the same code where I substituted (1ll<<i) to poweroftwo(i) gave me an AC, weird behaviour
Because you increase
i
in either cases, so it may hit a value bigger than62
, and1ll<<63
overflows, so it return negative value and code outputs-1
.You can do
++i
if the condition istrue
or check ifi<63
before evaluating1ll<<i
.Here is the Accepted code
We can think of Problem-B in another way, we can assume that the three sides chosen by us are $$$(2^x, 2^{x+d_1}, 2^{x+d_1 + d_2})$$$ where $$$d_1, d_2 \geq 0$$$.
As mentioned in editorial in order to make a degenerate triangle we want $$$2^x + 2^{x + d_1} > 2^{x +d_1 + d_2}$$$ (Sum of two minimum is greater than maximum).
After simplfying above inequality we get $$$2^{d_1} \cdot (2^{d_2} - 1) < 1$$$, which is only possible when $$$d_2 = 0$$$, thus for each $$$a_i$$$ we just want to find out the number of $$$a_i's$$$ after it. As for the first side length i.e., $$$2^{x}$$$ it doesn't matter what we choose so our final answer is just $$$\sum_{i = 0}^{N - 1} i \cdot \text{count of}\ a_i\ \text{in range i + 1 to n - 1}$$$. (Note 0-indexing)
Here is my submission.
Same idea but as a pure DP, without precomputed numbers count: 242489424. State is number of triangles with current element $$$a_i$$$ as longest edge.
why this code give wrong answer forn D question 242491110
Okay, I understand where my code failed. Thank you.
Can anyone please explain how tester of E could have been written so that it checks the answer in polynomial time? I can't think of one.
let dp[i] be number of increasing subsequences ending at position i, then it's O(n^2) to check. If we use sorting+fenwick to find dp starting from the lowest value, then it's O(nlogn).
I've written a checker for myself while solving problem E. Here's how it works: — Iterate through the sequence from left to right, and compute how many subsequences end with this index, and we store this value in a bBST — We check which numbers are less than the current one in our bBST (so to the left), and add their values up, because for each of these subsequences we can append the current number to the end — Then we store this value + 1 (because this value itself is also a valid increasing subsequence) in the bBST — Finally, we add up all elements in the bBST and add 1, because an empty one is also valid Here's my implementation: https://pastebin.com/5RFbryrk
Using number of occurrences of number in every sequence and calculating all subsequences.
[1,2,3,4,5] -> 2*2*2*2*2 — 1 + 1
[1,1,2,2,2,3,4,5,5] -> 3*4*2*2*3 — 1 + 1
Is this correct ? Never mind
I feel like my D should get hacked. Can someone try? submission
why is my code for problem D 242468805 getting a time limit exceeded signal ? shouldn't it be faster than this approach using sets?
Consider the case in which only 1 monster dies every round. In that case you will iterate $$$(n + 1 - i)$$$ times in round-$$$i$$$, which makes you solution $$$O(n^2)$$$.
doesn't the approach provided here using tree also have to go through all the alive monsters for each of the round .Or have i misunderstood the solution provided here?
They only consider monsters who can die in next round. See the use of set
ncur
.For F, I feel like we don't need to precompute that much to eliminate cyclic dependencies. Instead, we consider two cases:
a[l]==k
: we calculatedp1[l][r][k]
fromdp1[l+1][r][k]
first, then calculatedp2[l][r][kk]
fromdp1[l][r][k]
, wherek!=kk
.a[l]!=k
: we calculatedp2[l][r][k]
fromdp2[l+1][r][k]
first, then calculatedp1[l][r][k]
fromdp2[l][r][k]
.In the solution to D, what does prev(it) return in case "it" is the iterator pointing to the first element in the set?
It points to the last element of container (here,
std::set
). Another example hereWow, problem E is so creative, revolutionary and original — learned a lot about bitwise operation from that one!!!!! What inspired you to create such a ground-breaking, intuitive and simply perfect problem???.?!!!!!!
can someone explain problem D. I don't understand why the problem setter's claim is valid.
Let's assume 3 monsters i-1, i, i+1 are alive after some round R. Then monster i will be be alive even after round R+1.
Because the neighbors of i are same before and after round R.
Thanks a lot! I misinterpreted the question. I thought d[i] behaves like health and gets decreased by a[i — 1] + a[i + 1] every round.
Hey, could someone explain how removeing cyclic dependencies in problem F works. Is there a general approche or can we only do this for this spezific problem. Thanks!
Can somebody explain why my solution is getting TLE'D on test 15 for problem D 242631259
https://codeforces.me/blog/entry/124890?#comment-1109137
In problem E, it is written that : If we add a new maximum to the end of the array, the number of increasing subsequences in the new array equals 2x (since the new element forms increasing subsequences with any other elements).
I think this is not well explained. In fact, if we have x increasing sequences, there are x-1 non-empty sequences and 1 empty sequence. When we add a new maximum, there will be x new non-empty increasing sequences (x-1 from the previous sequences and 1 sequence composed only of the new element). if we count again the empty sequence, the total will be (x-1) + x + 1 = 2x.
I'm getting Memory Limit Exceeded in test 5 of Problem E, why is it so?
can anyone help me with the claim that when only the particular element is dead the suitable candidates would be its Neighbours ? in problem D
BledDest The editorial solution for D problem is a little bit wrong in the case where our i in cur is equal to 0 then the nxt and prev values give us the garbage value this is working because of the summation of the garbage values is always less than INT_MAX, but if we use long long vector to store the attack and defense value than the garbage value given will also be long long which will exceed the INT_MAX value so then it will give wrong answer. sorry for my bad English.
It was already mentioned, sorry.
Why somebody solve F so quickly?
because it is a standard dp on ranges problem as long as you get the dp2 idea quickly. Their method of handling cyclic dependencies is very very unnecessary.
how did you handled the cyclic dependencies ?
Also I dont think it is that that bad , this was my solution after I read the editorial : https://codeforces.me/contest/1922/submission/242787688
As you can see the only thing I did to get rid of cyclic dependencies was adding the 2 lines of code at the beginning of the function :
Nonetheless I am still curious about how you handled because your approach is clearly faster than mine , and I couldnt really understand your logic from your submission
I shouldn't be able to understand problem F solution, why am I? :-)
can enyone help me with this problem? I am tring to solve it using Hash in c++ but can't
https://codeforces.me/contest/271/submission/243292259
Bigger prime for hash gets the job done.
243325452
Thank you!
Hello everyone, I am having some trouble with problem F. I solved it with the help of the code from Dominater069.
From what I understood. He did and I copied something like:
Now the part where the part 3 and part 4 just relies on each other I want a closure of why this is not in recursion or recurance. I tried solving it like Bellmanford where if the weights stop relaxing we stop the algorithm between step 3 and 4 and it will work but it doesn't even matter. I', interested in the doesn't matter part. Can someone prove it.
Thank you for reading my comment and special thanks if you can shed some light on it. Thanks everyone.
The second question was very nice problem!!
Surprised that the editorial lists an $$$O(n^4)$$$ for problem F, when it can be done in $$$O(n^3)$$$, also surprised that no one has mentioned it in the comments.
243829676
for D: why if the neighbors of $$$i$$$-th monster are alive we don't have to check the $$$i$$$-th in the next round? Isn't it possible that the neighbors to kill it in the next round? UPD: I thought the defense (d) is being decreased each round
Is there an issue with codeforces's compiler ? I used unordered_map and ordered map in B and got different results whereas got same results with COdechef's ide