Codeforces Round #746 Editorial

3 года назад, # ^ |

+33

Also, Dfs order of edges without Euler tour traversal will work in 11 queries, But we didn't want to make the problem harder so we let ETT solutions pass.

→ Ответить

teruel

3 года назад, # ^ |

← Rev. 2 →

I think D can be solved in around $$$1 + 1.25 * log(N)$$$ querys for a general graph, by doing ternary search over the sets of nodes, even if edges from the graph are hidden. Sadly that was 1 extra query and i couln't solved it that way. Anyways, awesome problemset!

→ Ответить

JOOG

3 года назад, # ^ |

← Rev. 2 →

_runtimeTerror_ Bakry I do understand why ETT works, but could you please explain why your approaches work?

UPD: Already realized what's happening when using bfs/dfs. Just accepted it, 130744806 is my solution using bfs. Thanks!

→ Ответить

ChickenInKitchen

3 года назад, # ^ |

yes i did this solution i think that the euler tour solution is much harder to realize though

→ Ответить

Mazaalai

3 года назад, # ^ |

← Rev. 3 →

found it (Euler tour traversal)

→ Ответить

izhang

3 года назад, # ^ |

+36

I used a centroid decomposition solution, which passed in 11 queries for all system tests. However, there is a construction that makes it use $$$1 + log_{\sqrt{3}}n \approx 13$$$ queries. The construction is basically the pattern shown below, recursively expanded.

130697675

→ Ответить

3 года назад, # ^ |

Could you elaborate on it being log in base sqrt(3)? I also did centroid decomposition

→ Ответить

izhang

3 года назад, # ^ |

← Rev. 2 →

+23

Basically, this construction makes it so that the size of the tree only decreases by a factor of 3 every 2 queries.

In the tree above, 1 is a set of 334 nodes, 2 is a set of 333 nodes, and 3 is a set of 332 nodes. The solution edge is somewhere in set #3.

In the first query, the algorithm would query all of the nodes in set #1 and determine that the solution edge is either in set #2 or set #3.

In the second query, the algorithm would query set #2 and determine that the solution edge is somewhere in set #3.

We can then recursively construct the same tree structure in set #3.

As you can see, we have used up 2 queries, but only decreased the size of the tree by a factor of 3. This means the algorithm will use $$$1 + log_{\sqrt{3}}n$$$ queries, which is just barely over the limit.

I was able to hack your submission using a very similar test case.

→ Ответить

3 года назад, # ^ |

Thanks a lot!

→ Ответить

ahshafi

3 года назад, # ^ |

how are you always sure to reduce the tree by a factor of 3 at least?

→ Ответить

P___

3 года назад, # ^ |

I was also doing sort of centroid decomposition. If you have the time, you can try to hack my submission too. It passed all the hacks so far.

→ Ответить

izhang

3 года назад, # ^ |

← Rev. 2 →

+14

I just hacked your submission. I'm pretty sure that any solution involving centroid decomposition can be hacked. Thanks for letting me know and making the test set stronger.

→ Ответить

P___

3 года назад, # ^ |

Thanks, I agree.

→ Ответить

Gedawy

3 года назад, # |

Thanks for the quick editorial

→ Ответить

Ghuraba

3 года назад, # |

It was a miracle. compared to current speed of posting of editorials.

→ Ответить

SuryaManikanta

3 года назад, # |

B is Great!!!

→ Ответить

Suri429

3 года назад, # |

+29

Loved problem E.

→ Ответить

Letscode_sundar

3 года назад, # ^ |

Can you please explain how to do E in detail?

I can't understand so as to how to find the lower boundary ?

How will you construct a mask for this and check for odd and even cases?

→ Ответить

Suri429

3 года назад, # ^ |

← Rev. 2 →

Let ith bit is most important bit, that means, for all bits greater than ith bits, xor = AND = 0. So what you want is, when we are assuming ith bit is most important bit, can we somehow have only bits greater than equal to i, in each number of array and remove their lower bits. This can be achieved by taking bitwise AND of all numbers with a number which has bits>=i as set and bits <i as unset. All you need now is, in this modified array max length subarray with xor = 0.

