Tutorial
Tutorial is loading...
Solution
#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;
int ans = 0;
for (int i = 0, x; i < n; ++i) {
cin >> x;
ans |= x;
}
cout << ans << endl;
}
}
Tutorial
Tutorial is loading...
Solution
#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);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
for (int i = 1; i + 1 < n; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
if (i + 2 < n) {
a[i + 1] = max(a[i], a[i + 2]);
} else {
a[i + 1] = a[i];
}
ans++;
}
}
cout << ans << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << " \n"[i == n - 1];
}
}
}
Tutorial
Tutorial is loading...
Solution
#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);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (a[n - 2] > a[n - 1]) {
cout << -1 << endl;
} else {
if (a[n - 1] < 0) {
if (is_sorted(a.begin(), a.end())) {
cout << 0 << endl;
} else {
cout << -1 << endl;
}
} else {
cout << n - 2 << endl;
for (int i = 1; i <= n - 2; ++i) {
cout << i << ' ' << n - 1 << ' ' << n << endl;
}
}
}
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, p;
cin >> n >> p;
vector <int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
set <int> useful;
for (int i = 0; i < n; ++i) {
int x = a[i];
bool flag = false;
while (x > 0) {
if (useful.count(x)) {
flag = true;
}
if (x & 1) {
x >>= 1;
} else if (x & 3) {
break;
} else {
x >>= 2;
}
}
if (!flag)
useful.insert(a[i]);
}
vector <int> cnt(30, 0), dp(p);
for (int x : useful) {
cnt[__lg(x)]++;
}
int ans = 0;
for (int i = 0; i < p; ++i) {
if (i < 30) {
dp[i] = cnt[i];
}
if (i >= 1) {
dp[i] += dp[i - 1];
if (dp[i] >= mod) {
dp[i] -= mod;
}
}
if (i >= 2) {
dp[i] += dp[i - 2];
if (dp[i] >= mod) {
dp[i] -= mod;
}
}
ans += dp[i];
if (ans >= mod) {
ans -= mod;
}
}
cout << ans << endl;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
struct edge {
int type, u, v;
};
vector <int> adj[N];
int col[N], topo[N];
void dfs(int v) {
for (int u : adj[v]) if (col[u] == -1) {
col[u] = col[v] ^ 1;
dfs(u);
}
}
bool BipartiteColoring(int n) {
for (int i = 1; i <= n; ++i)
col[i] = -1;
for (int i = 1; i <= n; ++i) if (col[i] == -1) {
col[i] = 0;
dfs(i);
}
for (int i = 1; i <= n; ++i) for (int j : adj[i]) {
if (col[i] == col[j]) {
return false;
}
}
return true;
}
bool TopologicalSort(int n) {
vector <int> in(n + 1, 0);
for (int i = 1; i <= n; ++i) for (int j : adj[i]) {
in[j]++;
}
queue <int> q;
for (int i = 1; i <= n; ++i) if (in[i] == 0) {
q.push(i);
}
int ord = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
topo[v] = ord++;
for (int u : adj[v]) {
in[u]--;
if (in[u] == 0) {
q.push(u);
}
}
}
return ord == n;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <edge> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i].type >> a[i].u >> a[i].v;
adj[a[i].u].push_back(a[i].v);
adj[a[i].v].push_back(a[i].u);
}
if (!BipartiteColoring(n)) {
cout << "NO" << endl;
return 0;
}
// col = 0 -> orient left, col = 1 -> orient right
for (int i = 1; i <= n; ++i) {
adj[i].clear();
}
for (edge e : a) {
if (col[e.u] == 1)
swap(e.u, e.v);
if (e.type == 1) {
adj[e.u].push_back(e.v);
} else {
adj[e.v].push_back(e.u);
}
}
if (!TopologicalSort(n)) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = 1; i <= n; ++i) {
cout << (col[i] == 0 ? "L " : "R ") << topo[i] << endl;
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
const long long INF = 1ll << 62;
vector <int> useful_pair[N];
vector <pair <int, int>> queries[N];
long long bit[N];
void modify(int p, long long v) {
for (int i = p; i > 0; i -= i & (-i)) {
bit[i] = min(bit[i], v);
}
}
long long query(int p) {
long long ans = INF;
for (int i = p; i < N; i += i & (-i)) {
ans = min(ans, bit[i]);
}
return ans;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector <int> x(n), w(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> w[i];
}
for (int i = 0, l, r; i < q; ++i) {
cin >> l >> r, --l;
queries[r].emplace_back(l, i);
}
stack <int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && w[stk.top()] > w[i]) {
stk.pop();
}
if (!stk.empty()) {
int x = stk.top();
useful_pair[i].push_back(x);
}
stk.push(i);
}
while (!stk.empty()) {
stk.pop();
}
for (int i = n - 1; ~i; --i) {
while (!stk.empty() && w[stk.top()] > w[i]) {
stk.pop();
}
if (!stk.empty()) {
int x = stk.top();
useful_pair[x].push_back(i);
}
stk.push(i);
}
fill(bit, bit + N, INF);
vector <long long> ans(q);
for (int r = 1; r <= n; ++r) {
for (int l : useful_pair[r - 1]) {
long long val = 1ll * (x[r - 1] - x[l]) * (w[l] + w[r - 1]);
modify(l + 1, val);
}
for (auto [l, id] : queries[r]) {
ans[id] = query(l + 1);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << endl;
}
}
Thanks for your interesting round.
Wow, ratings updated super quick.
Thanks for the fast editorial. D was the most interesting problem for me.
Its a broken problem something feels off about it Observation was thrown forcefully into problem Anyway broken problems are always intresting I think this problem belongs to category where one needs to think what was question expecting and what could be possibily be used rather than searching for observations. I mean one knows what question is expecting there is literally no observation/blockers when one tries to solve problem ? The whole problem relies on single fact that you took a right direction
LIGHTNING EDITORIAL
THANK YOU SO MUCH FOR PROVIDING THE ROUND!
thanks for good problems and fast editorial !
can anyone please tell me why this is wrong?problem -C
if the last element is negative then the answer must be -1.
yup, I am checking that here
because it is also possible that the array is already sorted
if second last element is nonnegative and the last element is negative then the answer still remains -1 if the array is not already sorted but your code does not seem to be able to handle that.
I am also handling that case here
I ran your code for this test case.
Your code gave -1 as output but this array can be made non decreasing with 1,2,3 as x,y,z
Here you are checking as strictly more than 0 but you should be doing >= 0. I changed this part and submitted your code it gives AC.
Thanks a lot for your efforts.
Was A harder than normal for a lot of people?
Maybe yes, for some people. But A is easy for usually people.
What is the intuition behind this and why it can helps the new dp value?
(Problem D editorial)
Example array $$$a$$$ has 9, but 4 isn't belong $$$S$$$ you need count 9 and $$$2^3 <= 8 < 2^4$$$ so 9 counts in $$$dp[4]$$$.
+1
It feels like there's no way of coming up with the editorial solution. It uses some arbitrarily defined function that somehow happens to be ans to the problem. I feel there's some other intuitive solution that I'm missing but if this is the expected solution then that's pretty terrible problem.
I thought of it this way,
Multiplying by 4 means adding "00" to the end of binary representation of $$$x$$$ and doing $$$2x+1$$$ is adding "1" to the binary representation of $$$x$$$. So now you have some strings and you can either append two zeroes or a single one to them. The number of such strings is $$$fibonacci(p-size(x))$$$, where $$$size(x)$$$ is the number of digits in binary representation of $$$x$$$. With this approach, we can also see how some other element is a "parent" of $$$x$$$.
The number of such strings is fibonacci(p — size(x)).
What is "p" over here and can you elaborate a little more on how the count is fibonacci(p — size(x)) ? Thank you
Suppose you want to find number of strings of size $$$n$$$, then you can either add "00" to the end of all strings of size $$$n-2$$$ or add a "1" to all strings of size $$$n-1$$$. This shows that $$$f(n) = f(n-1) + f(n-2)$$$
$$$p$$$ is given in problem statement
That's a very interesting way to think of it.
I think the tutorial is trying to explain things in a concise way but somehow also loses intuitiveness. Here's how I solved the problem.
Observation I: Make the number binary. Then the problem will be like given a bunch of number, how much number under $$$p$$$ can be reached by adding a
1or00at the back of those given numbers.Observation II: If a number $$$a$$$ can be reached from another number $$$b$$$, than a is useless because all number that a can reach can also be reached by $$$b$$$. Thus, we only take $$$b$$$ into consider.
Observation III: If $$$a$$$ and $$$b$$$ cannot reach each other, than any number can only be reached by at most one of them.
So, after we deleted all the 'useless' values, it's just solve for every number ad add the result together. And that's some simple DP from there.
Hope this helps.
Can you prove the observation III. Thanks
If we look at the binary representation of $$$a$$$ and $$$b$$$, $$$a$$$ can reach $$$b$$$ iff $$$a$$$ is a prefix of $$$b$$$. So if $$$c$$$ is reachable by $$$a$$$ and $$$b$$$, $$$a$$$ and $$$b$$$ must both be suffixes of $$$c$$$, since $$$a \neq b$$$, one must be a suffix of another.
Co-authored by 8e7.
Could anyone help with my problem D submission? Submission
I basically used the fact that if one number can't directly be reached by another, all their children will be distinct. Submission passes the given pretests.
My implementation is quite the same with yours and I also get wrong answer on the same test
But so far haven't found the explanation why
try
2 3
3 4
the possible numbers are 3, 4 and 7(3*2+1) but your solution says it is 2, which is wrong
Thanks to The-Winner for giving small counterexample.
I messed up when it comes to considering which numbers are useless or not. What I was doing was finding the 'root' of each number where the root was the smallest number which could create it in the set S. Then I said that if some numbers have the same root, we take the minimum of these and the others are all useless. This is sadly not true, I would have to find all useless numbers in the same way as the tutorial.
My algorithm for C was the exact same, but instead of using the last 2 elements and the current element, I used the last element, the current minimum, and the current element. Why does this not work?
I also used last element, current minimum and current element. I could pass all tests after contest ended. Submission
same solution, same wrong on test 2, Why does this not work?
I think you might have forgotten an important equals sign.
in the editorial of the problem A Since, a1|a2|⋯|an≤a1+a2+⋯+an, the sum of the array has a lower bound of m why this statement is true and how did they arrive at this result
If you have two numbers, taking their sum will make bits that are the same 'carry', but taking their bitwise OR won't. For example if you have $$$10_2$$$ and $$$10_2$$$, the sum will be $$$100_2$$$, but the OR will still be $$$10_2$$$. I'm sure there's a rigorous proof somewhere but this is how I came up with the observation.
Are the recent contests tough or I lack practice? I'm clearly having a hard time solving questions nowadays.
I think as time progresses, people tend to become bored of older problems, which start becoming 'standard' problems. So in order to make the problem 'interesting', the authors tend to add some ad-hoc observations. Sometimes, these observations are cool to think about (I find the problems that can be converted to some graph problems interesting), while some become just arbitrary 'meh, cool whatever' (binary string problems for me). So have the problems become harder? Yes somewhat since many times you have to also think about what the author is trying to make u do, and which you can't do all the time.
Recent problems (like last ~10 contests) are more mathematically and more observation based than before.
I have seen people saying this for last 2 years
For me it feels like the opposite. Recent contests are more implemenatation heavy and less idea-oriented than a bit older ones(like autumn and older)
Can someone explain the proof of A like I am 5 ?
I don't think the $$$|a_x|$$$ in pC can reach $$$10^{18}$$$, it should grow in $$$O(n)$$$. Although I cannot give strict proof, I can say that the testers fear it happened. By asking them, as a friend...
Update, I'm wrong, abc864197532 does have code to hack it. \abcorz/
The operation is like
(-2b) (-b) (a - b) a bfor problem B
..but the optimal way is to set ai+1 to max(ai+1,ai+2)..i think it should be..but the optimal way is to set ai+1 to max(ai,ai+2)..Sorry, we will fix it later.
how would you rate c problem?
I think <=1300
can anyone tell why it says array not sorted after all operations in this -https://codeforces.com/contest/1635/submission/147096553
You can click on the link there to see which test case failed: In the link you provided, there is a line at the end which says "Click to see test details".
Thanks to codeforces for this round
Problem D can be approached by considering all numbers to be binary strings. We can see that the two operations then look something like this: 2x+1 is equivalent to appending 1 to the binary string, 4x is equivalent to appending 00 to the binary string. Its still important to ignore the useless numbers from the array, useless means those who can be generated by elements already present in the array. One we have an element (a[i]) from the array which is usefull we need to append some bits and make it a string of no more than p characters, so we can subtract length of a[i] from p and that will give us the free places to work on. We can append string of length 0, 1, 2.... p-len to the end and that will give us new numbers everytime. So we can count the number of strings of length 0, 1, 2, 3...p made up of 00 and 1 and then add all possible strings of length atmost p-len, Prefix sum can optimize this operation.
Here is my code for the same, hope it helps someone: 147075092
can u explain this line "2x+1 is equivalent to appending 1 to the binary string, 4x is equivalent to appending 00 to the binary string".
2x+1 = x<<1+1 4x = x<<2
<< Is binary left shift operator
Take any random x say x=22 (10110) 2x+1 = 45 (101101) 4x = 88 (1011000)
thanks bro
Thanks! This is helpful!
anandsaurabh46 can you please explain your below code ->
for(ll i=2; i<=p; i++) {
dp[i] = (dp[i-1]+dp[i-2])%mod; } for(ll i=1; i<=p; i++) { dp[i] = (dp[i-1]+dp[i])%mod; }And also why dp[0] = 1, as in fibonacci fib[0] = 0 and why you have written dp function two times?? Can you explain it clearly Will be very helpful.
The recurrence relation here is same as in fibonacci, but this problem has got to do nothing with fibonacci series. The reason dp[0] = 1 is that, for a string of length 0, we have 1 possible option that is empty string.
for(ll i=2; i<=p; i++) { dp[i] = (dp[i-1]+dp[i-2])%mod; }
This code is for prefix sum, because we want the count of all possible strings of length atmost x, so we will sum dp[0]+dp[1]+dp[2]....dp[x], so to optimize this operation, we can take dp[x] to be sum of all dp values from 0 to x.
anandsaurabh46 Ok now I understood, Thank you very much for your explanation and blazing fast reply. It actually really helps to understand things more clearly .
Hi anandsaurabh46, the below code, adding dp[i-1] second time:
We already added dp[i-1] once:
could you please tell why dp[i-1] is being added twice? Thanks!
Got it, first DP loop is computing possible string permutations for just ith length, the second loop is for counting all possible string permutations from 0th to ith length... Anyway thanks for the different solution approach!
Exactly!
I've solved only one problem during contest, but my overall rating got lower, why ?
Well, I guess you answered your own question, you solved only one problem.
But I've been thinking that for the 1st problem I must get from 260 to 500 scores. for the 2nd 1000, etc, depending on time and attempts.
As far as I know your new rating is a function of overall standings, not the scores you obtain on a problem. The higher number of problems solved facilitates that but can not ensure it if many people are able to solve it before you.
OK. My rating before contest was 1089, after the contest it become 1004 (-89). What should I do or how many problems I must solve during contest to make rating go up ?
What does the scores of the problems determine ? I've solved the first problem and got 438scores. But it gave -89.
There's a nice chrome extension cf-predictor. It tells you in real-time what your rating would be if your current standing is your final standing. You can use that. The score you obtain on a problem adds to your total score and your total score determines your rank which further determines your rating change. There is no hard rule of rating change on solving a certain number of problems, it's all relative scoring. For more info refer this blog
Your rating change will be calculated based on your postion in the standings table, your rating and the rating of the other partitipants. Actually each rating point one looses is a won rating point for somebody else.
The contest score doesn't directly determine your rating. The scores are used to rank you with other participants. Based on previous rating you'll be given an expected rank. If your actual rank is better than expected rank your rating goes up otherwise it goes down.
Hey, in editorial of B, ceil value should be used and not floor.
Thanks, we'll fix it.
What rating range should problems B and C be?
B = 800-1000 C = 1100-1300
A very well balanced contest,, Loved it..
Problem D with $$$p \le 10^9$$$ is also solvable.
For each "useful number" $$$u$$$, if $$$2^{k-1} \le u < 2^k$$$, we can generate $$$F_1+F_2+\dots+F_{p-k+1}$$$ elements ($$$F_i$$$ is $$$i$$$-th Fibonacci Number, begin with $$$F_1=1,F_2=1,F_3=2,...$$$) from $$$u$$$.
It is satisfied that $$$F_1+F_2+...+F_r = (F_3-F_2)+(F_4-F_3)+...+(F_{r+2}-F_{r+1}) = F_{r+2}-1$$$ , so we can just sum up it.
Time Complexity: $$$+N \log p$$$ instead of $$$+p$$$ in the editorial
code: 147068110
How do you calculate F_(r+2) in log r?
Matrix exponentiation is a common way, maybe this video is useful?
I'll watch it. Thank you!
When I suggested this problem to dannyboy20031204, the limit for $$$p$$$ was $$$10^9$$$. However, it was judged that matrix multiplication was too difficult for a div2 D problem :v I think that in the end, the value of $$$p$$$ doesn't really matter because the observations are all somewhere else.
My solution to A seems to be a little different. I used the observation that for two integers x and y, to make sum as small as possible and at the same time not changing x OR y, you need to remove a 1 bit for every position that the bit is 1 in both x and y. This is equivalent to removing x AND y
Do this for all pairs and the answer is the total sum: Submission
Good Round
The solution of F is so wise!
I like the problem F!
Thanks! <3
147064757 any one please tell me why this
puts("0")doesn't work...I don't understand why. what I've written is the same as you. but I got AC:147131885
Checker comment wrong answer Integer parameter [name=k] equals to 5, violates the range [1, 4] (test case 4)
Edit: Commenting out "IOS" will work though.
Cannot use:
when mixing C and C++ I/O.
thanks a lot!!!
I have a different approach for problem $$$D$$$.
Consider a value $$$x$$$. We have a set of possible values $$$< 2^p$$$ which we must include if we include $$$x$$$. For example, we must include $$$2x + 1$$$ and $$$4x$$$. Call these set of values $$$S(x)$$$. Using this notation, the problem wants us to find $$$\cup_i S(a_i)$$$.
How can we examine $$$S(x)$$$? It's much easier if you consider it in binary — consider a binary string $$$s$$$ which represents some value $$$x$$$ in base $$$2$$$. $$$2x + 1$$$ appends a $$$1$$$ and $$$4x$$$ appends two zeroes. Therefore, if we start at some string $$$s$$$, we have to include anything that can be reached by adding "1" and "00" some number of times. For example, if we have some string $$$5$$$ or $$$101$$$ and $$$p = 6$$$, then we can have $$$101\mathbf{001}, 101\mathbf{111}, 101\mathbf{100}$$$.
Notice that the size of $$$S(x)$$$ is $$$F[p - \lfloor \log_2 (x) \rfloor] - 1$$$, where $$$F$$$ is the Fibonacci numbers. The reason we have that floor log2 expression is because some prefix of our string is fixed (in the previous example, our string length is $$$3$$$).
Task: Count the number of strings of size $$$n$$$ which are compositions of "00" and "1". Result: Answer if $$$F[n]$$$, easy to prove. (Convince yourself via recurrence relation)
Task: $$$\sum_{i = 0}^n F_i = F_{n + 1} - 1$$$. Proof: Easy. Just use induction.
But why isn't our answer the sum of sizes of $$$S(x)$$$? The answer is simple — we could have overlaps. Consider $$$100$$$ and $$$1\mathbf{00}$$$ for instance. In particular, we have overlap between binary strings $$$s_1$$$ and $$$s_2$$$ iff there is a way to reach each other via adding only "00" and "1". On naive approach is to brute force $$$\mathcal{O}(N^2)$$$ for each pair of binary strings and check if they can be reached from each other.
But there's a better way. Notice that two strings can only be reached via each other iff one of them is the prefix of the other (say $$$s_1$$$ is a prefix of $$$s_2$$$). Since we know that the numbers are small (at most $$$25$$$ bits), $$$|s_2| \le 25$$$, so we can iterate over all prefixes of $$$s_2$$$ and check if they have some match in the array. Only if they do, check if they can be reached via some sequence of moves.
How to check if they can be reached via some sequence of moves? One simple way is to ensure that each contiguous block of zeroes has even length. There are other ways too, like with a stack.
147131385
Note: Some constant factor optimizations can be made to my solution, but it still generously runs within the time limit.
Cheers!
thanks, it helps me a lot.
How did you come up with this solution during the contest ? i'm finding it easier to understand than the dp one but more complex to come up with
In problem D why is dp[0] initialized to 1 ?
For the initial term, when you haven't applied any operation.
Getting WA on TC 5 in Problem D 147139694 Can anyone please point out my mistake?
You are making an error while checking whether a[i] can reach some previous array value. You are independently doing the operations num/4 and (num-1)/2. However these 2 operations can be combined.
For example, consider the array {3,25}.
3*4 -> 12, 12 -> 2*12+1 = 25. However, your code doesn't take this case into account.
Thank you!
The bug is here.
You are checking separately for condition 2x+1 and 4x. Here is my AC approach.
First time giving a competition.Could not solve any one of the problems.I am Slowly working through editorials.
ProblemA, Sample TestCase : 5.
Can anyone please provide a way to achieve
7for3 5 6?3 5 6
We replace 3 5 whose or is 7 with 7 0 whose or is also seven Now we have 7 0 6 We replace 7 6 with 7 0 because both or are 7 We have now 7 0 0 The sum is 7 Sorry for the poor English
I made video Solutions (for A-E) in case someone is interested.
What can be the cause of getting WA 9 in E? 147171369
Failing testcase: Ticket-462
How to solve Problem C if we need to minimize the number of operations
Can someone explain
This is actually a classic problem, which could be solved by sweep line trick + any data structure able to maintain prefix-minimum with single point updates, like BIT or segment tree.I am not able to understand the implementation in the solution as well.Is this some standard algorithm?The sweep line trick is an offline method. We'll sort the segments in the decreasing order of their left endpoints, and add them one by one to your data structure. After adding all segments whose left endpoints are not less than $$$i$$$, we can find the answer for those query $$$j$$$ with $$$l_j = i$$$, which is equalvance to the minimum segment whose right endpoint are smaller than $$$r_j$$$ currently. Btw, the data structure you need is segment tree or sth.
I think the solution is actually maintaining a suffix minimum, and his BIT implementation is just the opposite of the prefix one that I know.
Well, that is because in my implementation, I sort the segments in the increasing order of their right endpoints. This way I'll need to maintain the suffix minimum. It doesn't matter a lot since the basic idea is still sweep line.
The solution is amazing! I didn’t know that BIT can maintain suffix lol
Hi, can a programming god help me figure out why my D is getting WA on test case 5? I basically eliminate the useless numbers, and then do some fib dp to find the answer. https://pastebin.com/ARt4ESMf
Runtime Error
Hey! Thanks for the response. I've changed the code to account for that test case, but the answer is still wrong. https://pastebin.com/caQFEtC1
Runtime Error
Hey, for that input, my code actually gets the expected output.
My bad, I actually meant to type this testcase:
5
Thank you, it worked! How do you think of these test cases so quickly? I spent forever debugging yesterday.
Well, I cheated. And the secret is, CF Stress :)
I have not yet added Java support in the deployed version, but I do have Java support locally, with some workarounds. Hence I was able to come up with a counter example in less than a minute.
I have a question about the solution of problem d, regarding control flow
Doesn't
x & 3implyx & 1? Or shouldx & 3be replaced withx % 3? I don't understand why x is not useful ifx & 3. Could someone explain it for me?Thank you so much in advance
If the last two bit of the binary representation of x is
00, we need to continue finding possible parents. But if the last two bit is10, we need to stop finding since the operation is * 4 and there are no parents that can generate it.So in my implementation, I use
x & 3to check whether the second last bit is1or not. It can be replaced withx % 4orx & 2. The latter is because I have checked the last bit is0.if I do arr[i+1] = max(arr) in 1635B — Avoid Local Maximums, why it would not pass pretest2 ?
Here is the hack test:
Your solution will modify two numbers, but it's optimal to replace the third number with 3.
I think there is an important point to notice for Problem D: in
dp[i] = dp[i - 1] + dp[i - 2], what ifdp[i - 1]anddp[i - 2]contribute to duplicate numbers indp[i]? Fortunately, this will not happen becausedp[i - 1]only generate odd numbers indp[i], anddp[i - 2]only generate even numbers indp[i].For problem D, how are we so sure that two numbers that are not related (i.e., one is not a parent of another) cannot generate the same number some steps later?