Hello! Codeforces Round 847 (Div. 3) will start at Jan/27/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of **open hacks**.

You will be given **6-8 problems** and **2 hours and 15 minutes** to solve them.

Note that the **penalty** for the wrong submission in this round is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participant of the third division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, DmitriyOwlet and Vladosiya. Also this time, molney suggested one of the tasks.

We would like to thank: alwyn, morasha3, csegura, BledDest, stevenkplus, Darko, Coki628, Crutch, Qwerty1232, Jostic11, liouzhou_101, Jeffin, AW_Flister, glebustim, yorky, mango_lassi, 74TrAkToR, ErrorDeveloper, Be_dos, MODDI, Vercingetorix for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

**UPD**: Editorial

Hoping for the first time getting AK (solve all problems) in this contest.

Hoping for 6-8 NP-hard and NP-complete problems :D

Yes div. 3 round thank everyone

All the best !!

Congo

Congrats

Why has system testing not started yet!!!

The date in the blog needs correction i guess.

I just hope this round doesn't become unrated and no hearts are broken ;)

Hoping +ve delta for every participant.

-ve delta teaches more than +ve if you want to grow.

Yes you are also right. But if somebody already have rating < 900, how can he be happy with getting more -ve delta.

You know that's impossible right ?

Hopefully there will be no error like the yesterday contest

BTW the kitty in the Vladosiya's profile is very cute (◠‿◠)

It is Vladosiya

Iam new here and I didn't get the meaning of "penalty for the wrong submission in this round is 10 minutes", can anyone explain? .. Thanks in advance

Sorry, I am unaware of this.

No. In div3, div4 and education rounds, contestants are ranked by the lexicographic order of (count of problems you've solved, (-1)*sum of the minutes after the contest begins of your accepted solutions), and every wrong submission you submitted (before the correct one) will let the second term -10.

Stupid :}

If you make a mistake, then 10 penalties are added to your total penalty.

hey guys give me negative vote I want to be the 1st of the worst Contributer

no one can beat me!I am all thw ay down.

hoping to be Expert on this contest... Wish me Luck ... xD

if you try, you will become an expert and without luck

Some have the privilege of falling to expert, and some don't.

Good Luck Buddy ..

What if I can't solve at least 3 problems?

There nothing wrong as long as you not give up trying.

thanks for the advice

As a tester, tested.

Hopefully it will be rated round. And all problems are not Np hard .

As a participant,participated.

is it possible to getting everyone positive ratting?

The total delta of every contestants will

definitelybe negative due to the algorithm of codeforces. However, there are many new accounts (or alt accounts) which participate in contests with 0~1 problem solved, each of them bring +1400 rating to the total rating of CF users (by the first 6 contests they take), which makes the total rating ofactiveCF users being balanced.Hey, bro, seems like you know everything about the rules, where did you get it?

Basic rules

Rating algorithm

Hoping to get some positive delta guys!

Very nice new rules for Div3 contests

what do you mean by

new rules??Hope to solve at least 5-6 problems

omg blue round

Hoping to remain specialist:)

Hoping for you to be an expert :)

Is it easier to increase rating in div3 than div 2 considering I am a specialist?

Yeah, because mostly you will be on the top of the ranking list so codeforces favours those who are top in the scoreboard. But you might fall hard if you can't solve according to your rating as you should do as a specialist.

Finally, my time to shine

I have a question that usually I only need to take part in at least two rated rounds, but why this time I have to take part in at least

fiverated rounds? I'm very frustrated because I had only taken part in four:(`Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.`

Since you are green, you don't need to worry about it.

Anyone from Bangladesh (class 10 or lower)?

ChatGPT here, participating in this Round ^^ This will be Fun.

I bet, you wont get single question right,,, if you are using only CHAT GPT, and no Human logic/intelligence ...

will be using only CHAT GPT here, + very minor fix of the code if needed (missing include, output formatting, etc..) Let's see :) :)

First rated Round for ChatGPT, succeeded to solve problem A. Good start?

sure, good one...

My Turn ...... :)

Can someone suggest me some topics which are most common and helpful under problem ratings from 1200 to 1500?

number theory, greedy, implementation, constructive algorithms :)

Thanks!

include binary search, two pointers, interactive as well

OMG I am very exited, I wish to you positive delta!!

Hoping to be specialist :) There are only 4 ratings to go Don't let me down pls :)

I have been wait many days for div-3 contest. This is my entering contest on codeforces.

I can just solve 2 problems in Div.2, hope in Div.3 I can solve more

Please no NP-hard problems. Please no NP-hard problems. :D

I wish there were more Div.3 rounds as they've decreased nowadays.Excited for this one!!

Can't wait to see hmzqaq's performance in this round. (He's duck_pear)

first unrated div3 contest for me..........it's unbelivable :)

Cheers buddy

Thnx :)

Hoping to be a specialist... Wish me good luck.

