Problem: https://codeforces.com/contest/1620/problem/E
I was trying to apply some dsu-like logic in Problem E, when they asked for replacement of every $$$x$$$ with $$$y$$$ in the array, but it gave me WA on test 4.
The idea which I used during the contest:
from = replacement[x], to = replacement[y]
while(replacement[to] != to) to = replacement[to];
replacement[from] = to;
And, the idea which gave AC after the contest,
replacement[x] = replacement[y]
I know that the latter one is clever and more sleek, but why the former one fails? Can anyone please suggest a counter-case for it?
Except for these idea, the rest of code was exact same!
Submission 1 (with first logic): https://codeforces.com/contest/1620/submission/139872871
Submission 2 (with second logic): https://codeforces.com/contest/1620/submission/139872969
In the first code, by not recurring to the root of the tree that contains from, you omit to merge completely the two sets (the one containing x and the one containing y). Otherwise, even the code that gave you AC is very... sussy. Or at least, there is something in your code that you omit to show us (i.e. probably by changing
from, you might rewrite some elements that oughtn't be rewrited?)In any case, I do warmly, cordially, and everythingly reccomend you to read in more depth this page , so you would learn a.. proper implementation of this algorithm
Sir, just want to re-mention that I'm not using a proper dsu logic, I'm using instead a dsu-like logic.
A proper dsu logic, I think, will give wrong answer, because replacement of $$$x$$$, doesn't changes the replacement value of any other number $$$z$$$ in the group, unlike in dsu, where the parent of every member in the smaller group changes when union happens.
Please, don't do semantics on me.Using "dsu-like logic" is like saying building a cartesian tree uses "stack-like logic" or the Dinic's algorithm uses "bfs-like logic"
As far as you let me know, on the following test:
61 21 32 2 12 1 42 4 52 3 2You code might print: 5 1, because the replacement of 2 becomes 1, it doesn't change after that (after all, it's not 2 anymore that gets replaced directly). Then, at 3's update, it becomes 1, since the replacement of 2 hasn't changed at all.
Maybe your code actually goes from the back of the queries, a detail that you omitted to comunicate. Then, in that case, this testcase:
61 21 32 3 22 1 62 2 12 6 7Then:
r[6]=7 r[2]=1 r[1]=6 r[3]=r[2]=1Where
r[x]isreplacement[x]Then you might print
1 1. Which would be, you know, correct.So, if you want anyone to help you, you have to give us a little more context! Your code is clearly not wrong, since you claim that it passed all tests, but the picture of what you just shown me is incomplete. Please consider attaching the entire code.
Auto comment: topic has been updated by the_drunken_knight (previous revision, new revision, compare).