Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int>a(n), ans;
int cnt0 = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (!a[i]) cnt0++;
}
int cnt1 = n - cnt0;
if (cnt0 >= n / 2) {
cout << cnt0 << '\n';
for (int i = 0; i < cnt0; i++) cout << 0 << ' ';
} else {
cout << cnt1 - cnt1 % 2 << '\n';
for (int i = 0; i < cnt1 - cnt1 % 2; i++) {
cout << 1 << ' ';
}
}
cout << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int a[n];
int mi = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
mi = (a[i] > a[mi] ? i : mi);
}
vector<int> b(n);
b[0] = a[mi]; a[mi] = 0;
int cg = b[0];
for (int i = 1; i < n; i++) {
int ci = 0, cans = 0;
for (int j = 0; j < n; j++)
if (a[j] && __gcd(a[j], cg) > cans) {
cans = __gcd(a[j], cg);
ci = j;
}
b[i] = a[ci];
cg = cans;
a[ci] = 0;
}
for (int i = 0; i < n; i++)
cout << b[i] << ' ';
cout << '\n';
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int ask(int x, int y) {
cout << "? " << x + 1 << ' ' << y + 1 << endl;
int z;
cin >> z;
return z;
}
int main() {
int n;
cin >> n;
vector<int>ans(n, -1);
int mx = 0;
for (int i = 1; i < n; i++) {
int a = ask(mx, i);
int b = ask(i, mx);
if (a > b) {
ans[mx] = a;
mx = i;
} else {
ans[i] = b;
}
}
ans[mx] = n;
cout << "! ";
for (int i = 0; i < n; i++) cout << ans[i] << ' ';
cout << endl;
return 0;
}
1407D — Discrete Centrifugal Jumps
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 1;
const int maxn = 3e5 + 1;
int h[maxn], dp[maxn], lge[maxn], lle[maxn], rge[maxn], rle[maxn];
vector<int>jumps[maxn];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> h[i];
dp[i] = INF;
}
dp[0] = 0;
vector<pair<int, int> >st;
for (int i = 0; i < n; i++) { // the nearest greater from the left
while (!st.empty() && st.back().first < h[i]) {
st.pop_back();
}
if (st.empty()) lge[i] = -1;
else lge[i] = st.back().second;
st.push_back({h[i], i});
}
st.clear();
for (int i = 0; i < n; i++) { // the nearest less from the left
while (!st.empty() && st.back().first > h[i]) {
st.pop_back();
}
if (st.empty()) lle[i] = -1;
else lle[i] = st.back().second;
st.push_back({h[i], i});
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // the nearest greater from the right
while (!st.empty() && st.back().first < h[i]) {
st.pop_back();
}
if (st.empty()) rge[i] = -1;
else rge[i] = st.back().second;
st.push_back({h[i], i});
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // the nearest less from the right
while (!st.empty() && st.back().first > h[i]) {
st.pop_back();
}
if (st.empty()) rle[i] = -1;
else rle[i] = st.back().second;
st.push_back({h[i], i});
}
st.clear();
for (int i = 0; i < n; i++) {
if (rle[i] != -1) jumps[i].push_back(rle[i]);
if (rge[i] != -1) jumps[i].push_back(rge[i]);
if (lle[i] != -1) jumps[lle[i]].push_back(i);
if (lge[i] != -1) jumps[lge[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
for (int to : jumps[i]) {
dp[to] = min(dp[to], dp[i] + 1);
}
}
cout << dp[n - 1];
return 0;
}
1407E — Egor in the Republic of Dagestan
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1;
vector<int> bg[maxn], rg[maxn];
int b[maxn], r[maxn], d[maxn], col[maxn];
int n, m;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, t;
cin >> u >> v >> t;
--u; --v;
if (!t) bg[v].push_back(u);
else rg[v].push_back(u);
}
for (int i = 0; i < n; i++)
d[i] = b[i] = r[i] = n;
queue<int> q;
q.push(n - 1);
d[n - 1] = r[n - 1] = b[n - 1] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto to : bg[x]) {
if (b[to] < n) continue;
b[to] = d[x] + 1;
if (max(b[to], r[to]) < n) {
q.push(to);
d[to] = max(b[to], r[to]);
}
}
for (auto to : rg[x]) {
if (r[to] < n) continue;
r[to] = d[x] + 1;
if (max(b[to], r[to]) < n) {
q.push(to);
d[to] = max(b[to], r[to]);
}
}
}
if (d[0] == n) cout << "-1\n";
else cout << d[0] << '\n';
for (int i = 0; i < n; i++) {
if (b[i] > r[i]) col[i] = 0;
else col[i] = 1;
cout << col[i];
}
return 0;
}
top 3 reason for depression
breakup
Substance Abuse
WA in div2 A
hahhahaha right bro
excuse me? Ahahahahahahahaha should be the reply
what rply?
ahahahahahaahahaha happy??
It's a joke, based on that the title of problem A is "(A)hahahahahahahaha"
Not a joke. It is called pun.
Any idea why my "Not a joke. It is called pun" comment got so many down votes?? I am confused.
Your comment seems fine to me. Let me know when you find out the reason.
Even that comment got so many downvotes. Apparently some people downvote for no reason.
yeah, it was like question is laughing on me on WA lol Ahahahahahahahaha
Ahahahahaha would be better ;-)
Hey bro,please help me with question A Link:https://codeforces.me/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
Dont spam, I answered your question
We're together (A)hahahaha
Hey bro,please help me with question A Link:https://codeforces.me/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
Dont spam, I answered your question
Ironic, you just did what you are saying not to do
For problem D, I didn't use DP at all. Instead, I build the graph of valid jumps and do BFS.
To build the graph, I process all values increasing by height, connecting a node to the first one it sees in the left and right directions that was processed earlier. This is just maintained with a set. Of course, I do this again but decreasing by height as well.
I tried doing the same but I think I missed cases where heights are same.
I am trying to do the same thing as you, the difference being, that I am using stack to maintain the next Smaller element's index and the Next_Greater_Elements index using stack ( Yes I am also keeping track of the equal elements as well )
Still, I am facing WA. It would be very nice, if you could help me figure out how will stack implementation fail.
I think I coded it out properly, but in case : MY Almost Clean STACK+BFS CODE
Your code fails at
7
4 6 1 7 3 6 5
answer should be 3, your code is showing 5.
how to correct it- after popping in while loop inside the for loop, you still have to check for last stack element without popping it
Dry run at above test case and you will know what is going wrong
Sorry, if this sounds stupid, but could you please elaborate a bit more on this.
I understood something with the test case you provided ( Thanks for that ).
So, the problem I guess is cases like —
3
10 20 15
My graph should have an edge between vertex number 1 and 3, but value[3] is neither the next greater, nor the next smaller element to value[1].
So, my graph won't have that edge. Hence, I decided to implement what you said, but now, I guess I placed some extra edges, due to which it fails on Case 8 (And note, my answer is smaller than the expected answer, means, somewhere I might have placed more edges, however I can't find the issue
I also thought, that you might have solved the problem successfully, with the same method, so I thought of giving your implementation a look, there I found you also had experimented on my code ( I would thank you again on that )
So, I decided to do something on your code as well. However, that fails on case 32 now
Please help, whenever you are free. Thanks : )
See this is my submission using exact same approach https://codeforces.me/contest/1407/submission/92349038
Your code now fails at
12
10 15 16 14 13 12 9 8 9 8 9 17
answer is 2, your code shows 3
its because while building graph, you are assuming that there can be one edge for greater condition and smaller condition, but there can be multiple edges
in your code instead of using nse or nge directly add edge when required
path is 10->13->17 (your code don't have edge 10->13)
but according to my understanding your code gives 10->15->16->17
Hey bro,Can you tell me what is wrong in my code.its problem B Link:https://codeforces.me/contest/1407/submission/92360694 Please help
Dont spam, I answered your question
I think you should find next greater&smaller element to both left and right, then add edges to the graph accordingly. If you find only from one side you will miss out on some valid jumps.
Thanks for the reply first of all, I understood your concern. Basically, my previous code would fail at cases like :
3
10 20 15
My graph should have an edge between vertex number 1 and 3, but value[3] is neither the next greater, nor the next smaller element to value[1].
So, my graph won't have that edge. Hence, I decided to implement what you said, but Sadly, that also fails, now on case 8
Yeah. I can see that you are adding edges undirected. But if you look at the problem statement it says that "Let's call a jump from i-th skyscraper to j-th (i<j) discrete", i.e you can't make a jump backwards.
For example.
Your solution would say the answer is 3, by making the moves 0 -> 4 -> 3 -> 7. Here the move 4 -> 3 is not valid since i > j.
The correct answer would be 4, by making the moves 0 -> 1 -> 2 -> 3 -> 7.
I hope this helps. Correct me If I got something wrong.
Edit: 92320227 Here is the link to my submission. I've done it using the same approach.
I don't even know, how much can I thank the Codeforces community. Sometimes, it feels, that it is only you, who is here, having all the troubles in the world, and sometimes, you get that proved so Wrong.
Thanks a lot aswwwanth and manpreet.singh
To Both, the test cases, and also, for finding time in looking at the code, and finding the bugs. I love u both.
Finally, I have managed to get AC. Yes, you are correct aswwwanth, that I was building the undirected edges, because of which, some path did come, which should not have been there. I removed the undirected edges, introduced the Directed edges, and it worked.
Also, for manpreet.singh, your test cases came handy. I understood the mistake of my code, through your test case only ( However, I am stupid enough to not correct it on my own ).
May God Bless you both !!!
For other people, who might get benefitted with the discussion, although a code has already been provided, still, another CODE might help you in case you are trying the stack approach !
I tried building the graph using Sparse Table and Binary Search, but ended up with Wrong Answer on test 5, It would be appriciated if someone could help me figure out what's wrong with my code or algorithm. Thank you in advance.
My submission: I tried to make it clean and concise
You need to add edges for previous high and low too.
eg 4 1 3 5 . . . only consider the 1st number 4. You'd add edge from 4->1 (getNextLow for 4) and 4->5 (getNextHigh for 4), but 4->3 is possible too. By repeating the same process from right to left the getPrevHigh for 3 would give us 4, so we add an edge from 4->3
I finally managed to get it Accepted, thanks a lot man!
ahahahaha.. so clever
I'm sorry, but what does the title signify in this case, I didn't get the title.
it shows 22hrs ago, contest was just few hrs ago, he edited another blog post most probably
No the editorial is made before, you can set the time when to make it public
After 1 hr of unsuccessful struggle on A, i saw the title.
I actually got "ahahahahad" in problem A after a struggle of 1 hour:/
A
t = int(input()) for _ in range(t): n = int(input()) l = map(int, input().split()) out = [] for _ in range(n//2): if next(l) + next(l) == 2: out.append(1) out.append(1) else: out.append(0) print(len(out)) print(' '.join(map(str,out)))
I know this is a succinct code or whatever, but ew.
It's okay, the guy is playing code golf here.
The constraints on task C were way too tight for no reason. I barely passed (with Java) in 997 ms after failing to 3 times.
Sorry, it's my fault. I've tried to make $$$n$$$ smaller instead of big time limit.
Don't worry. I think most of the time is not used by the "meat" of the program but rather just by the inputs and outputs and since it's an interactive problem you can't use fast I/O (u really cant for output, u probably can for input but i mostly prefer the slower method which can just take the next integer so you don't have to worry where the next line falls (which can be not so clear in interactive problems)). Just next time make the time constraints less tight in a problem where having a worse complexity of the program doesn't even help you solve it more easily.
whats ur fast io? i was able to fast io it
By fast io I just mean buffered reader. In the contest I just used scanner unfortunately and it didn't pass. Buffered reader passes but just barely.
oof is bufferedreader unable to interact? that's p unfortunate. if u want a fast io template that can interact i can dm u i got it from g4g iirc
Same thing with my submission. I was wondering if my O(nlogn) 92255144 was computationally expensive.
As a general suggestion, it will good to have coverage for all languages (especially Java and Python) in tester's solutions to understand time limits better.
BTW, nice question, I enjoyed solving it.
While your O(nlogn) solution should also be able to pass in my opinion, the thing is that I had an O(n) solution and it didn't pass.
EDIT: lol, it didn't pass the system test. After switching to fast input it passed in 982 ms.
rip. do u know why System.out.printf TLEs although System.out.println passes? Shouldn't printf be fast (like C++) compared to normal concatenation of integer and string?
You are flushing all the time so it isn't really important.
The editorial for D is too bad. Can anyone explain me, Thanks in advance.
The concept is just next_greater and next_smaller. Greedy Approach
Here is my solution. For every element, find: - The closest element to the left of that element that is <= than the element. - The closest element to the left of that element that is >= than the element. - The closest element to the right of that element that is <= than the element. - The closest element to the right of that element that is >= than the element.
Make a directed edge from the elements that you found to that element (smaller index to larger index). There are a maximum of 4 different nodes that you can find using that method, so there are max 4N edges.
Do a BFS or dp to find the shortest path from 1 to N.
why we need to consider the right side values?
I did the same mistake during the contest. Think about this:
You are considering the jump in which both ends are smaller than what is in-between them (case A).
By only drawing the back-edges (left) you are only jumping from a smaller building to a bigger one, like this: 4 7 9 6, but you might be missing out from jumping from a bigger building to a smaller one (still fitting the A-case!) 7 9 8 100 3
The following case fails:
n = 12
4 100 100 100 4 6 6 5 9 8 7 3
Here, the 12th node is "missing out", having no smaller values to its left. By putting only back-edges my answer would be 4, while also adding the front-edges the answer would become 2(1 -> 5 -> 12).
Thanks for this nice explanation.Now Understood clearly.
Why Can't we make A bidirectional edge instead ? I tried it, it gives WA. Though I don't understand the logic behind it ?
"i < j", you can only jump forward
But why are we considering only those paths?
We are considering all the paths I suppose.
got it thanks
These paths cover all possible paths. For each element, there is a maximum of four other nodes (1 for each type, and you can't possibly have more than 1 path type starting from the same element).
got it thanks
Hey I did just what you said here. Can you tell me what I'm doing wrong here?
Your method for making paths seems different. I used stack, and it looks like you are using set. I'm not super familiar with C++ so maybe your way is also correct, but I recommend checking this out.
Ok thanks I'll check it out.
Btw I was using set to find out the lowerbound of elements from 0 to i of a[i]. This would basically be the element just greater than a[i] and the --lowerbound will give the element just less than a[i]
To clarify:
Say you had an array of [4,9,3,9,5]
The "closest element to the left of that element that is <= than the element" of the 5 is 3, not 4. By closest I mean closest in proximity, not closest in value.
Hi, I got how the graph approach works, can you pls explain how will the dp approach work ?
So by now you should have a bunch of directed edges. Let dp[i] be the minimum number of moves to the ith element. Initialize everything at infinity, except for dp[1] which equals 1.
For all i from 1 to n-1, loop through all neighbors of the ith element. Let's call the neighbor nei. Set dp[nei] = min(dp[nei],dp[i]+1).
Answer is dp[n].
Hopefully this submission will make everything clearer. The dp portion is at the end. I used an array called path instead of dp. 92266290
Unofficial EditorialD's explanation
I solved problem C in a different way. I used the same observation. My program asked for each $$$i$$$ and $$$i + 1$$$ for odd $$$i$$$ and divides the indexes in two groups, the one of the smaller elements, and the one with the larger elements. We know the values for the smaller elements ($$$\min(x, y) = \max(x \mod y, y \mod x)$$$). Now we can solve recursively for the second set. It converges to $$$2n$$$. 92266927
I used the same logic , but implemented little different
How to solve problem B if you change $$$c_i = \gcd(b_i, b_{i + 1})$$$
How to die peacefully when solution of D failed just because of
==in place of=solve E in next round... that might help(to not to die) :)
Alexandra has an even-length array a, consisting of 0s and 1s. The elements of the array are enumerated from 1 to n. She wants to remove at most n2 elements (where n — length of array) in the way that alternating sum of the array will be equal 0 (i.e. a1−a2+a3−a4+…=0). In other words, Alexandra wants sum of all elements at the odd positions and sum of all elements at the even positions to become equal. The elements that you remove don't have to be consecutive._ what was the meaning of consecutive element not to be removed but most solution got accepted without this condition being fulfilled
Not being consecutive and don't have to be consecutive are different things. It says it not necessarily needs to be consecutive. Consecutive elements are still allowed.
I think my solution of A is a bit easy to understand (idk you tell me)
Approach: run a
whileloop with $$$i = 0$$$ as initial index, if I see a $$$0$$$ I will include this in my sequence, else if I find a $$$1$$$ I will see the next element and if it is also $$$1$$$ I will include these both since they cancel out each other and increment the index by 2finally I print the sequence.
Yeah, I solved it as this also, for each consecutive sequence of ones, if its length is odd, then remove the last one.
Here is my approach to problem A. Divide the array into pairs. For an array of size n, there will be $$$\frac{n}{2}$$$ pairs each having either $$$00$$$, $$$01$$$, $$$10$$$ or $$$11$$$. Pairs with $$$00$$$ or $$$11$$$ will contribute equally to the even and odd sums. Only $$$01$$$ or $$$10$$$ could be problematic, so for each such pairs remove the $$$1$$$ so that there is only $$$0$$$ remaining. There will be atmost $$$\frac{n}{2}$$$ such removals which staisfies the problem condition.
Here is my submission using this approach.
Incomplete EdItOrIaL
I was thinking to use seqment tree with Dp to solve D
I did it (2 sparse tables for the heights + 2 segment trees to query minimum value of elements on the stacks + 2 binary searches to find the range on which I must query), but turns out this was completely useless, because after every query on a range of elements in the segment trees I would pop out exactly the same elements from the stack.
92278634
i.e Just never write editorial again, worst D explaination!
Was problem $$$A$$$ "Ahahahahahahahaha" written by dick? Seems so to me after reading it's name.
If a part of turorial is missing we can still use mango_lassi submission 92251944
Hey how did you get that ? None of the submissions on his 1st submission page is accessible, the reference number doesn't have link attached to it.
In the result list, if clicked "show unofficial", then we can see all the red ones. Then simply click those submissions.
mango_lassi's submissions are better than editorials
Damn! He literally explains it. Thanks for sharing. xD
thanks finally i will be expert :)
Congrats!!!!
How does one even get to that observation in C?
In general, think about constraints of problem, and what features they have. In this problem in particular, think about how modding by x will always give less than x, so if you can just find largest number you could mod everything else by that, and because numbers are distinct ai % max will always equal ai if ai != max. Now realize that you only need the maximum up to a point your currently at if iterating through array one by one, so you just check to see if current number is greater than maximum so far using similar mod features. Hopefully that gives some insight on at least how I thought about it.
I made a 7x7 grid with x%y in each cell to see if there's a pattern I can use. Though 7x7 was a bit overkill lol
Hi, my dp solution for problem D got WA on testcase 27 with just a slight difference with Jury’s answer.
Participant's output 102549 Jury's answer 102548
Basically my way of approaching it is for every building i, save the first building to its left/right that has height >= h[i], <= h[i] (4 dp values for each building).
Then using this information, compute another 2 arrays rg, rs.
rs[i]/rg[i] means the leftmost building which has height smaller/greater than h[i] and has i as its corresponding dp value talked about above.
After we got this values, just go from f[1] ~ f[n] and take the min of the previous steps that could jump to this point.
Can someone see why I got WA? Thanks!
same problem with me :(
WA at test case 27, Participant's output 102549 Jury's answer 102548
link https://codeforces.me/contest/1407/submission/92350316
Actually I figured out. When you transit during dp, you need to check all previous nodes than could come to this one, not just the leftmost one.
It would be great if you tell me what's wrong in my code.
Do you mean that for any index i we have to consider both forward jump and backward jump from it??
after doing this still getting wrong answer :(
I got AC after doing this. You can check my last submission of this problem.
I got into the same problem: 148249647, and tried doing this and got a TLE: 148250691. What should I do?
Thanks Bro
can anyone tell me what is the problem with this submission? I just cant understand why my answer isnt correct...
Why are you always taking a gcd with the first element? You should take the maximum of gcd(arr[j], last).
EDIT: oh thanks a lotttttt
Sorry, I did not quite get you. Is what you wrote a testcase for which your solution is incorrect?
sorry I got it .. and Im really thankful :)
Can someone please help me find an example test case where my solution for Question D will fail? I can't quite figure out why it is getting WA on TC 5 92270795
Consider the test case: 3 3 1 2
The correct answer should be 1, i think
I think the shortest valid sequence is 0 -> 1 -> 3. So the answer should be 2.
Sorry, formatting issues. I meant 3 elements, and the heights are: 3 1 2
so we can just from 0->2 in 1 step
Even I am getting the participant's output as 50. I am unable to figure out what is going wrong, if you figured it out then pls tell.
I got stuck in the 1st question !! So, I decided to start with the 3rd one. But even after solving 3rd, I could not figure out the logic of 1st question. A(hahahahahahahaha) .... Anyway a nice contest !!
Hey bro,please help me with question A Link:https://codeforces.me/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
Your code is complicated and may be you are missing some cases. Solution to this problem is simple. Suppose you have >= n/2 0s in the string, then simply you can put n/2 0s in the string and remove the rest. Now when you have > n/2 1s then you can put only n/2 1s if n/2 is even else you can only put n/2+1 1s. Then each case will be considered!! I hope you understand it now.
But here we can't remove consecutive elements.
if the case is: 1110000000 we can't remove 111 because they are consecutive. I couldn't understand this logic. plz help me.
You have to keep n/2 0s, thats enough!! So you will remove all the three 1s and then remove any two 0s which are not consecutive.
In 3rd approach of problem B , i got that number of distinct values of $$$c_i$$$ should be $$$O(logA)$$$.But i didn't got why we need to iterate only $$$O(nlogA)$$$ times ? It might be possible that first few values of $$$c_i$$$ might be equal ? Can someone explain through an example .
Can anyone please point out mistake in my code for 2C?I have been looking for many hours now but can't find it :( What can be the mistake? (Got WA on Test case 8) https://codeforces.me/contest/1407/submission/92283806
you have 2 i, in your code. one for i j and another one for your last for. its the only thing i can see
Thanks for the reply,but actually that isn't the problem unfortunately. I noticed that and submitted it again https://codeforces.me/contest/1407/submission/92297960 But stil WA on Test case 8.No idea why
umm, i cant get your solution completely but i think this while(p < n — 2) it could be wrong. look at this case, 4 1 2 3 5 6 7 ..., in this case when a = 1, b = 5, then you come and refind the second — fourth places again and in each step you are adding p by one i think its better to say while(a < n)
Yes that is the problem.Thanks!
how to solve E?
change the order of the edges, and then run a bfs from node number n. then in your bfs, when you computing a node, you will see some nodes which never comes before in your queue. then if you put that node in the queue, its dis will be dis[current_node] + 1, and you want to maximum the distance of each node from node number n(its a greedy approach you can prove it by yourself) and then for not putting this node in the queue, if you can, you will set its color equal to the opposite color of the current edge.
The question actually "ahahahahahaha"ed me for the first 20 minutes, then I "ahahahahahaha"ed the question with a pretest passed verdict.
In problem D, one can observe that using the DP approach for calculating the first next larger element, the jumps done while calculating $$$dp[i]$$$ are exactly the valid jumps stated by the problem. This can make the code simpler.
The other solution (the also computes for each index, the first previous larger/smaller), proves that the complexity of the DP approach is $$$O(n)$$$, or more precisely, the DP approach will make $$$2n$$$ jumps.
Greedy Solution to 1407E - Egor in the Republic of Dagestan
Save all edges in the reverse direction (save edge $$$(u,v,t)$$$ at $$$v$$$ instead of $$$u$$$).
Now do a BFS from $$$n$$$. Supposing we are currently dealing with $$$v$$$. For an edge $$$(u,v,t)$$$, if $$$u$$$ has been colored in $$$t$$$, then $$$u$$$ is inevitable and needs to be added to the queue. Otherwise, we set $$$u$$$'s color to be the opposite of $$$t$$$ so that $$$u$$$ would not be added, at least temporarily.
In the end, we check if $$$1$$$ has been visited. If $$$1$$$ has not been visited, then we have found a way to make $$$1$$$ and $$$n$$$ not connected. Otherwise $$$dist[1]$$$ is exactly the longest shortest path we are required to find.
The greedy strategy works, because it is always better, or at least not worse to make the decision at an earlier stage. Supposing there are $$$(3,5,0)$$$ and $$$(3,6,1)$$$, and we visit $$$5$$$ first during the BFS. If we set $$$3$$$'s color to $$$0$$$ (so as to ban $$$6$$$ instead of $$$5$$$), then $$$(3,5)$$$ will be a valid path, and since $$$5$$$ is visited earlier than $$$6$$$, the distance from $$$5$$$ to $$$n$$$ is no larger than that from $$$6$$$ to $$$n$$$, which is not what we want.
Since we have set the colors during the BFS, we only need to output them. For those uncolored nodes, either color is OK.
Code: 92282786
Problem D should add following statement to clarify the task: Vasya can ONLY use discrete jumps, It means that all non-discrete jumps are not accepted. I'm a bit confusing why doesn't Vasya jump straight from 1 to n in the first sample test :-)
In Problem C, in editorial's solution we are not flushing the stream.
My Code gives AC when I flush, But EXACT SAME Code gives Idleness limit error when I don't flush the stream.
If author's solution is working why mine isn't :/ Can anyone please tell the error ?
(Code is printing a new line after ever output!)
EDIT: Got it. I had a macros which defined endl as "\n", thereby not flushing with endl.
Endl, which is being called by editorial solution, besides printing a newline, flushes the stream. On the other hand "\n" does not flush the stream.
Yes. I forgot that I had defined my endl as "\n" itself. My mistake. Thanks !
Chinese tutorial has been uploaded.
For task E: Why is it necessary to reverse the edges? Why not just begin from 1st Node and try to reach the Nth node.
From what I understand, it might be to reduce the number of unnecessary nodes that the queue visits. Can someone explain it more clearly? What is the intuition behind it and when is such a modification helpful?
The problemset was well balanced in terms of difficulty level.
May someone please explain how do we implement the third idea in the solution of problem B? Thanks in advance :D
In editorial of C, how come the first query is valid given you are querying for (0, 1) and according to constraints : 1 <= x ,y <= n
Check the ask function properly.
In problem E editorial, why are edges reversed and then processed starting from n ?
@i.e . for (int i = 0; i < n; i++) { for (int to : jumps[i]) { dp[to] = min(dp[to], dp[i] + 1); } } cout << dp[n — 1];
could u please explain it and time complexity of this particular loop in soln of problem D div-2. Thanx in advance.
You can add at most 2 new jumps for each skyscraper, so there is
O(n)jumps, which means that the inner cycle works inO(n)There are O(n) jumps in total, that is correct, but I believe it is possible to add more than 2 jumps for some skyscrapers.
eg: 8 3 2 4 7 8
From the first 8, you can jump to 3, 4, 7, or 8.
Yes, and?
Just wanted to point out that "You can add at most 2 new jumps for each skyscraper" isn't necessarily accurate. Although, maybe I misunderstood your comment.
I didn’t say that we jump at most 2 times from each skyscraper, I said that we jump at most 2n times in total.
Can someone please explain me the logic of question B...
The idea is that the first element must be the biggest from a[], because that makes the biggest possible c[0].
Then we can maintain the gcd from all choosen elements so far, and add n times that remaining element from a[] which results in the biggest gcd. So it is basically brute force.
Apparently A(hahahahahahaha) was not so apparent
Hey bro,please help me with question A Link:https://codeforces.me/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
1 8 1 0 1 1 1 0 1 0
try for this test case
Your code is giving 5 0 1 0 1 0
which is definitely wrong
Removing 1s from odd position will not solve it, as after removing one digit, the sum f and s will change, as the positions after the first removed digit, will interchange(odd becomes even and vice versa) in the final answer.
The Problem E, Test #11.
92324802 Emmm, what happened? why the hint say the answer is 5?
I guess it means that your answer doesn't match the real value of the shortest path length for the schedule output by you, and if you delete all unsafe edges for your schedule, the shortest path is 5 edges length
I think you're right. Thanks a lot!
Can we use "\n" in c++ to flush the output instead of cout.flush()? I have solved interactive problems on other platforms and "\n" works fine. I used "\n" in problem C to flush output and got Idleness limit Exceeded.
Editorial of D states that if hx <= hy than hy is first skyscrapper that not smaller than hx.
Consider this case: heights: 2 6 4
let hx = 2 and hy = 4
here hx <= hy but hy is not first skyscrapper not smaller than hx. Instead it's the 2nd skyscrapper.
This is for the case when all skyscrapers between $$$x$$$ and $$$y$$$ are smaller. Your example is the case when all skyscrapers between $$$x$$$ and $$$y$$$ are taller.
Question D. Discrete Centrifugal Jumps With an explanation.
I hope my comments will help others to understand the solution :)
In the 5th question is making the edegs opposite necessary?? shouldnt it work on the original graph too?
Thanks to problem B, I've learnt that:
GCD(a, b, c) == GCD(GCD(a, b), c)
But I do not get why GCD of a,b,c must divide GCD of a,b.
Why it is not possible that there is an x which divides a,b,c but does not divide GCD(a,b)?
How to prove it?
Let's explicitly write two integers with all of their common primes:
a = p1^i1*p2^i2*..*p_n^i_n
b = p1^j1*p2^j2*..*p_n^j_n
(where p is a prime and max(i, j) > 1)
So we can write their GCD:
GCD(a, b) = p1^min(i1, j1)*p2^min(i2, j2)*...*p_n^min(i_n, j_n)
Therefore we get that GCD(a, b) divides a and divides b
(same factors with a power less than or equal to original power)
Now you asked why GCD(a, b, c) must divide GCD(a, b)
As you stated:
GCD(a, b, c) = GCD(GCD(a, b), c)
Denote GCD(a, b, c) as y and GCD(a, b) as x:
y = GCD(x, c)
As proved above, the GCD of two numbers always divides both of them, therefore y must divide x
By definition GCD of $$$GCD(a,b)$$$ and $$$c$$$ must dividide both $$$GCD(a,b)$$$ and $$$c$$$. Since their GCD is equal to $$$GCD(a, b, c)$$$ then $$$GCD(a, b, c)$$$ must divide $$$GCD(a,b)$$$
Hey, I had written a code for yesterday's problem D just for testing whether my algo was correct but in my opinion it is an O(n^2) algorithm ,but when I ran it on the problem just for testing it passed all tests so I wanted to ask if the tests were weak or my code is somehow amortized to O(n).
Here is link to my code:https://codeforces.me/contest/1407/submission/92338883
For problem B, I wrote a O(n^2) solution combined with the number of test case it becomes around O(n^3), But why does it pass?
Sum of n over all test case was 10^3. So, test cases were already counted.
I would like to share my stupid approach for problem C, it is wrong because it may use at most 2.5*n queries to get answer (which I mistakenly thought it to be at most 2*n during the contest).
Firstly, set pos=1 and iterate for i in range [2,n]. Ask the value of (p[pos]%p[i]), if it is 0 then set pos=i, else do nothing. Then, we will get such a pos that make p[pos]>n/2 hold. Now, for i in range[1,pos-1], ask the value of (p[i]%p[pos]). Then note that each remainder can appear at most twice in (p[i]%pos), query it if it appears twice.
For example, if p[]={1,2,5,6,4,7,3}(1-indexed) then we will get pos=4 and the remainder is {1,2,5,-,4,1,3} and only 1 appears twice so we use one additional query (1,6) to determine their value.
Apparently, it may use (n-1)+(pos-1)+(a[pos]-1) queries, which is at most 2.5*n, but I just keep thinking it is no more than 2*n queries during the contest :(
Code: https://codeforces.me/contest/1407/submission/92258020
My submission for 1407C was 92267975 and i got runtime error on test 31. I don't understand why I am getting this as it is working fine on my machine without any error(even on test 31). Some help please!!!
It is because you are using fast io in an interactive problem. Remove the line fast and it will be AC. See 92343642
Ok, now I am confused. I submitted the code after removing fast io but still got the same result 92344000. Then I tried submitting the code in GNU C++17 and got AC in both (with and without fast io).
Now, I am wondering what is wrong in GNU C++17 (64).
This is out of range. vis has dimension n only. Thus you have undefined behaviour.
Yeah! I saw that and I changed its dimension to n+1, see 92344148 but still the same result.
I guess the problem lies in the language in which it was submitted. But I don't know what exactly it is.
No, it is because you are not using consistently the range 1 to n. You replace your line by fi(i,0,n)vis[i+1]=0,l[i+1]=-1; and you get accepted see 92347506
All right! Thanks a lot.
But still one doubt: why 92344465 this got accepted?
Here's a simple way to solve E: 92321081
thx
I didn't get D, how can we prove that the number of pairs i<j such that we can jump from i to j will be in order of n ? i.e
Because for a particular index there can be at most 4 just next nearest neighbours(left smaller , right smaller , left greater , right greater) which are smaller or greater than its value!. So in total there will be at most 4*n edges + n normal edges of adjacent elements . Thus at most 5*n such pairs exist!
Thanks got it now
92352918
Please someone help why my simple dp solution is not working.. And sorry for dumb mistake since I am new to this!
Sorry, I found mistake but still can't solve problem D.
You need to consider jumping in both directions. Assume
Answer should be 3.
In Case anyone feels difficulty in understanding official editorial of problem D Try this
At first try solving this problem It is the basic prerequisite :-Next Smaller Element
Now you are much knowledgeable to solve the problem yourself or just give another try if you are here for first time . I would recommend 5 to 6 more try!
Consider this problem as a source given (1) and you need to reach destination (n) under the given conditions in minimum time . Now one basic transformation one can think of is to draw a graph with various edges depending upon the conditions. and then if the graph is weighted then apply DIjskarts or if it is unweighted then apply BFS!.
Don't be confused actual main idea starts here .
Creating the graph
Move 1--> We can always move from i to i+1th node so our graph is connected that is we can always follow this route to reach n.
node ---- 1-->2--->3--->4--->5----6...--->n
time ---- 0-->1--->2--->3--->4--->5------>n-1
so for ith node minimum time taken is i-1 (self explanatory) if we dont draw any other edges. SO now we have our basic connected graph that is a tree!
Move 2 was that from a node i we can jump to node j (means an edge exist if all elements in the range i+1 to j-1 are strictly lesser than both a[i] and a[j].
Now how can I find these pairs efficiently.
First lets consider for i <j and for j We need to find i which satisfy this. Right!!
lets find all those i for which just next greater or equal element to right of a[i] is a[j] . If you would have solved previous prerequisite problem then these is too easy to find for all indices altogether in O(n) time.
Now prove that why for all i given j will satisfy the move 1. As a[j]>=a[i] and all in middle indices(i+1 to j-1) between i and j are lesser than a[i]. ( Because if middle index would have been greater than a[i] then we never would have reached j.)
thus to move 1 finding these and same for left to j. and right to i is sufficient. Thus to draw {i,j} edges in our original array represented as graph! we have to add following edges. for each i find next greater element to left and next greater element to right.
MOVE:-3 From a node i we can jump to node j (means an edge exist if all elements in the range i+1 to j-1 are strictly greater than both a[i] and a[j].)
For strictly greater part to draw {i,j} edges in our original array represented as graph! we have to add following edges. for each i find next smaller element to left and next smaller element to right. Proofs are same as in first part. Now our graph would look something like this at each index !
>>>>> >>>>>> 1-->2--->3--->4--->5------->6.....-->n <<<<<< <<<<<<<<this extra dashed edges are created by moves 2 and moves 3.
Now we have constructed our graph and we need to find shortest path from node 1 to node n
As It is unweighted graph we can use one simple thing is to find Single source Shortest Path using bfs! Pretty common technique.
First option of bfs works for only unweighted graphs but consider another problem that edges have a weight of (j-i)/k then in case of weighted graph we would have used Dijskarts but complexity would be O(nlogn) . Also what if there is a negative edge means for some edges weight becomes negative then we would go for Other advanced algorithms like Johnson Algorithm . Which is again having O(nlogn) solution but what if we have to consider all the things in linear time. If the graph is having any type of edges without having negative cycle then definitely the below given solution with Dynamic Programming works well for handling all such scenarios in linear time. I liked that approach very well but Bfs can do this easily. So if you only have to go in more conditions and more conditions then only consider the next spoiler with DP.
Solution is use DP.Lets define dp[i]= the minimum time taken to reach node i if we consider only first i nodes and minimum time taken to reach here from node 1. Ok how to make transitions in this dp.Well lets say for a particular node i we have 4 edges . jlefts,jrights,jleftg,jrightg.g=greater element,s=smaller,jrights , jrightg > i > jlefts, jleftg.
for node i following 3 transitions are possible.
dp[i]=min({dp[i-1]+1,dp[i]});
dp[i]=min({dp[jlefts]+1,dp[i]});
dp[i]=min({dp[jleftg]+1,dp[i]});
And for future coming nodes node i can play a role to its minimum value thus we have to make extra 2 transitions! dp[jrights]=min({dp[jrights],dp[i]+1});
dp[jrightg]=min({dp[jrightg],dp[i]+1});
If you won't make these extra transitions answer won't be minimal in worst case. THUS I tried to explain it clearly. If further doubts occur consider my simple solution!
92355697
THank You!
Thanks for such a clean code and wonderful editorial
"First option of bfs I won't recommend as it doesn't involve much thinking and what if the graph would have been weighted?"- if graph was weighted, we would have used dijkstra. How do you conclude that graph approach doesn't require thinking, how dumb are you Mister specialist. If it didn't require much thinking why were you not able to solve it during contest, you dumbass
Na gaand hai na chuchi, aur baate kare uchi uchi
I have a personal choice of algorithms where to use which one may be It contradicts you. The idea to Solve the problems was crystal clear to me around 10.minutes before the contest. But due to my slow implementation speed I was not able to implement. Lets say Now There is a edge with weight x>1 in graph or I can better say that for each I to j transformation the time taken is (j-i)/k where k is some constant factor for a particular graph. Apply Bfs if you can!
The only option is to involve deep thinking in this case. When a problem is solved during a contest sole moto is to compete but when an editorial is written or when you are upsolving we have to consider 4 to 5 ways to approach problems and consider side effects of each and every approach that's what I did in my editorial.If it hurts you I am sorry but my way of thinking is not to strict my self in a bound of known algorithms.
Ya I am a specialist but capable of understanding data structures and Algorithms clearly.
You could have said that you liked dp approach more, but instead you concluded that graph approach does not require thinking. Don't fucking contradict your statement, you dumbass.
Your rating graph shows how things are crystal clear to you Lol
First of all try to do C in every contest, then try to write editorials of D. You wasted 2 minutes of every person who tried to read your cancer editorial
Mind your business. I know what I have to do and where I have to practice. I have written editorial because official version was not much clearer to many persons. And if you Think that it is cancer then just skip it . I have not forced you to read it and do harsh comments and spread hatred.
Thanks AM_I_Learning for writing your editorial. You have nicely explained all the things.
Your welcome !
You are so stupid that i have to repeat myself, IF GRAPH WAS WEIGHTED WE WOULD HAVE USED DIJKSTRA
And you are talking about capability of understanding data structures and Algorithms clearly
What if edges would have negative weight . That is in my above comment if k becomes -ve for some transition then you would go for Johnson's right but Dp is a universal solution I take back my words of deep thinking. I have revised it you can see orz! Not going to talk more
Ya I have said that I have the potential to learn clearly . I have never said that I already knew them clearly. I am just beginning learning them. Anyway thanks to bring deep insights in me.
wrong ans case 32 code: 92383805
i tried too much.my approach al most same to you..i can't find wrong. do you please check my code ?
also i can't understand why need those
dp[jrights]=min({dp[jrights],dp[i]+1}); dp[jrightg]=min({dp[jrightg],dp[i]+1});
We need these transition because there exists edges both to the left and. Right side of a node . If you won't update these right nodes with the current node. Then when you reach any node j>i for which j is the next right greater element then there is a possible jump but at i only we know that there is a jump possible not at J . Thus To consider all the possible cases we have to make both left and right transitions while parsing a single node.
thank you got it..i handle this bit different process...I consider jleftg,jlefts.. if any i there is no jleftg or jlefts then I load possible maximum jump for this i..
this is done here
for(i=1; i<=n; i++) { while(1) { if(stk.empty()) break; z = stk.top(); if(z.first<D[i]) break; nextmn[z.second] = i; vis[z.second]=1; stk.pop(); } stk.push(mp(D[i],i)); } while(!stk.empty()) stk.pop(); for(i=n; i>0; i--) { while(1) { if(stk.empty()) break; z = stk.top(); if(z.first<D[i]) break; stk.pop(); if(vis[i]==0) nextmn[i] = z.second; } stk.push(mp(D[i],i)); //cout<<i<<" "<<stk.size()<<endl; }
Thanks if any one person got insight with my editorial I feel good .happy coding keep learning!
Thanks AM_I_Learning for the detailed explanation and the suggestion to solve "Next Smaller Element" which helped a lot.
In the problem AHahahahahahaha.(1407A) I am confused about the editorial solution .It says if count_one<=n/2 , we remove all ones and the alternating sum will be oviously zero. But what if suppose n=12 and array will be like 0 0 1 1 1 1 0 0 0 0 0 0. According to the i.e's solution we should print 0 0 0 0 0 0 0 0. But according to the question "The elements that you remove don't have to be consecutive.".Just correct me if I am wrong.
P.S:- You will get AC on submitting the solution described in Editorial
"elements don't have to be consecutive" — they can be both consecutive and nonconsecutive. It's written in this way because some participants could think that it's allowed to erase only subarrays, not subsequences.
You are right but You should have written "need not" in place of "Don't" coz these terms are very critical if we read it as English. BTW I took it as "don't" while contest and didn't remove more than 1 consecutive element from the array. and result for above e.g is the same as the original array i.e [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0].
bro, english is not my first language, but as I know "don't have to" means "you can do it, you're not forbidden to do it". and as you can see this task have been solved by too many users, they understood this line so it's not typo.
In C, how do we decide the index to place a or b (which is either mx or i) in the original permutation ? Thanks in advance :)
suppose permutation P in P[1]=3,P[2]=5 call for ? 1 2 will return 3 (a=3), but call for ? 2 1 will return 2 (b=2) though ? 1 2 return maximum .so it is clear that index 1 < index 2; so index i mean p[1] will be max .(like as P[1]=a)...next check for index 2,3 and so on
Who interested, I found out that we can always erase not more than one number in the first task. It's not hard to prove, you can do it by yourself (I can write, if you really want, but I'm too lazy :) ). So we can solve it with $$$O(n^2)$$$ — simply check initial array and array without each element.
(maybe somebody wrote about this solution in the comment, in this case, I'm sorry)
After discussion with my friends we came up with the same conclusion lol
It can be implemented in O(n) tho: 92392220
i.e or Nezzar can you prove this please ? I tried to prove using induction but didn't succeed.
Briefly (not formally):
For any input, we can keep ignore(virtually delete) neighbouring 00/11s.
The result string will always be 1010101010... or 01010101...
Let number of 1s be k
If k is odd, delete the middle 1 (so that there will be floor(k/2) 1s for odd and even positions)
If k is even, delete the middle 0 (the 0 between k/2th 1 and (k/2+1)th 1).
(Obviously if result string is empty then we don't delete anything)
But aren't we deleting more than 1 time in your proof ? Also in that case number of deletion can be more than n/2 .
By virtually delete we are not actually deleting them, just that we pretend they do not exist. The actual deletion (if any) only happens at last step.
92410698
Why is editorial for Problem D so complicated when we can have much simpler and shorter implementation.
Guys, can anyone help in understanding why my solution for E is wrong. Basically, my logic is, start from vertex 1 and explore all edges to vertex n. If there's an edge that lies on the shortest path to n, color the vertex opposite to that edge so that we cannot travel on it. It feels like a simple solution, but it's giving WA. Can anybody help in explaining why along with a smaller test case? Thank you! Solution: https://codeforces.me/contest/1407/submission/92859047
Sorry, I'm a bit confused here. Could somebody help me? For problem D, why do we have to check both from the left and right? Wouldn't checking just from the left suffice?
My bad, I got it
In E, edges are from u to v or undirected ? i.e please look into.
Can you please explain why recursion doesnot work 94162657 and iteration works 94163536 in D Div2. I just don't get whats happening at 32 test case.
I solved problem E using modified dijkstra. submission