Well, it seems that I failed... :(

Hopefully I can reach expert

Either my Code is Wrong or Something Else PROBLEM=B,

Verdict: WRONG_ANSWER Input 7, 2 2 1, 2 4 2, 4 9 5, 5 17 11, 3 15 10, 4 4 3, 5 20 15, Participant's output 1 1, 2 2, 1 1 3 4, 2 2 2 5 6, 5 5 5, 1 1 1 1, 3 3 3 6 5, Checker comment wrong answer wrong r: 15 expected, 14 found (test case 7)

Im getting same if i output the same thing

I'm getting something similar, on test case 5, my sequence sums up to 15. But it's getting wrong answer r: 10 expected, 9 found

Not a bug, actually. Just can't tell why it's happening during contest, but it's not a bug. The best I can do is to advice reading the statement carefully.

shit,, thanks

Got, It Thanks Bro

You were right. I reread it, made one slight change on an if statement, got AC.

A channel is providing solutions in youtube live during contest. This is not fair. The round should be unrated.

I think this comment should be removed asap so less people will see the link.

The same things had happened in some of the div2 contests before directly. However, those contests were rated too. So I thought it would be better to ignore them and just remove cheaters afterwards instead of making the whole contest unrated.

How will you determine the cheater if he didn't copy the code but only copy the idea behind the implementation?

so you saying that more than thousand people that write it fair won get their delta because of one man?

it's much more unfair to make it unrated, because most of the people solved the problems on their own.

Was it in your youtube feed?

This contest is a little hard but quite interesting comparing with other div3 contests. Thanks for the authors' and testers' hard working!

lmao this was probably the easiest div3 in a long time since most div3 participants only solve till D/E

Wtf this is not Div. 3

Sir Please be respectful here. Don't use those hard word. ~~~~~ I am sure you can express yourself even without those slang. ~~~~~

and you (both of you) please go back to solving tasks?

Bro F is out of my league. I have already solved till E within 50min. Waiting for editorial for elegant solution of F.

4000 + submissions of E, and you say its not div3

it's actually F just copy the code centroid on internet and done-.-

do you mean centroid decomposition?

It is

nah, u could think 2 minutes longer and make it in O(n) easily

MikeMirzayanov

Someone with codeforces handle demons_paw is providing solutions of Codeforces Round 847 (Div. 3) Codeforces Round #847 (Div. 3) in youtube live during contest. This is not fair. The round should be unrated. I have sent the youtube live video link in your codeforces inbox. Edited**

Why do you share this in a public discussion post during a contest ? At least should wait until it’s over

I think, there is a possibility that the youtuber can delete the live video at the end of the contest.

By the way, now you really should edit the comment and delete the link so that no one else can use it

Thank you, we've already seen it and we're really upset about it.

Please don't cheat on the rounds! Firstly, it is forbidden. Secondly, it won't help you develop your competitive programming skills at all :(

Was it in your youtube feed?

Finally I was able to use first 31 digits of pi from my template :D

first 30 digits were given in sample cases

Didn't notice lol

problem f is really one of the best i really like it

Me after solving A,B,C,D,E

Who else can remember PI without searching the google =)))) BTW, I really love all of the problems

you don't have to remember pi, neither do you have to google for solving that problem. That's why I liked the problem (hint: look at the testcases)

you could just copy pi digits from the sample input xD

"OR" really confused me :(

Problem G was worded very badly in English :notlikeblob: I wasted about 20 minutes just trying to understand the problem (the statement is much better now). Using terms like move / jump / turn interchangeably was just confusing, surprised this wasn't picked up in testing.

Even after I solved the problem, I had zero clue what this meant: "The same bonus can be used an unlimited number of times, but not more than once per turn."

?????

Oh well, still got 8th place :sunglasses: Screencast + editorial at https://www.youtube.com/watch?v=fVaNJ2eTegw&ab_channel=JoshuaChen :)

Problem A: The observant programmer might have noticed that one of the test cases included all 30 digits of pi for a quick copy and paste

Problem B: I spent more time deciding what the best way to implement would be than if I had just picked the slowest way and started writing it immediately

Problem C: Neat problem, interesting observation that the answer can be deduced from just the first 3 permutations and all of the other ones are irrelevant. Spent 30 minutes debugging poor code though.

Problem D: Standard frequency map problem

Problem E: A little disappointing that the solution was readily available on Geeks For Geeks, pretty sure most people just pasted the algorithm because it's allowed.

Didn't have time to solve F or G but F looked interesting.

how to solve E

I literally don't know. Copy and paste this. https://www.geeksforgeeks.org/find-two-numbers-sum-xor/

can you explane why 5 is -1?

x = 5

a = 5

b = 5

a OR b = 5

(a+b)/2 = 5

It is XOR not OR

Exclusive OR = XOR, if you click the link it redirects to wikipedia XOR article https://en.wikipedia.org/wiki/Bitwise_operation#XOR

oh my bad

thank you so much :)

