The title says "Разбор" which is not translated ig

Where can I read more about the XOR property mentioned in problem A?

Alternative solution for D: we can compute maximum distance of some node for each node in a tree, now if k>maximum distance between any two nodes , number of connected components is n. let number of nodes with maximum distance be x. then for k=x, answer is n-x+1. Now iterate from x to 1 , answer for k=y is n-(freq[y]+freq[y+1]+freq[y+2]......+freq[x])+1,where freq[x] denotes number of nodes with maximum distance equal to x. link to submission

keep them parabolas to yourself

There is an easier and more beautiful (imo) observation in C:

When we know that we need to find such a $$$k$$$ that $$$(b-k)^2 \lt 4ac$$$, we could rewrite this inequality as $$$k^2-2kb \lt 4ac-b^2$$$. $$$4ac-b^2$$$ is fixed for one parabola, so for each parabola we need to minimize $$$k^2-2kb$$$. But this is also a parabola (but there is $$$k$$$ instead of $$$x$$$), so its minimum is in $$$k = \frac{2b}{2} = b$$$. Now we can just binary search for $$$b$$$ in the sorted array of $$$k$$$ and check the closest values to $$$b$$$ to the left and to the right of found value in the $$$k$$$ array to satisfy the $$$(b-k)^2 \lt 4ac$$$.

no need to think, a brute-force solution works for problem 1805A - We Need the Zero

My solution link: 200395467

def xor(n, a, x):
    b = [None for _ in range(n)]
    for i in range(n):
        b[i] = a[i] ^ x
    
    ans = b[0]
    for i in range(1, n):
        ans ^= b[i]
    
    return ans == 0


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(256):
        if xor(n, a, i):
            print(i)
            return
    print(-1)


_T = 1
_T = int(input())
for _ in range(_T):
    solve()

Can someone explain Hint 2.2 of problem F1?

In hint3 of solution of F:

How to solve the problem if ai≤1?≤2?

There's an extra '?' character

Problem A, hint 1: $$$A \oplus 0 = 0$$$ should be $$$A \oplus 0 = A$$$

Problems were nice. And to make this comment less nonsence

In D every vertex that was chosen on i-th step has at most 1 neighbour which wasn't chosen yet and it will be chosen on (i-1)-th step (also it can't be leaf). So you can search only for leaves with distance i from diameter ends, and with those neighbours they will be all i-th chosen vertexes

Actually, it's big overthinking, but anyway

Problem C is a good example for ternary search. Solution.

Great contest! if you people feel stuck on Problem A, Problem B, Problem C, Problem D then you can refer to my video editorial here-video editorial

There is a simple solution to problem E, which works even if MAD operation is defined as max value appearing at least k times.

I tried a math approach but my solution fails at test case 5

https://mirror.codeforces.com/contest/1805/submission/200453634

anyone could help?

I overcomplicated my approach to C https://mirror.codeforces.com/contest/1805/submission/200453634 it gives Wa test 5 could anyone help?

Is Task C somehow related to task A of the first day of the regional stage of the VSOSH 2023?)

In problem C, at last we need to find a k which satisfies the equation $$$b - \sqrt{4ac} \lt k \lt b + \sqrt{4ac}$$$.

But how do we find any such k if $$$4ac \lt 0$$$? i.e. how do we find a real number between two imaginary numbers?

I solved E using (segtree + euler tour + mo algorithm + coordinates compression + frequency array).

Submission: 200485345

Has anyone solved E using rerooting technique?

Can anyone explain Question D in more detail?

I have different solution for problem D. Let's calculate farthest leaf from node i (this can be done by rerooting) and keep this value in fd[i] (short for farthest-distance). Now, for specific k, we check if node fd[i] is greater or equal to k. If this statement is false, then this node is isolated from every other node completely. Otherwise every node which satisfy this statement will be connected into one whole component. Thus we can calculate number of isolated components by prefix sum and add one as a "main" component. Consider fact that you can get answer n + 1 so you have to print min(n, answer).

Here's code for better understanding 200435906

P.S. If you liked this explanation or it helped you solve this problem, please add me as a friend. Reply if you need proof for this type of solution.

In problem C, can someone point out my mistake? 200462857

Finally became specialist! :)

E's idea is pretty straight forward yet somehow I failed to notice the simplest implementation...
I noticed that the biggest value appears more than 2 times will be the answer for all edge and all values that appear 2 times will update all the edges that are not on their path, yet to update and maintain maximum value on a tree in O(1) or O(logn) is beyond me(in the worst scenario n/2 updates)(and yes, I thought about HLD which I only know about the general idea).
The lesson here(at least for me) is: practice your tools until you are perfectly familiar with it, so you know exactly what it can do, what can be done with it and what can't.

My submission 200473816 for F1 has passed but I believe it should fail. I have represented every number in the form a.m + b where m = 1000000007 and b < m. Since the number can reach $$$2^{3000}$$$, it should still be insufficient to store such numbers. Can someone please look into this?