130719800

→ Ответить

hunxuewangzi

3 года назад, # ^ |

Thanks for the code

→ Ответить

ashishdtu007

3 года назад, # |

What was the intuition to B? like I got to know that what will work but what is the line of thinking (approach) to solve this problem ?

→ Ответить

FrozenKandy

3 года назад, # ^ |

+13

My approach: We cannot move an element if i-x < 0 and i+x > n-1 (i is the index of the element), so its index must same as in the sorted array. We can swap the rest of the elements as we want.

My Solution

→ Ответить

Fanarill

3 года назад, # ^ |

What a lovely idea. I thought about something like this but still coudn't complete this idea. Thanks!

→ Ответить

quiet_one

3 года назад, # ^ |

← Rev. 2 →

can you tell me what should be the output for** ~~~~~ n= 5 x=3 arr[]= 5 4 3 2 1** ~~~~~

and how?

→ Ответить

FrozenKandy

3 года назад, # ^ |

YES

Explanation

→ Ответить

oursaco

3 года назад, # |

You could just sort the edges and do binary search on D

→ Ответить

Oceann

3 года назад, # ^ |

fucking great idea,sad to realize this after contest...

→ Ответить

Parinay2003

3 года назад, # ^ |

What is the reason for sorting?

→ Ответить

oursaco

3 года назад, # ^ |

none really. I just tried a few test cases and it seemed to work

→ Ответить

LYC_music

3 года назад, # ^ |

You could do it on the bfs order.

→ Ответить

Nutella3001

3 года назад, # ^ |

+34