Honestly I would think that means OR too but I am familiar with the XOR operator symbol ⊕

was able to find solution to C in first glance but got stuck at implementation and spent whole time debugging to find out that .resize() doesn't works if called multiple times within another loop, the solution got accepted just after the contest got over :/

My solution for C -https://codeforces.com/contest/1790/submission/190877527

You are almost reach the most elegant answer to Problem C. All you need to do is just figure out the first element of the original permutation and combine it with the new permutation that does not have the first element.

i have shared above the accepted solution i did it using frequency array maintaining the highest count of an element in a column and that will be the number pi for the ith position. did same from the back using 'j'

how do improve in these type of questions/observations?

practice

Do we have to solve problem E using recursion?

No. You just need to check if x is even and if (x + x/2) ^ (x/2) is equal to x. If both conditions are true, print x+x/2 and x/2 else -1.

How did you think of this?

Noticed that in examples a and b are equal to x +- some number. Found such numbers using bruteforce for x in [1, 256] and found out that there is either no solution or at least one solution with x+-x/2.

Seems like checking if ( x & 1 || x & x >> 1 ) is false works too.

Wow. People hate this comment so much :/

Did you hack your own solution PURPOSELY? What's the logic behind it?

To be honest, there is not that much logic behind that. Was wondering, what would happen, and desided to try this dumb idea out...

How to prove D?

Obviously if we have multiple of the same number we must start a new doll. And it also optimal to continue the streak of a previous doll if we have one. So greedy covers both cases.

u proved nothing

A new sack has to be started for number i if there is no number i-1 available before it. We can use a frequency map to tell if i-1 is still available and reduce 1 from f[i-1], or open a new sack if it is not. This would minimize the number of sacks, as only numbers with a value of i+1 can follow behind numbers with a value of i.

starting the set from smallest doll, we will take elements in set until current+1 is not present in array.{current is initialized with smallest doll value}. Example :- (1,1,2,3,3) starting from 1 we will take 2 and 3 now array/Map contains (1,3) Again starting from 1 we can take 1 only(as 2 is not present) Now we will start from 3 as the smallest element present is 3 Thereby 3 sets will be required intotal

how's D done anybody ?

Sort the array and put each element into a frequency map. If freq[a[i]-1] == 0, increment answer by 1. Else, freq[a[i]-1] -= 1, because it can no longer be used. Then freq[a[i]] += 1 because it can be used for a bigger doll.

F was the same as: https://codeforces.com/problemset/problem/342/E

speedforces

Problem F

This problem 342E. Xenia and Tree is almost similar to today's problem F :)

:(

Is there any wrong in my B? I output $$$s-r$$$, $$$\lceil r/{(n-1)}\rceil$$$ n-2 times and $$$r-(n-1)*\lceil r/{(n-1)}\rceil$$$. I have no idea why it is wrong.

I was trying to find an elegant way to have n dice sum into the desired sum, and I settled on initializing an array with all 1's then replacing as many as I could with the max allowed dice number, then replacing the final 1 with the remainder.

There is a chance that s-r would be smaller than r−(n−1)∗⌈r/(n−1)⌉ (the dice with largest num will be taken) . You have to reduce that last number by distributing to elements other than s-r until it is smaller or equal to s-r.

Lol, first tournament I have answered something. :)

Good job!)

Me also

Good job!

How to do Problem F?? I thought of an approach of applying bfs every time I make a node black (bfs from ith node in array c) and whenever I reach a node which is already black I make my mini variable (which stores the min result till now) to be the min of previous mini and level of this bfs which took me to a black node

Why I think this should run!! lets say in worst case scenerio I have a linked list type tree then ttou can easily observe that you would take atmax n bfs steps to identify the first black guy then for the second time you would only take atmax n/2 and similarly next time n/4 .... which leads us to a very simple series sum n+n/2+n/4+n/6+....+n/n which I thought would work within the given time limit Also whenever my mini becomes 1 then I am simply breaking out and puuting all my ramaining answers to be 1 only

This apporach gave a TLE on test case 18 :(

can anyone please tell me what must be wrong in my approach

PS:- Sorry for the spelling mistakes if any :)

The worst case scenario is a snowflake with sqrt(n) tails, every tail has sqrt(n) vertices and first sqrt(n) black guys are ends of a tail. The first sqrt(n) bfs will take n steps, so in worst case this algorithm has time complexity o(n^(3\2)). I think, that in this problem you must use LCA instead of BFS to find distances between the vertices

Ohh Now I understood why it was giving TLE

I got frustrated in the contest as I couldn't think of this worst case scenerio

Thanks a lot man!

what is wrong with O(n^1.5)? Are we supposed to do better than this? I am running TLE on test 18 also.

It would pass I guess But in my case I was using set instead of visited array (as array construction would take n time which would definitely give TLE) but since I was using set it would add extra complexity so I guess due to that it's giving TLE.

