<copy-pasted-part>
Привет! В Aug/24/2018 17:50 (Moscow time) начнётся Codeforces Round 506 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</copy-pasted-part>
UPD1:
Поздравляем победителей:
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | problem_destroyer420 | 5 | 209 |
| 2 | syh0313 | 5 | 225 |
| 3 | VinceJudge0 | 5 | 230 |
| 4 | SaIah | 5 | 234 |
| 5 | EctoPlasma | 5 | 241 |
Поздравляем лучших взломщиков:
| Rank | Competitor | Hack Count |
|---|---|---|
| 1 | halyavin | 506:-92 |
| 2 | antguz | 121:-20 |
| 3 | Anguei | 50:-11 |
| 4 | taran_1407 | 41:-1 |
| 5 | zdw1999 | 41:-2 |
| 6 | applese | 40 |
Всего было сделано 1217 успешных взломов и 926 неудачных взломов!
И. наконец, люди, отправившие первое полное решение по задаче:
| Problem | Competitor | Penalty |
|---|---|---|
| A | i_f_y_m | 0:03 |
| B | SaIah | 0:03 |
| C | SaIah | 0:13 |
| D | _kawaii_neko_ | 0:17 |
| E | syh0313 | 0:43 |
| F | iamunstoppabIe | 0:19 |
UPD2: Разбор опубликован.
just have strong pretests because then only hacks make sense
Will be original cf round on September 1st?
How are you going to detect the people who hack solutions having some if statement to remove them from standings table? Is there some algorithm?
I'll try to check all peoples, who will hack their own submissions, manually and check if in their code will appear parts like
if (n == 1234) return 1;and similar.Why is it even allowed for people to hack their own submissions?
Not all hacks of their own code are such as I say above. Many hacks of your code can be useful because there are can be not complete testsets in the contest. But hacks of kind
if (n == "blablabla") return 1;are useless and make no sense.Few contests back, there was a comment mentioning a person hacking someone else in the same room but both the accounts probably were being used by the same person. This way it won't show up in the list of people who hack themselves but this practice needs to be curbed.
We are trying to undermine all such cases but it is very hard to do that without any mistakes or omissions.
Ah, so you build a tricky/big case and let codeforces check the correct answer for you. Never thought about it, makes sense!
People do like this mostly for dropping their ratings purposely. That is repulsive addiction。
Successful Hacking Attempt …
move contest time 3 hours later .. this time is not good
Why did you change your profile picture?
Well Well Well
Is it communist?
Warning, this is a joke, don't feel bad if you are div 3.
yeah didn't even felt the joke.
yeah, it seems is not funny, I just wanted to hide in a subtle way a sad truth
don't underestimate anyone,who knows an extremely low rated div.3 guy is doing some other wonders.
Too real
DIV3 ROUND! It's time to challenge your coding skill together with coding speed!
coming expert , i wish .
Welcome to future,your rank in 504 will be 2942.
Ya, they have beaten me up
Same here
Hope there will be strong pretest. Don't want the codeforces changes to the hackforces. Thank you very much.
Hope that I will become expert after this contest. :)
gl hf
Why the 15 minute delay ?
standartno
So that no of registrations crosses 9k mark...
For few seconds, the website crashed as well. Maybe the delay was to fix the issue
Delay :(
+15 минут? Серьёзно?
Я даже страницу обновил за две минуты до начала, и переноса ещё не было! БЕСИТ!
The Wait!!!
00:00:15 -> F5 -> 00:15:00
Someone please make a Codeforces Delay Predictor -_-
how to solve A?
To solve A: 1. Wait for 15 minutes. -_- 2. Open contest page. 3. See question A. 4. Solve.
Nice
Yeah, it works, 10q
http://lmgtfy.com/?q=codeforces+how+to+solve+problem+A+in+contest, Here you go.
are you genius evil hacker?
Before:00:00:15 before start, Now:00:08:00 before start, Will-be:This round will be unrated :)(JUST JOKING)
Hackforces, Delayforces, Memeforces, Mathforces, who's next??
Unratedforces
dragonforces
Wrongproblemorderforces
Is it Div 3 contest? I think it's too difficult
<copy-pasted-part>
<copy-pasted-part>
.......ANNOUNCE.....
</copy-pasted-part>
</copy-pasted-part>
You may do in such way, we'll understand
I am getting wrong answer on test 1 problem A and can't even figure out why. :'( edit: figured
How to solve problem D ?
I didn't actually give it a go, but I believe you should calculate ((V[i] * 10 ^ j) % K) for every i and j and then, for each j, build a frequency array / map of these such values. After that, it's easy to see that for every V[i] the amount of elements you can pair it up with is freq[j][K — (v[i] % K)].
42061028
It was hacked. You should let your code run faster. 42080262
This too!
this is not div.3 contest
i hate vovuh
This is sad :(
Although I found the problems harder than the last div3 contest, I still enjoyed it! At the end of the day, I'm sure I'll come out of this round knowing more than I did before(once the editorials are out of course xD)
So a relatively difficult div 3 contest(compared to past div 3 contests) isn't necessarily a bad thing :)
Vovuh why not increase the time limit to 2.5 hours because i think most probably div3 contests have a large fraction of people who always thinks that if i could have given 15 more minutes i could have definitely done one more problem(i m one of them).. i mean this just boosts up the confidence and belief.. this suggestion may be immature but i feels at least 2.5 hours should be given for 6 problems to do justice with the contest,those who solves first will have better rank whether the time is 2 hours or 3 hours.. although these contests are awesome always if one try to solve problems before or after contests .
I try to solve Problem B with a solution of upper_bound(a[i]*2) but fails. How to solve this?
You miss read the statement.
I solved it with sliding window
Even I tried the same but got wrong i case 4
Could not find what is missing. Please help. Thanks
Thanks got it,I misunderstood the problem
I think the time complexity of your code is not right. You can use double-end queue (deque). Like this. 42036114
In problem F, what does this mean : "all tiles of at least one color would also form a rectangle." ?
At least one color must form a rectangle i.e if you remove red, blue must form a rectangle or if you remove blue, red must form a rectangle
Thank you.
I also was not able to understand the problem statement because of this. According to Firastic, the intended meaning is quite different to what they wrote.
What is pretest 4 for B?
A pretest of this type: your solution should be based on the statement and not the samples.
Got it, but that was still a shitty statement. Could be framed better.
Welcome to Codeforces Round #506(Div.2)
Edit: only A isnt a Div.3 A problem.. B is easy but the trap in reading the statement is just so unexpected
other problems are Div.3 problems
pretest 6 in A. I want to know that sh*t and yea, i still hate vovuh and his friends who always writes shity contests. (I'm not afraid downvotes)
try this input:
6 2
ababab
output should be: abababab
ohhhhh, got it, by the way thanks
Why do his contests then?
How to handle the case in D when 2 | k or 5 | k. Is there an easy way to do this than to calculate modulus for all possible factors of k which still aren't coprime to 2 or 5
Your approach seems not to be on the correct path. You may want to think it differently.
What's pretest 7 on C? I can't figure out where I screwed up.
My guess is that it is something like this:
There should not be hard deadline time to end the contest, atleast 20-30 seconds extra should be given, given the initial load on the system. I missed the D by 1 second today.
Same here, I putted the code and clicked submit and there was almost 10 seconds, but it wasn't submitted :(.
Then that hard deadline should have a hard deadline. xD
Yeah, no.
What the wrong answer test 17 in the problem D ?
Try this input:
2 1000000000 1000000000 1000000000
I solved C with Segment Tree, is there other topics solve this problem? because I feel that it is easier than SegTree when I saw someone solved it quickly.
only the top 2 numbers matter.
Thanks, I will see your submission for more details.
Initial idea is that if you consider all the segments, the intersection is formed by lowest right end and highest left end.
Now, if you want to improve your intersection, you would want to either:
Now think about which one would you choose.
Yeah I got it now, thank you very much :D
Easy O(n log n) with multiset 42096347
Good idea :D, thanks for sharing it!
can someone plz tell me what is wrong in this approach for E? A node ( > depth 2) may be reached through child or parent who has a direct edge or there is a direct edge to this. SO, a) if i want to reach this node from parent, then for each child there must be a direct edge or any of their children must have a direct edge. b) if i want to reach this node from children, any one can have a direct edge and others can have direct edge or their children can have a direct edge.
c) if i have a direct edge to this node, then i can take the min( a, b, c);
Can someone plz tell me what is wrong here, here is the link, https://ide.geeksforgeeks.org/Nn0MdojmeD
Will an O(10 * n * logn) solution pass systests for problem D? Link
Yes, it will. Mine did.
42061028 will this pass
I don't understand but it already says Accepted.
edit: oh you are worried about hacking phase, it wont exceed time limit, that case is already there.
hmmm.what's that case well
Can someone tell me about solution for problem E ?
DP d(i, j): i represent the index of the nodes, j represent the depth of node i; http://mirror.codeforces.com/contest/1029/submission/42054107
The complexity is O(n)
Root the tree at 1. Sort the nodes by their depth in descending order (so we start with leaves). Make an array to store if we can reach a node in <= 2 steps. Loop through the nodes by depth and if not marked create a connection to the parent of that node and mark all the neighbors of the parent in the array.
I was trying it with dp, though couldn't complete the code within contest. My idea was to consider states if there is an edge from 1 to v or not. if there is an edge from 1 to v, then there can be edge from 1 to childrens of v or not. if there is no edge from 1 to v, then there must be an edge from 1 to atleast one of child of v
Seems like problemsetters have been missing how problem A should be :D for the last few contests.
Am I the only one who misread the problem statement of B? I guess no.
problem F, finished in 10 mins after contest :((
during the contest I coded it in 8 minutes but I got WA37 did you get the problem in this test?
the same problem, in the last 5 minutes of the contest, I knew my mistake but i did not have enough time to code :|
How to Solve C ?
The intersection length of n segments is min R - max L (invalid if it's negative), so just ignore each segment and evaluate length, i used multiset to insert/remove in O(log n). I'm doing this for n segments, so the total complexity is O(n log n).
Code: 42096347
what's wrong with 37'th in problem F ?
Small infinity(got wa on 37 too).
2 large prime numbers, so only rectangle with side 2 will pass
sorry can you explain more?
the area (a + b) can only be divided by 2, some people have the answer 6179835302 because they devide it by 64728, but we can't color the rectangle like this because " all tiles of at least one color would also form a rectangle ". The solution is check that are there any divisor of a (or b) (called i) that i <= (divisor of S (called div)) and a/i <= (S / div) so we can have a rectangle with size div * (S / div).
my code : https://ideone.com/3bFclD
Nice contest : )
for me the statement on b,c are very confused after explanation b become clear and I'm solve it, c after contest solve it its easy but not clear with this statements.
Is it possible to share ideas of hacks with other people before the end of the hack phase? Does it violate the rules?
Honestly, when I saw problem A, I thought for a second if it is really Div 3 (and I haven't passed A). It was quite good, except they were a bit too hard for newbies (like me), and frankly some problems were more suitable for Div 2, or even Div 1 instead. Still, I appreciate the hard work of today's contributors for thinking up the problems!
is it a rated contest or not ? also i can't understand the General announcement, which say (We will publish separate standings for trusted participants after the contest.)
:) :) :)
vovuh, MikeMirzayanov.
Why his submissions are not showing after testing?
seems like another halyavin day , nearly 450 hacks . wow again .
I can't comprehend how do you even hack. There are too many solutions and most of them are fully correct.
Can somebody explain, please?
It seems he is the one brought done the submissions of D for ~640 to ~150
lol，halyavin is really good at hacking，I have been hacked by him for many times. But I maintain it also help me develop my skills，because the probability I will be hacked decreased more now at least.
can you please explain your code for E?
Firstly, we get a tree rooted by 1. We get dep[i] to express the depth of i in the initial tree, and let's call a vertex is right if the distance to 1 equal or less than 2. Obviously, if a vertex i with dep[i] <= 2, then the vertex is right. Our goal is to make all the vertex right. Consider we link 1 and a vertex i, it makes all the vertexs which are adjcent to i right. So in my solution, we first sort all the vertex in the decreasing order of dep[], and consider them one by one. If we find a vertex i is not right yet, then we link 1 and fa[i], which fa[i] is the father of i in the initial tree, and it will make all the vertexs which are adjacent to fa[i] right. It can be proof that in this way we use the least steps. XD
why do we choose the vertex with largest depth first?
Because we have to deal with it, if we don't solve it this time, we must solve it next time. And solve it from down to up do not influent others, because all the vertex in this subtree are right.
thanks a lot!
Can I have the original picture plz?
Did anyone solve B using dp and implicit segment tree? I guess it's an overkill, but to me it seemed better than to guess that the solution is always a continuous segment.
I guess that this solution would be the best if the sequence was not in increasing order.
You can try to prove it during the contest. Just imagine you have already some subset, with the last element at index i (the array is sorted, and all of the elements with indexes > i are bigger). Now you want to try to add another element to this subset, suppose you added element j (j > i+1). Now you can see, that if element a_[j] <= a_[i]*2, the same applies to other elements in an interval [i+1, j-1] and it's always worth it to take smaller element. But why? Consider x as the smallest integer in the subset we consider at the moment. It's easy to see we want to minimize the largest integer in our subset (lets name it y), so 2*x >= y. This strategy applies to every element we consider in our subset — concluding — our subset will always be contiguous (if the array is sorted). Please correct me if I made some logical mistakes.
in problem B 2 1 2
how is the answer 2 ?
i knew that the statement contained <= but i thought that it is <
how isn't there any pretest to check this ?
Just curious, how could someone (or to be precise, antguz) confidently hack my O(10 * n * log(n)) solution of problem D to successfully give a TLE verdict?
My hacked solution: 42049909
My re-submitted one (with some slight optimizations, still TLE on other similar tests, which gave the conclusion that my solution ran at somewhere around 2.5-3s): 42071241
I had the very same issue as you so I thought of helping. TLE will go if you use unordered_map. Link to your submitted solution.
sigh Ah yes, unordered_map... Thanks! :D
P/s: Still seeing that got TLE is insanely weird :-P
I think the issue is not in usage of
mapinstead ofunordered_map, but it is in that you used the operator[]when you wanted to add values to the result.Instead, you should check if a key you want to add its value was already existed in the
mapby the member functioncount(), and if yes, then add the value of that key to the result.Because when you use
[], if the key in[]is not existed yet, this operator will create it, so the size of the map will increase by one, and so on. So, the time needed to access the map will also increase with the increasing of its size, thus you will get TLE.Check my submission for more details.
Well, just as I was discussing with one of my friends about this exact issue.
Yeah, I was critically careless in that, thinking O(10 * N * log(10 * N)) will do no harm. I was stupid :-P
Guess this should be a huge lesson for me from now on. Thanks! :D
Thank you very much!
Can anyone please point out why my code is giving TLE for problem D? I have tried all the optimisations I could think of at my level. It would be really helpful if someone can help me out here. Thanks in advance !!
use unordered_map
Thanks a lot. It worked
http://mirror.codeforces.com/blog/entry/61399?#comment-453807 . Hopefully this comment of mine helps you to get an AC by using map only.
Are there any better solution in problem B? I use dp and RMQ to solve this problem, but I think it's too complex for the problem B in div 3 contest :((
I use F[] with the meaning that F[i] is the answer ending at i. I use lower_bound to find the minimum value that more or equal A[i] / 2 (called j), than find the maximum value of F from j to i — 1.
P/s : If the array isn't in increasing order, what should we do?
Edit: If the problem like this : find the maximum length of a subsequence ( by delete some elements ) (like LIS) but a[i] <= a[i-1] * 2 in this subsequen. what will we do?
eg:
Input n = 3 array[] = {2, 1, 4}
Output 2 ( 1 and 4 )
You can traverse greedily in O(n): find the longest increasing subset that the criterion aij + 1 ≤ aij * 2 holds true.
So, of course, if the array isn't sorted yet, we can just sort it beforehand — nothing special.
Thank you.
If the problem like this : find the maximum length of a subsequence ( by delete some elements ) (like LIS) but a[i] <= a[i-1] * 2 in this subsequen. what will we do?
eg:
Input n = 3 array[] = {2, 1, 4}
Output 2 ( 1 and 4 )
Excluding the last element (i.e., the biggest), you can just calculate the length of the largest interval I = [L,R) such that I[R-1] <= 2 * I[R-2] holds.
So L starts at 0, R at L+1, keep increasing R until the property I[R] <= 2 * I[R-1] is false. Then reset L = R, and repeat the process until R >= N. After doing that, the answer is the max R-L difference you've found in this process. There is one corner case: N = 1.
Thank you.
Freakin' A Again >(
Мне кажется, для задачи D ограничение по времени стоило бы немного увеличить, потому что те люди, которые решали эту задачу за O(10 * n * logn) получили взломы в виде ограничения по времени. Несправедливо, ибо это же не лобовое решение, и оно, как мне кажется, имеет место быть в ряду АС.
In problem D, using unordered_map gives TLE while submission with map gets accepted. I can't figure out why.
http://mirror.codeforces.com/contest/1029/submission/42051858 (AC code)
http://mirror.codeforces.com/contest/1029/submission/42063201 (same code with unoedered map)
Some special data can make the complexity of unordered_map become O(n).(like test 64. I used pb_ds and got accepted after the contest. :P
knew this thing but ignored it don't know why -_-
42061028 this got hacked(map) -> tle verdict on hacking 42073938 this got tle at test 66 unoredered map
any reasons?
Unordered_map is implemented using hash table. So due to collisions in the worst case it can be O(n) for accessing an element. But map guarantees O(logn) for access.
CodeForces is the worst. Solution 1 Solution 2 Both solutions are the same. So during system testing, my correct solution fails only because of the load on CF server, which is basically CF's fault. So now I've to pay for it to settle for a worse rank.
And I know even tagging MikeMirzayanov won't do anything because these kinds of crap has happened before and nothing was done.
Your solution was already borderline. Also, time is actually calculated by the no of clock cycles your solution takes to finish execution, and not wall time, so I don't think it has anything to do with server load. +-100ms in similar code execution can be expected
Yes I know it was borderline. It had passed test 7 in 2.8 s during the contest. But I think it's the server load only because I've read more such cases in a few contests held earlier and my solution to D also took more time to execute than it took during the contest.
In general I have observed that borderline solutions fail only during system testing leading me to believe that load during system testing is the only reason, because otherwise they still pass.
When will ratings get updated?
Finally Blue Yaaay!!!!!!
I don't know why this submission for problem C 42040684 got hacked and then I again made the submission 42076792 with the same code and it passes all the tests, this seems to be a serious issue, as its the fault of the system which gives different execution time for the same solutions and unexpected time penalties. I think the hacked test case is the last one #71 ..Plz have a look at it.....
Was the time limit too strict for problem D?
42055423 Uses unordered_map and gets a TLE; 42076582 Uses cc_hash_table and gets an AC.
Time complexity of both solutions is O(11*N).
but both of them is log(n) data structure. So the Time complexity is O(11*N*log(N)).
The unordered_map runs very very slowly.
maybe there are better solutions...
Asymptotically the solution should get an AC, but as noble_ said unordered_map is very slow.
https://mirror.codeforces.com/blog/entry/50626 I found this quite useful.
after testing, I found that map<int,int> or unordered_map<int,int> will both get an ac, and unordered_map is slightly faster ..
using long long in map will be slower
tweaking
load_factorof your hash table gets AC in 1044ms (42080080).Worst case time complexity of unordered_map is O(n).
AC with unordered_map ~997ms
Problem D makes me very sad.
I write a O(n * logn * 11) then get a TLE on test 28.
I make some optimization to O(n * logn * 10) then AC.
I got TLE on test 28 during the contest https://mirror.codeforces.com/contest/1029/submission/42058174
Resubmitted exactly the same code and got AC (added 1 extra comment line). https://mirror.codeforces.com/contest/1029/submission/42078570
on test 28, time is 1871ms
TLE on test 39 https://mirror.codeforces.com/contest/1029/submission/42079643
same code AC https://mirror.codeforces.com/contest/1029/submission/42079619 time 1653 ms on test 39
Can someone explain why there are such big time differences?
If you check for C[j].count(needed) before taking its value, it gets AC in 350 ms. Even if it's zero, it creates the node for it in rb-tree anyway, thus increasing both memory usage and time.
When will ratings change?
How to solve problem D?
when will the editorials be out??
The same code for Problem D running on G++11 gives TLE on test 50, and with G++14 gets Accepted. I don't think such stiff time limits give fair assessment.
How to solve D? just an idea will be helpful
Assume you are at a point ai and assume ai is l digits long. Then ai gives a solution when there exists aj in the array with the property 10l × aj + ai. has a remainder 0 when divided by k. With a bunch of precomputing you can find how many ajs have this property. However you have to be careful to remove the case when i = j. Also for the precomputing using 10 maps or unordered_maps for each of the powers of 10 you need seems to lead to TLE. You can avoid this issue by instead sorting and using a binary search.
got it, thanks for the idea
UPD: Sorry I got it, the answer of my idea is 2 + 2 * (a + b). So, never mind.
In F, is there any statement in the statement denys us from coloring the tiles as a rectangle with dimensions (1 * (a + b)), so the answer will be a + b + 2?
Because in the given samples (and all testcases I guess), the answer with my idea is always less than or equal to the answer from these samples.
For Problem D — TLE issue
People here find the Time limit strict ( even I did ) , but actually it isn't that strict. The only issue while using map which almost everyone is facing is :
If u simply do ans += mark[digits][requiredmod]; then even though that required mod doesn't exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1), and if you do this n*10 times the size of the map would increase and therefore the time to search as well
So what u need to do is first search whether that element is present in the map and then add it to the answer, as shown below :
if ( mark[digits].find(requiredmod)!=mark[digits].end() ) ans += mark[digits][requiredmod];
This is the only difference in my accepted and TLE solution.
Accepted Solution : http://mirror.codeforces.com/contest/1029/submission/42081763 TLE Solution : http://mirror.codeforces.com/contest/1029/submission/42082128
"then even though that required mod doesn't exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1)". It is your assumption or document that says so ?
No it is not my assumption. Very simply, you can compare the memory of both of my solutions. Why open the documentation when you can code... LOL.
Output :
1
2
Thank you, that's interesting !
Definitely not assumption
Tried everything and still got TLE on different tests. After that, I read your comment, changed that line, and got AC with 342 ms. Incredible :P
Great ;p
It is true, whenever you wanna create a new element x in a map you can just do
M[x];
This is the same case, doing
ans += M[ x ][ y ];
Will always create a new element [x][y] if it didn't exist.
For me, changing unordered_map to map helped me solve the TLE issue.
DP Solution for Problem E
DP state : (node, cur, par)
node -> The index of the node
cur ( 0 or 1 ) -> Whether the given node either has or is supplied with an extra edge connecting it to the root
par ( 0 or 1 ) -> Whether the parent of the given node either has or is supplied with an extra edge connecting it to the root
Now 3 cases arise :
cur:1 -> sum over all children {min(solve(child,1,1) + 1, solve(child,0,1))}
cur:0 par:1 -> In this case the current node has a path of length 2 to the root by going to its parent and then from parent to the root. sum over all children {min(solve(child,1,0) + 1, solve(child,0,0))}
cur:0 par:0 -> This is the most important case. Main Point : This node doesn't have a path of length atmost 2 to the root, so it has to make use of ATLEAST 1 of its children*
Case 1: Leaf node -> You need to make an edge straight from here to the root. ans =1
Case 2: Internal node -> Select atleast one child from which you will make a direct edge to the root. Code for this :
can u help me with this i am not understanding why this approach will fail dp[i][0]- best ans of subtree rooted at i such that i don't have direct edge to 1 dp[i][1]- best ans of subtree rooted at i such that i have direct edge to 1 ans is sum of min(dp[j][0],dp[j][1]) j is child of 1 https://mirror.codeforces.com/contest/1029/submission/42097382
For E does greedy approach like this work? Take any leave. If its distance to root in the input tree is <=2 we are done for this leave. Else connect parent of this leave with the root and delete this parrent and all his sons and his father from the tree.
yes it works, but you have to sort by dist first, check this
U mean depth? That is obvious we need to take the deepest leave always.
Could you please publish a tutorial for the contest !
Can I get a tutorial for this contest?
Could you please publish the results, the best hackers and the tutorial?
And we know, the best hacker is halyavin as usual.
It's sad having problem E with all tests except samples n = 200000. Have WA8 and don't know how to debug)
Why don't you attach your code? I think you were wrong while not interested if addition edge from 1 -> v then we could go from 1 -> v -> parent (v).
You're absolutely right. It's just about "aaarrrgghhh why I can't just copy failed test?"
I think the ranklist has something wrong.
Such as the participants VinceJudge0's solution for D was failed during the system test, but the ranklist shows that he/she solved 6 problems. Is this a bug?
vovuh Please check it. :D
Hope I fixed it now, sorry, there is a problem with Codeforces API, I don't know where is the bug. Thank you for your comment!
I agree.
I disagree.
I agree.
I disagree.
Are you playing inclusion–exclusion principle？
I agree too.
42038360 He use “for(int i=1;i<=floor(sqrt(a)+0.5);i++)” .He got TLE on my computer because calculate sqrt() many times is much slower than calculate it at first. But codeforces maybe use -O2 -O3 or something and he Accepted. :(
Can someone tell me why I'm getting TLE in D? my submission
I read all the comments but can't figure it out.. :(
Honestly i don't know, i tried playing with your code for a bit but i still got TLE. If it helps, my TLE on-contest submission used about 80k memory, and then it went down to about 10k with the Map.count(). Yours is still ~80k for some reason
Thanks. I think my code structure is the problem. Compare to editorial and accepted codes, I insert ten times more nodes.
That might slow down map operations and maybe larger memory consumption itself can be a problem.
If it helps you, i've solved it quite fast by using a single map:
https://mirror.codeforces.com/contest/1029/submission/42099251
But i'm pretty sure you should be able to solve it using a map for every amount of digits (in fact, it should be even faster).
Why does this TLE?
Can't find the reason.....
The time complexity should be O(n*log(10n)) (Correct me if I'm wrong) http://mirror.codeforces.com/contest/1029/submission/42107686
std::map is not O(1),and log10(n)=log2(n)*log10(2) so your code is O(nlog^2(n))
OH!
Thanks
you should probably change the time limit of Problem D.
Here is my code : (https://mirror.codeforces.com/contest/1029/submission/42053492)
Hope that the contest page doesn't show "starting in 15 minutes" after 3 minutes