<copy-pasted-part>

Hello!

Codeforces Round #506 (Div. 3) will start at Aug/24/2018 17:50 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) 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 participants of the third division*, you must:

- take part in at least two 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 my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

**UPD1**:

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | problem_destroyer420 | 5 | 209 |

2 | syh0313 | 5 | 225 |

3 | VinceJudge0 | 5 | 230 |

4 | kredo | 5 | 234 |

5 | EctoPlasma | 5 | 241 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | halyavin | 506:-92 |

2 | antguz | 121:-20 |

3 | YangYunFei | 50:-11 |

4 | UselessChallenger | 41:-1 |

5 | zdw1999 | 41:-2 |

6 | applese | 40 |

1217 successful hacks and 926 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | i_f_y_m | 0:03 |

B | kredo | 0:03 |

C | kredo | 0:13 |

D | NT_Master | 0:17 |

E | syh0313 | 0:43 |

F | iamunstoppabIe | 0:19 |

**UPD2**: Editorial is published.

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

Yes,rated for participants with ratings up to 1600

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

I am div -1 ;)

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

its good but its bad

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 :(

WHY 15 MINUTES DELAY?

typedef Codeforces_Rounds 15_Mins_Delay

15 minutes delay -_-

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

Haha, LOL. Yep, just Codeforces thing :p

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)

Will participation cross 8500 :)

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

I find B easier than A so tried B, thought have a perfect solution but only getting wrong answer. Div 3 contests are always something special. Edit: Finally solved and that's first for me in a div 3 contest, even I'm kinda new here :P

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 don,t know why Mike trusts so much on Vovuh for div-3 he prepares really bad div 3 rounds

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.

What a foolish mistake. now i understand. It just need to compare a[i] and a[i+1]. Thanks!

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

My codeThanks 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.

Honestly, Its seems like Div-1 to me.

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(nlogn) with multiset 42096347Good 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? LinkYes, 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

For problem E:

We should start processing leafs and add to the result the number of their parents only if those parents distance from 1 is > 1 (level 2 or further)...

Remove current leafs, their parents and the adjacents to their parents from the graph..

Repeat the process on the new graph.

Is this approach correct ? What is a better one ?

Whats pretest 5 in A? Just can't figure it out :(

try this input:

6 2

ababab

output should be: abababab

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://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

I have also used the same approach: http://codeforces.com/contest/1029/submission/42130661 The function reqd() does the main job. But I'm getting wrong answer on test case 8.

The function prepareChild() turns our indirected tree to directed tree using BFS.

Can you tell what's wrong here?

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 ?

I tried to find maximum of left interval and minimum of right interval. Let max1=difference of 2. Then remove the row in which left array max is there and find max2. Then finally remove only the row in which right array min is there, max3. The answer is max(max1,max2,max3,0)

The intersection length of n segments is

minR-maxL(invalid if it's negative), so just ignore each segment and evaluate length, i used multiset to insert/remove inO(logn). I'm doing this for n segments, so the total complexity isO(nlogn).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

good contest.But I got ac to C after 10 minutes after the contest is finished

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.)

:) :) :)

I wish I could code this fast XD. Parallel Programming :P

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?

He might have a self created program which runs multiple codes at a same time or maybe downloads all the codes of the competitors . maybe , maybe not .

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.

It's just a cumulative sum problem!

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.

sighAh yes, unordered_map... Thanks! :DP/s: Still seeing that got TLE is insanely weird :-P

I think the issue is not in usage of

`map`

instead of`unordered_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

`map`

by the member function`count()`

, 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 :-PGuess 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://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 criteriona_{ij + 1}≤a_{ij}* 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 >(

In problem D, using unordered_map gives TLE while submission with map gets accepted. I can't figure out why.

http://codeforces.com/contest/1029/submission/42051858 (AC code)

http://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://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_factor`

of 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://codeforces.com/contest/1029/submission/42058174

Resubmitted exactly the same code and got AC (added 1 extra comment line). https://codeforces.com/contest/1029/submission/42078570

on test 28, time is 1871ms

TLE on test 39 https://codeforces.com/contest/1029/submission/42079643

same code AC https://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

ratingschange?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

a_{i}and assumea_{i}isldigits long. Thena_{i}gives a solution when there existsa_{j}in the array with the property 10^{l}×a_{j}+a_{i}. has a remainder 0 when divided byk. With a bunch of precomputing you can find how manya_{j}s have this property. However you have to be careful to remove the case wheni=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 bea+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 issuePeople 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 wellSo 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://codeforces.com/contest/1029/submission/42081763 TLE Solution : http://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 EDP state : (node, cur, par)node-> The index of the nodecur ( 0 or 1 )-> Whether the given node either has or is supplied with an extra edge connecting it to the rootpar ( 0 or 1 )-> Whether the parent of the given node either has or is supplied with an extra edge connecting it to the rootNow 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 =1Case 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://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://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://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

Sir , I think that you should change the limit exceed of Problem D, I got TLE on test31，but my algorithm is correct. Sorry for my poor english

Here is my code : (https://codeforces.com/contest/1029/submission/42053492)

Hope that the contest page doesn't show "starting in 15 minutes" after 3 minutes