I am just unable to think how to keep track of visited nodes within time limit as I want a new visited set or array for every ci.

Did you AC at the end?

My idea is to go through each black node and do a dfs up to answer steps, (answer is the min distant so far) and see if I can find another black node that is closer than answer. If I find one, update answer so that next time we can dfs less depth. However, this will tle at test case 18. I thought the time complexity is O(n^1.5), but clearly this will TLE. Appreciate if anyone can help me understand why.

My submission 190916688

Any hint for F?

you can dfs to update the minimum dis of every white nodes to the nearest black node, and we need to set the maximum dfs dep to the curr ans.

Or just spam Centroid (it's very similar to this problem 342E

Let us not mention the fact, that tasks E and F are very well-known, what is a purpose of giving task A?

Tasks B C D G were great though.

Is F well known coz it is repeated? Or the concept well known as well? Hints also pls :D

This task can be solved with centroid decomposition. If you are using it, you can just follow some well-known approach.

I wasn't participating the round, but it seems to me that this task is solvable by DSU. If we will suppose that there can't be two adjacent black nodes, then if you will treat black nodes as deleted, the answer is the size of minimal component plus one. However I'm not sure this will work. But the fact that the task can be solved with centroid decomposition using some well-known approach makes this task well-known and thus not suitable for the round.

I am wondering how you tell your opinion about the problems without participating in the round, I think something is sus here

See, I'm a master, and I can read the tasks, think a little bit and come up with a solution :)

Well not all the master think like you, I hope you're right ...

I really liked A because instead of calculating the value of pi upto 30 places or searching it on the internet , i for a moment looked at the samples and found the asnwer's is already there and tbh it made me chuckle a bit and i started rest of the contest with smile. i don't know it's purpose and but yeah that's how it made me feel!

My solutions for the first four problems:

Problem A:

SpoilerWe can create a string with the first digits of PI, and iterate over it with a counter, stopping the loop if a mismatch happens.

Problem B:

SpoilerDifference between $$$s$$$ and $$$r$$$ is obviously one of the dice elements, for the rest we can create a vector of $$$n-1$$$ elements and increase each element while decrementing $$$s$$$. If $$$s$$$ reaches $$$0$$$ we can exit, print $$$s-r$$$ and the $$$n-1$$$ elements.

Problem C:

SpoilerWe can maintain an array of $$$n$$$ elements that holds our guesses. For each of the $$$n-1$$$ vectors we check the position of the $$$nth$$$ element, if it is higher than our guess we increase it to it's position, since the highest position it will reach will be it's true position, this is easy to see since for each element except the last there will be a vector where all the elements before it are present. In the end we will be left with $$$2$$$ elements with the same position of $$$n-1$$$, we will take the one with the highest frequency to be the last element, since it is the last, it will always appear in the end except for the case where it isn't present.

Problem D:

SpoilerWe maintain an ordered frequency map, we will iterate over that map, if the difference between the $$$ith$$$ element and the $$$i+1th$$$ element is more than 1 then we know there was a disconnect and we add the frequency of $$$i+1th$$$ element. else if the frequency of the element increased, then we know that sets were added and we add that increase in frequency,

E is a bit of a well known problem. We are trying to get two elements with sum of $$$2n$$$ and xor of $$$n$$$, you will find plenty of code snippets for it or finding two elements with xor $$$x$$$ and sum $$$y$$$ in general.

Could D be solved this way but counting decreasing values instead of increasing?

Not sure if I am understanding correctly but I assume you are talking about the case that they are continuous sizes and we saw a decrease in the frequency. say {2,2}, {3,2}, {4,1}. In this case we can't really make a guess about the number of sets, since we are trying to minimize a decrease in frequency would be interpreted as one/several of the sets ending. The answer here would be 2 sets, {2,3,4} and {2,3}.

Can some one explain me how were the rules of the game for problem G?

I didn't understand the problem statement :(

hi im new here, is this rated or unrated cuz i wanna get a rating but when i click on my profile it says that this contest is unrated, but in this announcement it says its rated, thanks :)

All contests will be shown as unrated until the rating update is calculated.

oo okay thanks a lot

First time solve 4 problem in div 3.Thanks every problem setter.

Is there any issue in copying the given sample testcases to clipboard, in

`Problem G`

