Привет! В 27.01.2023 17:35 (Московское время) начнётся Codeforces Round 847 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin и Vladosiya. Также в этот раз одну из задач предложил molney.
Также большое спасибо: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 за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.
Всем удачи!
UPD: Разбор
Hoping for the first time getting AK (solve all problems) in this contest.
Hoping for 6-8 NP-hard and NP-complete problems :D
All the best !!
Congo
Congrats
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 ?
Наконец-то третий Див))) Мы ждали слишком долго...
div3 мусор
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.
If you make a mistake, then 10 penalties are added to your total penalty.
[ Deleted ]
no one can beat me!I am all thw ay down.
hoping to be Expert on this contest... Wish me Luck ... xD
Good Luck Buddy ..
What if I can't solve at least 3 problems?
There nothing wrong as long as you not give up trying.
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 definitely be 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 of active CF users being balanced.
Hey, bro, seems like you know everything about the rules, where did you get it?
Basic rules
Rating algorithm
Very nice new rules for Div3 contests
what do you mean by new rules ??
Should I give DIV 3 if my rating is 1400. Does div 2 has more chance to increase my rating than div 3
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 five rated 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.
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 ...
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 :)
Hoping to be specialist :) There are only 4 ratings to go Don't let me down pls :)
Please no NP-hard problems. Please no NP-hard problems. :D
Can't wait to see hmzqaq's performance in this round. (he is duck_pear)
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.
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)
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.
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!
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.
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?
there is a typo in problem E Vladosiya it should be XOR not OR pls update it
no
Finally I was able to use first 31 digits of pi from my template :D
first 30 digits were given in sample cases
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
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 ⊕
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.
Wow. People hate this comment so much :/
Did you hack your own solution PURPOSELY? What's the logic behind it?
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
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.
This problem 342E. Xenia and Tree is almost identical to today's problem F
F was the same as: https://codeforces.com/problemset/problem/342/E
speedforces
After contest, i m posting this..
a harder version of problem F https://codeforces.com/contest/342/problem/E
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.
Lol, first tournament I have answered something. :)
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 :)
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!
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.
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.
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 only i-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$$$.
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]=trueafterq.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
initfunction, 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
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!
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
I 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…
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?
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.
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
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
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!
So will this round be rated? >_<
I hope so.
When rating will appear?
When will wait over ? UPD: wait over.
System testing has been finished??
has not started yet
I am new here (kinda), I don't know why this contest shows up on my profile as unrated ?
All contests are unrated until the ratings are updated.
Publish the Editorial plz
Why is this round not rated for me? My rating is well below 1600. The final standings are out, yet i dont see any changes in my rating.
The system testing hasn't started yet. Just wait.
That's too slow. Why not start the system test?
I remember system testing used to be wayyyy faster. Now they delay it so much for each contest
That's true. I don't understand why system test has been delayed for so long either.
Hi! Can anyone explain what's wrong with this solution for D? I've got Time Limit on the Test 27.
Count a frequency of every doll's size (current size =
k). Iterate through doll's sizes and check there is doll with size less by 1 (k-1). If there is no, then it's start of new sequences. If it is, then we can use dolls with sizekin a new sequence only if frequency ofkis more then frequency ofk-1Hi! The code similar to yours in C++ also receives the verdict TL (on test 28) — 190976286. However, if you replace the unordered_map data structure with just a map, the solution gets OK — 190976343. This is due to the implementation of these classes "under the hood":
unordered_map is a hash table. The standard Python dictionary uses it. On average, the asymptotic behavior of each operation is O(1), but in the amortized worst case (when a hash collision occurs) this will be O(n). On large tests according to the paradox of birthdays collisions will occur quite often.
map is a red-black tree. Even in the worst case, the main operations are performed in O(logn). On average, it works slower than a hash table, however, due to not the best standard hash functions, I recommend using map.
So, you should implement the red-black tree yourself, or switch to C++ to explicitly choose which data structure to use.
why is this round unrated?
(a^b)+2*(a&b)=a+b Where did everyone get this formula from, how does it work out. Explain, thank you.
https://stackoverflow.com/questions/4068033/add-two-integers-using-only-bitwise-operators
Think about the sum of two numbers a and b, and let's focus more on the ith bit.
x[i] = 0 if the ith bit of the binary representation of x is 0 else x[i] = 1
if a[i] & b[i] = 0 then (a[i] + b[i]) = (a[i] ^ b[i])
else a[i] + b[i] = (a[i] ^ b[i]) + (1 << (i + 1)) because you should carry one extra bit to the right.
and (1 << (i + 1)) = 2 * (1 << i)
so a[i] + b[i] = (a[i] ^ b[i]) + 2*(a[i] & b[i])
it's just addition of bits that is only one of numbers and those that are in two of them
When will the ratings update
Why the rating isn't update yet?
thanks!
The rating is usually updated a little longer after the educational rounds. You should get used to it.
SpeedForces during contests, SlowForces during rating updates.
Finally, the system testing has started! @_@
Too bad it will be finished only in 4 hours
Is this contest unrated as the ratings have not been updated yet?
it's rated. Mike's removing cheaters
Has the official rating been published? My rating didn't change..So, I don't know if I have improved or not...
The official rating hasn't been published yet. If you want to predict your rating delta you can use cf predictor
How my code is giving Time Limit Exceeded?? Can anyone explain alwyn csegura Darko Submission->190829557
include <bits/stdc++.h>
using namespace std;
define ll long long
int main() { int t; cin >> t; while (t--) { int n; cin >> n; int a[n + 1]; ll int ans = 0; unordered_map<int, int> m; vector v; a[0] = -1; for (int i = 1; i <= n; i++) { cin >> a[i]; // cout<<a[i]; if (m[a[i]] == 0) { v.push_back(a[i]); } m[a[i]]++; } sort(v.begin(), v.end()); int smallest = v[0]; for (int i = 0; i < v.size(); i++) { if (i == 0) { ans += m[v[i]]; smallest = v[i]; continue; } if (v[i] == smallest + 1) { // cout<<smallest+1<<endl; if (m[v[i]] == m[smallest]) { smallest = v[i]; } else { if (m[v[i]] > m[smallest]) { int mini = min(m[smallest], m[v[i]]); ans += max(m[smallest], m[v[i]]) — mini; }
smallest = v[i]; } } else { ans += m[v[i]]; smallest = v[i]; } } cout << ans << endl; }}
Probably because of collisions in unordered_map<>. Try doing the same thing with map<> or use custom hash with unordered_map<>
But it is not my fault!!
It actually is. You chose to use unordered_map instead of map, while it's well known that unordered_map might cause collisions, resulting in O(1) average, but O(n) worst.
I don't think so, It's my problem,It is default Things,This type of solutions must be Accepted.
It's not about solutions. It's like unordered_map being slow, therefore not passing time limit. Solving those problems isn't the hard part of them. Solving them EFFICIENTLY is. Therefore, you are required to solve them efficiently, or forced, I should say.
Yeah, it's definitely sad to fail your solution in that way, but it's a good 'lesson' which you will know the next time you encounter it. That's why we do CP, to learn.
when the new ratings will happen
Is there an error in the system testing? My solution was accepted during contest (accidentally submitted in python instead of pypy), yet TLE in the system testing. Test case 26 on 200,000 length array runs in 300ms, but then saying same length array runs over 2000ms for test case 27? Unable to replicate an inflation factor of 6x on my local computer with big numbers.
https://codeforces.com/contest/1790/submission/190800700
Same Accepted during contest but TLE now,wtf is happening
Your solution is wrong, that's what's happening
2 words: hash collision
dict query worst case time complexity can be O(N)
https://codeforces.com/blog/entry/111872?#comment-997343 same with your structure
Attention!
Your solution 190852686 for the problem 1790F significantly coincides with solutions PassionFruitEnjoyer/190852686, Gurudev_Dutt/190863308, HieuNekodesu/190864005, HieuNekodesus/190874217. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Clearly we all used prewritten Centroid Decomposition code taken from https://robert1003.github.io/2020/01/16/centroid-decomposition.html and we were flagged incorrectly.
MikeMirzayanov
Firstly, the message to you contains precise instructions on where to write about such issues. Why are you breaking it?
Secondly, can you clarify any reason why the main parts (not CD code) in all solutions are the same?
The above is the basic part to get the input, so it is difficult to avoid it being the same.
And the last part is because the topic says, I just do it.
** Change the color of a vertex and get the minimum distance from that vertex to one of the given vertices (must calculate the distance first because if we change the color first, it will be wrong)
First of all, I apologize for my bad English. Then after completing the Codeforces Round #847 (Div. 3) contest, I received the following message:
I used the Centroid Decomposition code from this blog — a well known algorithm website in my country, and this blog, so I have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition.
First of all, I apologize for my bad English. Then after completing the Codeforces Round #847 (Div. 3) contest, I received the following message:
I used the Centroid Decomposition code from this blog — a well known algorithm website in my country, and this blog.
About main function part is similar:
The above is the basic part to get the input, so it is difficult to avoid it being the same.
And the last part is because the topic says, I just do it. "Change the color of a vertex and get the minimum distance from that vertex to one of the given vertices" (must calculate the distance first because if we change the color first, it will be wrong)
MikeMirzayanov can you answer my comment?
When will the ratings be updated?
is this rated? cuz i did not see any change in mine.. also how to solve the D problem can someone explain.. i am new to CP
Here's a tutorial for this contest https://codeforces.com/blog/entry/111948 They are always published after the end of the contest and you can aslo find a link to it in this article.
Bruh in D i used unordered map during the contest and it gave TLE after the contest on test 28 but when I changed unordered map to map it gave passed all test cases!!
that's something you should have known. unordered_map is always be hacked.
has the round been declared as unrated??
this was the first time I turned green :(
but am back to newbie now
There is a small chance that contest became unrated due to E problem.
How come the tutorial solution for problem F gives TLE ? https://codeforces.com/contest/1790/submission/194017127