sorting mustn`t work in this task... guess tests are week maybe

→ Ответить

ScarletS

3 года назад, # ^ |

+11

cute pfp

→ Ответить

BidoTeima

3 года назад, # |

nice contest. fast systest and editorial :D

→ Ответить

ctrl_alt_delete

3 года назад, # |

Thanks for the fast editorial. For problem C, may I ask that how do we find the two required edges to break the tree into 3 parts with xor sum of each component equal to x in O(n) or O(n lg n) time? I have been trying to solve this problem but I am stuck at the implementation.

→ Ответить

ctrl_alt_delete

3 года назад, # ^ |

I saw the update in the editorial. Thanks for explaining it!

→ Ответить

mym0404

3 года назад, # |

I Think, in problem A, ans should be "H / (x + y)" multiple by 2

→ Ответить

3 года назад, # ^ |

we've corrected it in the editorial

→ Ответить

ushachok

3 года назад, # |

Thank you for a great round and fast editorial!

→ Ответить

yoneking_tw2

3 года назад, # |

Thanks for fast editorial!

→ Ответить

lexiyvv

3 года назад, # |

+41

Are there any provements for C that the deepest subtree erase is always right?

→ Ответить

abhishekJr

3 года назад, # ^ |

If we do not choose the deepest subtree we might mistake choosing a subtree which has three (2n+1) subtrees in itself who individual XORes is equal to the XOR of all the nodes in the given tree. And unfortunately we might not find any other subtree with the required XOR.

→ Ответить

3 года назад, # |

← Rev. 2 →

Problem D could've been solved relatively naively due to the limit being $$$n < 10^3$$$, ie. without any consideration in which order to process edges. Simply maintain the set $$$E$$$ of suspected edges and traverse graph in any way you like (in my case it was DFS) until you enumerate $$$|E| / 2$$$ suspected edges (for the binary search part; edge set will be denoted as $$$E'$$$). Collect all the visited nodes into a single query, and if this query gives the same result as the initial query for the whole graph, set $$$E = E'$$$. Otherwise, $$$E = E \setminus E'$$$.

Of course, each time we print a large portion of the tree just because we enumerate zounds of "unsuspected" edges. What I mean to say is that there was no need for consideration of Euler tours nor to care about efficient implementation.

Btw, this makes IO load equal to $$$O (n log n)$$$ rather than amortized $$$O(n)$$$ as in editorial.

Also, I liked this problem a lot :)

→ Ответить

P___

3 года назад, # ^ |

Could you please explain why is it O(N log N)?

→ Ответить

3 года назад, # ^ |

Most cases you will enumerate lots of edges that are not in set $$$E$$$, because we queried about them already. In other words, almost every query will be about a set of O(n) vertices. There are O(log n) queries, thus O(n log n) vertices printed in all the queries.

For example, imagine a path of length 512. First you enumerate ~256 vertices. If the sought-after edge is not there, in the next query, if you start dfs from the same source, you need to query 256 + 128 = 384 vertices rather than just 128 (because first 256 vertices enumerate only edges not in $$$E$$$, and you need to print a whole connected component). Etc.

→ Ответить

3 года назад, # ^ |

Though I checked my submission 130706195 and it seems that during the round I mitigated this problem, because I stored the visited component as a set of suspected edges from this component (the $$$qry$$$ variable). And instead of querying vertices from the whole component, I print only those adjacent to at least one $$$qry$$$ edge. It seems that this trick makes all queries to contain at most $$$n + 2n - 2$$$ vertices in total = $$$O(n)$$$.

Anyway, $$$O(n log n)$$$ should pass as well (ie. if you stored vertices from the component rather than edges).

→ Ответить

SriniV

16 месяцев назад, # ^ |

← Rev. 3 →

Sorry for the necropost, but I had a very similar idea in mind, and it looks like it is nlogn as well ( maybe nlog^2n ), but it TLEs. Not sure how to optimize it or if its even worth trying. Here is the link: 214129320 Could you let me know what I am missing or if I should just try and go for the intended sol?

→ Ответить

16 месяцев назад, # ^ |

← Rev. 2 →

Sorry for the late response: It seems that your search for a set of half of the edges is quadratic (due to running a BFS for each vertex). I did not analyse very deeply but this is what seems to be the case. And this complexity times twelve queries takes you above 1000ms time limit. At least it seems like so.

Hint: It is much easier to switch your viewpoint from tracking vertices (ie. sub forests) to edges (this may very well be a set of disconnected edges). Just pick a set of edges to query for and the actual query is all vertices that are endpoints of the selected edges. Then you require only a single DFS / BFS per query (so that the endpoints do not mark unwanted edge that should belong to the set "right"; example if you are left with a path 1 — 2 — 3 — 4 and you want to select 2 edges, do not accidentally pick 1-2 and 3-4, because the set of all endpoints is {1,2,3,4} and it's incorrect. You should pick edges 1-2 and 2-3 or 2-3 and 3-4. The set of edges can be selected with a single DFS).

[Edit] Hint 2: In this problem you can very easily prepare testcase with n = 1000, by just making a path or a star graph. Then you can play with where the bottleneck is.

→ Ответить

SriniV

16 месяцев назад, # ^ |

Thank you so much for your very detailed response! I will look into it! Never too late of a response :)

→ Ответить

Abulkhaerov

3 года назад, # |

In problem A ans=(h/x+y)*2

→ Ответить

3 года назад, # ^ |

we've corrected it in the editorial

→ Ответить

Parinay2003

3 года назад, # |

Could anyone please explain me that why does this submission 130717510 to D fail because I guess that this approach was fully correct. Moreover can anyone explain me why does this submission pass 130725042. I cannot find any valid reason for this and am doubting this to be a case of bad test cases

→ Ответить

satyam343

3 года назад, # ^ |

Your AC solution fails on

1 2 4

2 3 1

1 4 1

1 5 1

→ Ответить

Parinay2003

3 года назад, # ^ |

That's exactly what I was saying weak tests

→ Ответить

post

3 года назад, # |

Can anybody disprove the following?

We can split into 3 components if we can find a subtree (not the tree itself) that has $$$xor$$$ equal to the $$$xor$$$ of the whole tree.

I am getting wrong on the test 10, with this idea. Solution.

→ Ответить

mohamedeltair

3 года назад, # ^ |

Assuming that other nodes count is > 1, you guarantee that you can split them into 2 components with equal xor value, but this value is not necessarily = the whole tree xor.

→ Ответить

Adam_GS

3 года назад, # ^ |

← Rev. 2 →

1
3 69
2 2 3
1 2
1 3

→ Ответить

post

3 года назад, # ^ |

Ooh, yes. Thanks.

→ Ответить

n0sk1ll

3 года назад, # |

+57

Now this is a great round. A-C were creative and easy to code, D required some implementation, E was just beautiful and no "fancy" algorithms appeared until F2, the hardest problem.

A perfect example of how div2 rounds should be prepared.

→ Ответить

vyer

3 года назад, # |

← Rev. 2 →

rel-a-table

→ Ответить

Kyou_mo_kawaii

3 года назад, # |

+22

Systest for C seems to be weak. I wrote something nonsensical (count all edges that can split the graph into zero and the target xor value). But it can be uphacked with this simple test case:

→ Ответить

gabaswillwinIOI2022

3 года назад, # |

← Rev. 2 →

For problem D maybe my solution can be hacked because my basic idea was finding maximum edge at first by 1 query. After that split the tree to 2 trees so that new smaller trees have 1 common node and their union is current tree. Also while choosing this 2 trees we are minimizing their size difference. Now after splitting we can easily ask one query about them and determine which one includes max edge and continue to process until our tree has only 2 nodes. This works quite well but I can't create worst case scenario If you know how to do it please share your ideas. my code

→ Ответить

huikang

3 года назад, # ^ |

My friend hacked my solution post-contest with randomly generated trees.

My solution selects half of the remaining nodes by starting from a random node and dfs, and repeat if necessary.

→ Ответить

peti1234

3 года назад, # ^ |

Hacked with a tree, where each node has $$$9$$$ children. $$$n=820$$$, it has $$$3$$$ layers, and in the worst case it is $$$4$$$ question to handle each of them. $$$3*4+1>12$$$. I think a similar construction works, where each node has $$$5$$$ children.

→ Ответить

kanishk779

3 года назад, # |

How can E be solved in $$$O(NlogN)$$$? According to editorial, it looks like the time complexity should be $$$O(N^2 logN)$$$

→ Ответить

Tutis

3 года назад, # ^ |

I only know a solution in Nlog(max A), I think the editorial meant that it's solved by iterating k giving total complexity N(logN ?)logmaxA. One observation you can do is that you can split the array into intervals [x, y], where for all positions k is set, and then find tho positions which are furthest apart with the same xor (in the interval [x-1, y]), but with the same parity of indices.

→ Ответить

LipArcanjo

3 года назад, # |

← Rev. 2 →

In problem E, shouldn't be $$$r-l+1$$$ is even, instead of odd?

→ Ответить

3 года назад, # ^ |

Edited. Thanks!

→ Ответить

sharmaharisam

3 года назад, # |

As always, here are the video solutions to the first three problems : solutions

→ Ответить

3 года назад, # |

It's not solution but I want to share idea about 1592D - Hemose in ICPC ?. You should know that tree is bipartite graph. Let's say one partition is array a, and other partition is array b. Request answer for 1,2,...,n. Let's say it's r. Now, repeat following:

if partition a bigger than b, just swap them.
now split array b (array of vertices) into two halves c and d, or closest size. Because in bipartite graph each edge goes from one partition to other, we get that edges connecting a and c are different to edges connecting a and d, and together they make whole set of edges between a and b.
ask about vertices a + c.
if result is less than r, then say new partitions are a and d, otherwise new partitions are a and c.

Do this until we get 1 vertex in both partitions. I didn't proof how many requests it does in worst case, but I guess it's around 17 (case 500 size of both partitions). So it's a little bit more than we can afford. Sad. But very easy to implement. 130691922

→ Ответить

3 года назад, # ^ |

For some reason, if I remove isolated vertices each time before the check for swap, then it get wrong answer, but it should be request limit exceed if idea above is correct. Something is wrong. 130827040

→ Ответить

3 года назад, # ^ |

I found bug. Proof above is wrong.

Why?

Everything right what is stated above, the hole is in understanding of what you asking by query. If you read carefully statement, you're asking maximum Dist(u,v) but it doesn't forbid to walk through vertices not in set. I was thinking about paths only over those edges which connect vertices we choose but it's wrong. Simplest counter case of proof is graph:

First partition is 1 3 5, second partition is 2 4. It asks about vertices 1 2 4, but there is path from 2 to 4 via 3 which has two edges of weight 10, and thus it thinks that we need only 1 2 and 4. but 4 is isolated now, so it answers 1 2 which is wrong.

→ Ответить

3 года назад, # |

+20

The contest was fun, but i think the editorial is kinda bad. For example, on E, what is "which can be solved easily in O(NlogN)" supposed to mean? If you're not gonna explain the solution at least put code so people can learn what to do.

→ Ответить

kevbamboo

3 года назад, # |

me: thinks I can pass 1000 this round

codeforces: nope, here's your 999

→ Ответить

3 года назад, # |

Can someone break my idea for D? Im finding the centroid of the tree and doing a knapsack to find the value closest to n/2 you can get by summing subtrees of the children of the centroid and do a query with those subtrees + the centroid. If the value you get by doing it is less than the answer, you remove all those children from the tree (i.e mark them) and repeat that algorithm until i have 2 nodes.

Code: 130722106

→ Ответить

Soonic

3 года назад, # |

why we multiple by 2 in problem a?

→ Ответить

3 года назад, # ^ |

Because we're using two weapons. Think of the case where h = 10 and the two weapons are 5 and 4

→ Ответить

Soonic

3 года назад, # ^ |

bro i don't understand all equations for problem a Can you explain them?

→ Ответить

3 года назад, # ^ |

Assuming you understood the first part of the editorial:

The ammount of times we can be 100% confident we can use both weapons will be h/(x+y) (the ammount of times we can fit both of them in h).

That would cost (h/(x+y))*2 operations and leave h-(h/(x+y))*(x+y) hp remaining (each time we take x+y hp off, and we will do it h/(x+y) times). We can notice that this is the remainder on the division of h by (x+y), or h mod(x+y) or in c++ h%(x+y).

Since the hp remaning after that will be smaller than x+y, you will either use x or x and y if it is bigger than x.

If you still cant get it, do some cases by hand and/or read the editorial and this comment again

→ Ответить

mmpataki

3 года назад, # |

← Rev. 2 →

Hemose Bakry there is unproved part for C. "If you can partition the tree into m components".. how do I prove this?

Can you please help in proving if these (below) are the components with every one of them with xor=x, we can have another set of 3 legal components?

→ Ответить

Video explaining the idea

3 года назад, # ^ |

you cant partition into those components in the first place because you cant get that by removing edges

→ Ответить

ram.18

3 года назад, # |

In problem C, Can anyone explain how do we search for the 2 edges in the tree?

→ Ответить

ak2006

3 года назад, # ^ |

Basically once we fix the first edge, I explain how all edges fall under 2 categories:

1)An ancestor to its parent and

2)A vertex from a disjoint subtree of an ancestor to its child Then I explain how we can check for these 2 cases in the DFS.

→ Ответить

Ausmosian

3 года назад, # ^ |

Or you can also just count number of edges (say cnt) s.t the subtree corresponding to these edges have xor = 0 or xr (=xor of whole tree)

ans = (cnt >=2 ? "YES" : "NO")

My submission: 130710063

→ Ответить

rajipthakur01

11 месяцев назад, # ^ |

← Rev. 2 →

your solution is not giving correct answer for below testcase:

6 4

10 1 1 1 1 1

1 2

2 3

3 4

4 5

5 6

Expected: NO

your solution ans: YES

→ Ответить

ducati

3 года назад, # |

← Rev. 2 →

+21

F1 and F2 are one of the best F problems I have seen before: It's really difficult to come up with the correct ideas, but the solutions are quite short.

→ Ответить

ducati

3 года назад, # |

In the editorial of F2, perhaps "if" is spelled wrong in the last paragraph:(

→ Ответить

rama_pang

3 года назад, # ^ |

"if and only if" is sometimes shortened to "iff". Link.

→ Ответить

ducati

3 года назад, # ^ |

Oh, I have known that know. Sorry for my poor English:(

→ Ответить

shubham84

3 года назад, # |

Can someone give me a solution to D problem in simpler words, I just can't understand it from the editorial.

→ Ответить

3 года назад, # ^ |

check this URL to understand what is euler tour https://www.geeksforgeeks.org/euler-tour-tree, and we generate an euler tour array from the input tree, then use binary search to find the edge with maximum dist

→ Ответить

3 года назад, # ^ |

Why does binary search in the Euler Tour yields the right answer?

→ Ответить

3 года назад, # ^ |

Let's define Dist(u,v) as the greatest common divisor of the weights of all edges on the path from node u to node v.

means the maximum dist in this tree is simply a maximum weight edge from u to v, because a >= gcd(a,b) for all positive integers

→ Ответить

3 года назад, # ^ |

I understand that. What I don't get is: how do you know that when you choose the midpoint in the binary search, you're not "breaking an edge"? In other words, how do you know that all the edges you have to consider will be either in the left or the right part of subarray you're considering?

PS: I can see why that won't happen in the first 2 splits, but I can't see why it'll never happen.

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

there is no way to break an edge since we only do binary search on nodes, in one search we decide to search the node's left or node's right (here left/right means left/right in euler tour array)

→ Ответить

3 года назад, # ^ |

1 2 3 2 4 2 1 5 6 7 6 5 8 5 1

Assume the answer is edge 5-6. Let's say that the first binsearch split gives you:

6 7 6 5 8 5 1

Now, the second split will query either

"6 7 6" or "5 8 5 1"

and neither has the answer (5-6).

→ Ответить

3 года назад, # ^ |

in the second split we will split the arr into (6,7,6,5) and (5,8,5,1), then ask whether the left part has the maximum.

here's my code

        while (l + 1 < r) {
            int m = (l + r) / 2;
            get arr from euler arr[l,m](l and m inclusive)
            int t = ask(arr);
            if (t == target) {
                r = m;
            } else {
                l = m;
            }
        }

→ Ответить

3 года назад, # ^ |

Why does the second split will split into (6,7,6,5) and (5,8,5,1) rather than (6,7,6) and (5,8,5,1)?

→ Ответить

shubham84

3 года назад, # ^ |

Thanks for the explanation got it.

→ Ответить

Letscode_sundar

3 года назад, # |

Nice Contest and finally I have become a PUPIL.

I was able to solve both A and B within 45 mins for the first time and got stuck at C without knowing trees .

Can anyone explain E please?

→ Ответить

ChickenInKitchen

3 года назад, # ^ |

nice bro i was stuck on B for almost the whole contest lol had to solve C and D and I found them much easier than B :(

→ Ответить

utr491

3 года назад, # |

In D can't we just take half the edges every time?

→ Ответить

3 года назад, # ^ |

We can't do this in simple way. Because edges are defined by vertices we ask. So if we want to check edges (1,2) and (3,4) just two edges, then answer to our question will also may have edge (2,3) if (2,3) is connected in initial graph.

→ Ответить

3 года назад, # ^ |

r57shell, can you explain why the binary search on the Euler Tour will never "leave edges behind"? Like, edges whose one endpoint is to the left of the midpoint and the other endpoint is to the right. I understand that that won't happen on the first or second split, but it's not clear why that won't happen as the binary search progresses.

→ Ответить

3 года назад, # ^ |

Explanation turned out to be long

→ Ответить

3 года назад, # ^ |

But when you go through (u, v) the first time, you add "u v" to the Euler Tour. The second time you go through (u, v), you add "v u". Assuming the answer is (u, v), isn't it possible that one of the binary search splits will put "u v" in separate segments ("u | v"), pick the segment that contains "v u" (since that is the answer) and later on another binary search split will put "v u" in separate segments ("v | u") and now the answer won't be in either segment?

Maybe you tried to answer that, but I still can't see why that wouldn't happen...

→ Ответить