?Problem F is similar(same) to 342E - Xenia and Tree! I would like to ask why to give a Centroid Decomposition problem in Div3 round? (it's for < 1600 people) is it expected from them to know Centroid Decomposition??

Cause this problem can be solved without centroid decomposition. Don't assume your way is the only way to solve a problem.

I spend way too much time reading random CF blogs and immediately thought of centroid decomposition because there was a recent action on a blog about it. But I've never even experimented with the algorithm so I didn't even try to solve it with my remaining time.

We can solve this problem by DFS with maximum depth set to the current answer. I passed it without centroid decomposition.

Is this n log n? Because if the black vertices were adversarially chosen then they have to be at least at the half way distance between two other black vertices?

Although I can't prove it I think so. IMO the worst situation of my solution is: The graph is a chain with 2^n+1 nodes, and black nodes are added by the order (0, 2^n, 2^(n-1), 2^(n-2), 3*2^(n-2), …) where time complexity is O(n*log(n)).

Unless I am misunderstanding your solution, the complexity is at best $$$O(n \sqrt n)$$$. Consider a set of paths of lengths $$$b, b+1, \dots, 2b$$$ merging at a single vertex, and $$$O(n)$$$ leaves connected at that single vertex. The vertices at the ends of the paths turn black one by one, starting from the longest path. For the first $$$O(\sqrt{n})$$$ vertices that turn black, every leaf adjacent to the path merging point is visited, thus at least $$$O(n \sqrt{n})$$$ vertices are visited in total.

Enlightening example, thanks

What is the number of edges in this case? I think the complexity is O(min(m, n*sqrt(n)))

upd: ...My comments above is wrong, I was thinking, for each node, there should be a value stored indicating the nearest black node, If that information is maintained, not necessarily accurate but should be accurate if the value is smaller than current result, then for this test case, bfs should stop when reach the 'root', the complexity is O(m).

I tried solving F using bfs with some optimization, but got TLE on test case 20, can you or anyone please help with what is the time complexity of my solution, and why it's failing. 190874842

can you please explain that how is the complexity O(n√n)? I am not able to understand ur previous answer?

We solved it without centroids (didn't even think about it), so we decided it would be just a great task.

Had solved all problems in a Div 4 earlier, today solved all problems in Div 3.

Can someone please look at my profile and suggest what's happening? I really don't know. Thank You.

All problems solved (if no FST).

A: Ctrl+C the last line of the example and Ctrl+V to the code.

B: Do division with remainder for r and n-1.

C: For numbers with initial position i in range [1,n-1], the position after remove a number will be i or i-1. If i==n, the position after remove will be

onlyi-1. Therefore by count the miminum and maximum position of numbers in each permutations after removal, we can find their initial position.D: Greedy. Always remove a maximal equidistant sequence with common distance 1. But we need implement this solution by an ordered map. We count the time of occurence of each number and store them in a map, and for each adjacent key-value pair [k1,v1] and [k2,v2], if k1+1==k2 we add max(v2-v1,0) to answer (because we can extend some sequences containing k1 to k2), if k1+1<k2 we add v2 to answer (because k1 and k2 cannot appear in any same sequence).

E: By the equality (a^b)+2*(a&b)=a+b, we need to let a^b=2*(a&b)=(a&b)<<1=x. Therefore, if x is odd number or x&(x/2) is not zero, there's no solution, otherwise (3*x/2, x/2) is a solution,

F: We use dfs to update the minimal distance of every white nodes to the nearest black node, but we need to set the maximum dfs depth to the current answer.

G: First we need to check if node 1 or any neighbor of 1 has token on it. If not, use bfs to search how many tokens can reach node 1 by any sequence of bonus nodes. If there's no such token, there's no solution; if there're >=2 such token, we can move them alternately to node 1. If there's exactly 1 token, we need to check if there's other movable token and how many times we can move them. We need to check for every edge (u,v), if u, v are both bonus nodes, mark them as "infinite move". Then for each tokens we check if they have any adjacent bonus node. Therefore, the final condition is: there's some other node adjacent to an "infinite move" bonus node, or the number of movable token (except the one can reach node 1) >= (the distance of the reachable token to node 1)-1.

You can do F with centroid decomposition.

Missed the last condition in G

Do you know exact proof for D? thanks

Here's this bizarre solution for E I found right after the contest ended (I solved it the same method with yours in contest).

Just try $$$(\lfloor n/2 \rfloor, \lceil 3n/2 \rceil)$$$, if their XOR is $$$n$$$, then that is the solution. else, -1.I don't understand why this approach works, but it seems like it does.Also, here's a very elegant solution for C, which I came up with because I didn't want to do make implementation a rigorous job. Basically,

just sort by sums of indices.Submission goes to 190790499.That's what tourist has done

Yep, I just saw. Doesn't change the fact that I found the method by myself, though. Let's just say that we both found it independently.

I found this during the contest, but forgot to check if their XOR is $$$n$$$.

x^y=x+y-2*x&y, this is why that solution works

Can you explain your dfs solution a little more?

The answer decreases on every step, and this rate of descent is very quick. For a worst case, lets say, the first two colored nodes are on the diameter of the tree, and the third colored node is on a centroid. You can see that now the answer is halved. So even on the worst case, we will use an average $$$O(n \log n)$$$ time complexity in total. If we consider every worst case (such as an "f$%&ed up star", a term I just came up with, which is like a star but there are $$$O(\sqrt n)$$$ paths with length $$$O(\sqrt n)$$$), the worst case will probably be $$$O(n \sqrt n)$$$. Definitely not $$$O(n^2)$$$, though.

UPD: actually I am pretty sure it's $$$O(n \sqrt n)$$$ or better even in the worst case, that "f$%&ed up star" in fact starts to get towards $$$O(n \log n)$$$ after $$$O(\sqrt n)$$$ steps, $$$O(n)$$$ each step.

I used the same logic for G but it gives wrong answer on testcase 5,i've spent two hours trying o decode but can't find it. here's my solution- https://codeforces.com/contest/1790/submission/190884446 any help is highly appreciated.

Try to add

`vis[v]=true`

after`q.push[v]`

.My first wrong submission also made this mistake, which caused distance was calculated incorrectly.

Thanks YocyCraft. My profile pic and face looks same after this silly mistake.

I use the similar idea for F (i.e. limiting the distance by using current answer for traversal) but using BFS to implement it but got TLE in case 18.

Any idea what's the catch?

(a^b)+2*(a&b)=a+b Where did everyone get this formula from, how does it work out. Explain, thank you.

(a^b)=(a|b)-(a&b) by the definition of xor

(a|b)=(a+b)-(a&b) by the inclusion-exclusion principle

This is my solution for F , it keeps getting TLE on test1 and i don't have a damn clue why:(

can any one tell ?

190880017

in the

`init`

function, the declaration is wrong. you need to specify the type.How to solve E(with proof)?

We know that, a+b = a^b + 2*(a&b) here a^b is given let say it is x, and sum is given as 2x so, 2x = x + 2*(a&b) => a&b = x/2 , so all bits of x/2 should be there in both a and b, and x should be even, if odd then answer is not possible

so, both a and b are atleast equal to x/2.

now bits of x should not be present in both a and b otherwise it will not be present in their xor which is x, so x^(x/2) must be 0, if not then ans is not possible else we can add x to any of them and answer would be 3x/2 and x/2 190824234

Where do you learn things like a+b = a^b + 2*(a&b)? I never seen it in my life

You can read about bitwise math properties or you can discover them through problems

well. my solution is bit complicated i guess but

1) it's not hard to prove that a+b = (a^b)+2(a&b) (consider 4 cases when ith bits are (0,0), (0,1), (1,0) and (1,1) and check that this statement is true)

2)by definition a+b = 2*(a^b) => a^b = 2(a&b).