Is that 3 dfs in D a common trick to find all ending nodes of diameter? Can't figure out an efficient way to do so during contest.

great round

For F2 the smallest K that works is 43

There is a $$$O(Nlog^2N)$$$ solution for Problem E using Sack on tree..

We can root the tree at any arbitrary node. Now every edge between a parent and child in the tree will break the tree into two components. One of the components is the subtree of the child and the other component is all the other nodes. Now if we had to find the largest value having a frequency greater than x, we can do that normally with sack. However, it won't work for the other component. To solve for the other component we can have an additional data structure. Initially, we will add all the node information to this data structure. Then we can start with our sack on the tree. Whenever we add any node to the data structure for a subtree, we delete it from the additional data structure and vice versa.

Now coming on to the data structure required. We have to support the following actions, increase or decrease the frequency of any value and find the maximum value having the frequency>=2. For performing both of these operations quickly we can use a map and set together. We can update the frequency in the map and then use the set to answer queries about the maximum value. We will have to use a frequency array instead of map for our code to work within the tl.

Implementation

For D

let $$$min(f(k)+1, n)$$$ equals the solution for k

If we have x nodes that their farthest distance are less than k So, f(k) equals $$$x$$$.

I think this approach would work if this statement is true

let d(x,y) equals the distance between x and y. Then suppose d(a, b) >= k and d(c, d) >= k then one of d(a, c), d(a, d) must be >= k which means if the vertics is not indvidual, then it is connected to all other non-indvidual vertices

which means there is one or zero big connected component and all the other vertices are indviduial. So the answer of k should be the number of indvidual vertices ( + 1 if their number is not (n)).

which equals the first equation $$$min(f(k)+1, n)$$$

this is the approach I used in my solution here but it got WA 4

Could anyone please tell me where I went wrong?

excuse me, for question C, if there exits a solution so the max k for this open upwards parabolas is bigger than which has been input and the min k is lower than which has been input, so I tried to check : double nma = b[i] + 2 * sqrt(a[i] * c[i]); double nmi = b[i] — 2 * sqrt(a[i] * c[i]); also there are some special I did checked xd. but wrong answer on test(2,57), is that mean "double" can not fit this solution? Sorry about my poor English. Here is my code, thx if you can drop some advices. https://mirror.codeforces.com/contest/1805/submission/200577146

My O(nlog^2(n)) solution to problem E using small to large merging technique. Implementation

Why couldn't I passed promblem E with Segtree + Mo's algorithm,or this way is wrong,can somebody help me,thanks so much! 200585844

Dumb $$$O(N\sqrt{N}\log{N})$$$ solution using Mo's for problem E which runs very fast: Link

1805C - Place for a Selfie A simple solution for C 200620934

I got TLE on test 5 in problem F1,I think my progress time complexity is O(n^2 logn),can sombody help me. This is my submission,thanks so much! 200650061

I tried to use dsu on tree in problem E,I think its time complexity is O(nlogn),but I got TLE.can sombody help me. This is my submission,thanks so much! https://mirror.codeforces.com/contest/1805/submission/200871054

I have a question about F2.

Here is one a submission.

I used the same solution as F1, but instead maintained each number and its number of occurrences, in the random case the different numbers are few and far between, the code works fast, but it gets time limit exceeded on test 26.

I would like to know what kind of data can be used to maintain a large number of different numbers during the operation. Can anyone help me?

My English is bad, if there are any grammatical errors, please point them out.

for problem E, my approach is to flatten the tree and apply mergesort tree for queries (similar to number of unique numbers in range but here we need to find maximum value non unique number).

Im getting wrong answer in testcase 18.

my submission: https://mirror.codeforces.com/contest/1805/submission/200885370

please anyone say whether my approach was wrong or any mistake in my code. thanks in advance.

Alternative Solution to E in $$$O(nlog^2n)$$$:

We can use small to large merging technique. We will maintain $$$3$$$ vectors of sets:

$$$\cdot$$$ $$$Current: $$$ will maintain current $$$MAD$$$ values in subtree $$$\newline$$$ $$$\cdot$$$ $$$Unusable: $$$ will maintain values that are occur less than $$$2$$$ times in the other created tree but occur more than $$$2$$$ times in the total tree $$$\newline$$$ $$$\cdot$$$ $$$Other: $$$ will maintain the largest values that occurs more than $$$2$$$ times in the total tree but less than the values is $$$Unusable$$$ $$$\newline$$$ First one is pretty easy to update, just update it when you currently have less than $$$2$$$ values in the node but will have more than $$$2$$$ when updating it with a subtree.$$$\newline$$$ Second one is updated is a similar way, if you have more than 2 values not occurring but updating it with a subtree results in less than 2 values not occurring add to this set. Also when we add to this set make sure is the value occurs in $$$Other$$$ erase it from there $$$\newline$$$ Third one is a little bit more annoying to update. Find the value right before the current value that occurs at least twice in the tree. Make sure it is not the smallest value in the tree and also that this value does not occur in $$$Unusable$$$. $$$\newline$$$ After doing the merging mentioned right above, we have to do a little casework. $$$\newline$$$ $$$1.$$$ If $$$Current$$$ is empty and number of values occurring at least twice is equal to the amount of numbers in $$$Unusable$$$ the answer is $$$0$$$ $$$\newline$$$ $$$2.$$$ Let $$$max$$$ define the largest number that occurs twice in the tree. If $$$max$$$ is not in $$$Unusable$$$, the answer is $$$max$$$ $$$\newline$$$ $$$3.$$$ Otherwise the answer is equal to the maximum of the largest number that is in $$$Current$$$ and $$$Other$$$ $$$\newline$$$