2.1) it's not hard to see that if (a^b)%2==1 then there is no solution because a^b must be even because it's equal to 2(a&b).

2.2) but there is some even numbers that can't be answers too. lets consider some cases:

if a and b have the same leftmost bit X than XOR on position X must be (1^1)=0, but at the same time AND on position X must (1&1)=1 => this case is not possible, so leftmost bit in a and in b not in the same position. now lets say that a>b so leftmost bit in a is more that in b.

if a>b it means that on position X XOR equals (1^0)=1 and AND equals (1&0)=0. but we remember that (a&b)+(a&b)=a^b => X-1 th bit of a&b must be 1 (otherwise a&b + a&b != a^b) => but if X-1 th bit of a&b is 1 that X-1 th bit of a and b is 1 simultaneously => X-1 th bit of a and b is 1. => X-1 th bit of a^b is 0.

but we can use the same approach for every 1 in a^b. according to the above, if we see 1 in the position Y in a^b, then in the position Y-1 we MUST have 0 (otherwise we won't have a&b + a&b = a^b)

2.3) now we need to iterate over a^b and check if there is exist two adjacent indices M and M+1 such that M==(M+1)==1. if they exist, then answer is -1. otherwise we can get answer.

3) iterate over a^b. if bit X is 1 then a+=(1<<X) (a>b because i want so) and a+=(1<<(X-1)), b+=(1<<(X-1)) (because as i proved it above, X-1 th of a&b must be 1). thats all.

anyone can tell me test case which hacked D

Probably people using unordered map. https://codeforces.com/blog/entry/62393

Like this one for example https://codeforces.com/contest/1790/submission/190826838

i wanna test case

how to solve e ?

a xor b= 2*(a & b) after this observation?

x = 2 * (a & b)

So a and b has similar bits to x / 2, let's say:

a = x / 2; b = x / 2

But, to maintain equation (a + b) / 2 = x, a should be 3 times bigger:

a = 3 * x / 2; b = x / 2

If this is not a valid pair, then there is no answer

a should be 3 times bigger ? how i'm not getting this point?

if (a + b) / 2 = x, and b = x/2, then:

(a + x/2) / 2 = x

a + x / 2 = 2 * x

a = 2 * x — x / 2

a = (3 * x) / 2

thanks a lot _ /\ _

You're welcome!

i ran a brute force dp on small constraints and found out a = x / 3 and b = a * 3. Lol i can share my dp code if you wanna know about it

how can we conclude that is this is not a valid pair then no other pair is possible? I am stuck in this statement.. PLease help.

Nice problems like all other div 3s. orz ITMO University team

My solution got TLE on test on problem F

I've used Heavy-light technique.

I thought the solution should fit in the time limit, but I was wrong

Any thoughts why ??

My solution

solution explanationI made a vector to store black nodes,

light query is to pass through all of black nodes in that vector, and check the distance with query's node

heavy query is to run a multi source bfs and clear that vector

and BTW very nice contest today ORZ

Update : thie solution passed, i had to make a small change to make bfs code faster

**edit dont't try it, I made a mistake

In problem G why does this case's answer is "NO"?

Hi Guys! If you are upsolving and want help with video tutorials you can refer this: https://youtu.be/YEyg27tm2sQ

This contest had a lot of "standard" problems. Seems like both E and F could just be looked up, which is a little unfortunate.

I think F was a good one, but for E yes it was standard, Actually I just searched for "How to find two numbers a, b where their sum is S and their xor is x"

Agreed, I feel as though alot of people who did E just googled it, which makes rankings unfair.

You could google it too :)

I would not cheat

It's not cheating, because it's legal

You are not searching for a fresh solution for this problem, you are searching for a similar problem

It is legal according to the rules, but it feels unfair and I don't want to gain rating I don't deserve.

ok it's up to you :D

oh shut it now, googling is also a skill and searching for hints to crack the problem will help you in the long run

sve ću vas pobit majku vam jebem retardiranu

literaly nuke india and dont flinch

Problem F, why TLE? just java(use java17)?

My similar C++ solution runs for 800-900 ms, and jaTLEva often cost 4-5x times…

C is a harder version of https://codeforces.com/problemset/problem/1512/A

The data of problem C is too weak. There is not even a test case with $$$T=10000$$$. I hacked many people by $$$T=10000$$$.

How? It says "the sum $$$n^2$$$ over all input sets does not exceed 2⋅10^5."

Thanks. I changed the post.

Can you try hacking mine? I'm trying but it says

`Testcase can not be longer than 256 KB`

;-;with generator

The name of problem B looks pretty familiar :)

nuke cheaters pls

Concerns about problem E.

After the contest I visited a few solutions and searched online. There are codes available online to determine two numbers from their sum and XOR.I copied one solution and changed it a bit (i)in order to run for t test cases and (ii) set Sum to x*2,where x was the given XOR of a and b. It got accepted. Is it okay to have this type of problem which has solutions available online?