First log factor comes from the sets, other one comes from small to large merging. Be warned the constant factor is extremely tight and i had to do many things to barely fit into TL so this is not recommended.

Implementation: 201189988

Please add the rating of the tasks in the archive:)

Actually, for problem $$$E$$$ small to large merging is an overkill.

The first thing to notice, as the editorial states, is that numbers that appear once or thrice can effectively be accounted for quite simply. Thus, we only need to consider numbers that appear twice. From here on out, assume that every number appear twice.

Of all the numbers that appear twice, one of the numbers is going to be the maximum (as in, find the maximum number that appears twice). Say this maximum number is $$$x$$$, and it appears on vertices $$$u$$$ and $$$v$$$. Then, for all edges not on the path from $$$u$$$ to $$$v$$$, the maximum number you can get is going to be $$$x$$$, since $$$u$$$ and $$$v$$$ will be on the same connected component after the split.

Therefore, we only have to deal with vertices on the path from $$$u$$$ to $$$v$$$. To do this, we can root the tree at $$$v$$$ (or I guess, by symmetry, at $$$u$$$) and naively update the connected components.

If done right, the complexity of this approach is $$$O(N)$$$. In my implementation (211295484), the complexity is actually $$$O(N \log N)$$$ because I used maps, but you can do it without maps.

I have an interesting but unproven algorithm for F2. Would be cool to see someone find better conditions / prove tighter bounds, I've been trying. 303373657

My intuition relied on two observations (everything is 0 indexed here, a[0] = 0 always):

-> The number of elements that are "close to a[3]" should grow exponentially (or even faster), because there are so many pairs "close to a[3]". Intuitively, ncr(3, 2) = 3, but ncr(4, 2) = 6, so there should be a superexponential blowup of "close to a[3]" pairs. (but I bound it to exponential in my analysis because it's easier to prove).

-> Eventually, if a[3...n] are all "close" to each other, what happens is that the array looks like repeatedly subtracting a[1] from a[3..n] (and setting a[1] = a[2] — a[1]). Since all the deltas are the same, you can just simulate it in O(1) per step. (but you need O(n) to reconstruct the finalized array once a[2] gets "too close" to a[3]).

--- To formalize "closeness", the best bound I could derive is something like n * log_2(n) * log_3(n) * log(MAXAI) which is... extremely loose lol (also the below is kind of handwavy)

"closeness" can be defined as:

1. if 2 * a[3] > a[n], this means that no two numbers with i, j >= 3 can pair with each other, justifying the need to only look at pairs that include a[1] or a[2]. The number of numbers that satisfy this condition grows as a function of f(n) = 3 * (n-3) + 3, so it takes log_3(n) iterations to converge to a "good state" in the worst case.

2. On the other hand, if 2 * a[2] <= a[3] (along with the previous guarantee), then we know that we will only consider pairs (a[1] + a[i]).

(Actually typing this part out, I have no proof for the following justification either :shrug:)

In O(1) steps after that, a[2] must decrease by more than half, similar to why gcd converges in log steps.

So the claim is that the algorithm goes in repeated steps of 1, 2, 1, 2, 1, 2, 1, 2 for log(MAXAI) steps. But each "chain" of step 1 should take log_3(n) steps.

When I implemented these checks, the number of iterations did not exceed 45, far less than log(MAXAI) * log_3(n). It could be that the analysis is very loose, could also be that it's hard to make a countertest. You could definitely make smarter checks than I did, I was just very safe in the analysis since it's so hard to reason about ;-;

I don't think you can get better time complexity than the editorial, since the editorial only considers log_2(MAXAI) elements, but it still may be interesting to look into, since the observation that you can just literally simulate on O(1) elements in some cases, and shrink the array's potential in half is powerful (offset by having to manually simulate some cases in nlogn).

(I also think this observation might just straight up be compatible with the editorial observation, proving you only need to do K^2logK + K^2 work, but that seems horrible to implement)

Edit: K^2logK was some simple changes, 125ms :) 303388839

I do wish the algorithm had better provable bounds, it really reminded me of gcd :/

https://mirror.codeforces.com/contest/1805/submission/372642770

This is my submission for F1. I basically store [quotient, remainder] of a two pairwise element sum of the array in priority queue and pop the minimum one out. But the number can go till 2^3000 * 1e9, if all 3000 numbers are 1e9 which would overflow quotient.

Why does my solution work?