I solved till D :( because i got stuck at C for simple implementation bug which i couldn't figure out and took most of my time and then i solved D in the last minutes after doing C. I wish I could have more time for E! I will try my best to reduce these mistakes in the next round.

For F, how to prove the efficiency of "keep doing BFS from every c[i], but only push a new node in the queue if its distance is getting decreased"

How about the case when tree is

c0->c1->c2......ci->ci+1->....->cn

for each i, doesnt it takes O(n)?

I have solved problem F with sqrt-decomposition over queries in

`997 ms`

. Solution.We can divide all queries in $$$\dfrac{n}{\sqrt{n}}$$$ blocks with size of block equal to $$$\sqrt{n}$$$. When we reached a border of current block, we can run multi-bfs from all of black vertices in this block and calculate vector

`dist[u] = distance to nearest black vertex from vertex u`

. Also we can calculate distance between two vertices in same block with LCA in $$$O(1)$$$.So, solution works in $$$O(n \cdot \sqrt{n})$$$.

This was my solution from the testing phase, and I had one hell of a time squeezing it into TL. Thankfully, the problem authors increased the TL after this.

Nice contest. Had enough time to finish the dishes after solving 5 array problems as I do not know graph/trees.

problem F more like Xenia and Tree 2

190861468 can anyone try to hack my E solution? I do not have proof for this approach

I liked C and D, couldn't solve from E and above.

https://www.geeksforgeeks.org/find-pair-of-integers-such-that-their-sum-is-twice-their-bitwise-xor/?ref=rp same question

F problem, so many Python submissions got TLE, but the same of C++ can just AC, that's not fair! I think the tester at least should test some widely used language, not just C++!

the TL is 4 seconds, i do not think the authors could've possibly made it more otherwise people would just brute it, tourist's solution was under 200ms.

But some red can't pass it using python, so if we have different TL for different language, this problem will be solved. I know it's hard to change, but it's really a good direction

that is true, maybe Mike will make a change to allow custom TL per language in the future

it seems that no one can hack the code in $$$O(n^3)$$$ in problem C. I think this is a mistake. A better way is to make $$$1\leq n\leq 100, 1\leq t \leq 1000$$$.

How to solve F using DFS approach?

Let's call dis[u] as the minimized distance that all black vertices to u.

For each $$$C_i$$$ ，we DFS it while calculating the depth. When DFS v and dis[v] is less or equal to the depth, we break the chain.

We can demostrate that it's $$$O(n \sqrt n)$$$ ，because：

1、For the first $$$\sqrt n$$$ vertices that will be black, all vertices' dis[u] will be updated for max $$$O(n)$$$ times，that's $$$O(n \sqrt n)$$$ ；

2、After that, each dis[u] will be less than $$$\sqrt n$$$. When we DFS the other vertices, each dis[u] will be updated for max $$$O(\sqrt n)$$$ times，that's $$$O(n \sqrt n)$$$ .

How are you calculating dis[u] and couldn't understand this statement " For each Ci,we DFS it while calculating the depth. When DFS v and dis[v] is less or equal to the depth, we break the chain". Could you explain it in detail

DFS from the vertice that be black just now, and update each dis[u] with dis[u] = min(dis[u],depth). When dis[u] is already no larger than your DFS depth, it's ok to return.

Sorry for my poor explanation, it's my first time to comment this at cf:)

Hey, how do you prove that the for later sqrt(n) queries they'll take at max sqrt(n) time? And what is the worst case tree for your solution?

Actually I also was thinking about this.

IMO, it's not necessary that for each dis[u] will be less than $$$\sqrt{n}$$$. However, $$$ans = \min_{u}{dis[u]}$$$ would be less than $$$\sqrt{n}$$$ within $$$O(\sqrt{n})$$$. After than, when doing DFS (or BFS), each node will be updated only up to $$$\min(ans, dis[u])$$$ number of times.

Why ans is less than $$$\sqrt{n}$$$ within $$$O(\sqrt{n})$$$ is where I am not exactly sure. This can be organized as the size of maximum subset of vertices such that the minimum distance between each pair of vertices is $$$\ge \sqrt{n}$$$. Just a heuristic explanation is that most of the vertices will be covering at least $$$\sqrt{n}$$$ vertices within $$$\sqrt{n}$$$ distance.

so the worst case would be a linked list with the first sqrt(n) queries on consecutive nodes from one end? Tbh this "all queries after first sqrt(n) queries will give an answer of <= sqrt(n) seems so intutive rn but IDK how to prove it mathematically.

After handling $$$k$$$ nodes the maximum distance must be at most $$$2n / k$$$. Consider a ball of radius $$$r$$$ around each of the black nodes. If some two of these balls intersect, the corresponding black vertices have distance at most two times the radius of the balls minus one, which is $$$2r - 1$$$. Otherwise, we have $$$k$$$ disjoint balls containing at least $$$r + 1$$$ vertices each, which is a contradiction for $$$r \geq n/k$$$.

Oops, i made a mistake:(. Not dis[u] is no larger than sqrt(n). Actually it's the update times of each node is O(sqrt(n)) for later queries. Thank you for making i realize it!

When will the rating get updated??

Looks like I overcomplicated D. Went for a divide and conquer instead of simple greedy because I couldn't convince myself that greedy works...

Can anybody explain problem E?

I will try to explain how I solved this question... As, a+b = a^b + 2(a&b) Hence, a+b = x + 2(a&b) => a&b = x/2 let's denote x/2 as y. Now, a^b = x and a&b = y let's take an example say, x = 10 => in binary, x = 1010 and y = 0101

Now the positions at which y is 1, both a and b will have 1 (a & b), and the positions at which x is 1 either of a or b will have 1, and other will have 0. Thus our answer will be a: 1111 & b: 0101. Of course, solution will not be possible when x and y both will have 1 at same position, We will handle this case separately. You can refer to my solution: https://codeforces.com/contest/1790/submission/190929183

Could anyone please explain the problem in this code? It is problem B of this contest. I cannot understand the explanation of the wrong test case Taisia and Dice

The value of the removed dice is 5 in that test case, it is stated that it is the maximum that is removed so you can't have a dice with value 6.

Got it. Thanks

In test 7 you are having a number on dice 6 while s-r = 5. And condition is that s-r is the largest number.

"Taisia's pet cat steals exactly one dice with

maximumvalue ai"Ok. Thanks

You have a die with 6 in test case 7, but the max allowed is s-r=20-15=5.

Ok.Thank you

So will this round be rated? >_<

I hope so.

Can anyone tell why I don't see my ratings for this round ? Am I not qualified for div 3?

They are yet to be updated.

When rating will appear?

i didn't understand #D can someone explain me please?

Consider sets of nesting dolls. They are segments consisting of consecutive numbers. Then there is the following solution: 1) sort the array 2) go through the elements in a row and see how many such elements there are. Let the elements x, the element itself, well, If the elements with a value of x — 1 are less, then we need to add to the answer the difference of these two numbers, because we need to create all sets of nesting dolls, in which the element x — 1 is not included in them. 3) output the answer This can be conveniently done using map (you can see my solution). P.S. I do not know English, so please forgive me typos or some grammatical errors.

thanks but i was expecting only question part

When will wait over ? UPD: wait over.