Hello!

Codeforces Round #490 (Div. 3) will start on June 21 (Thursday) at 14:35 (UTC). You will be offered 6 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 problems and 2 hours to solve them.

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 Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

**UPD**: Also great thanks to step_by_step, kevinsogo and nhho for help in round preparation and testing the round.

**UPD2**: The results table!

Congratulations to the winners:

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

1 | EricHuang2003 | 6 | 150 |

2 | JerryKFC | 6 | 151 |

3 | Lovely_qgq | 6 | 170 |

4 | Meroeht | 6 | 181 |

5 | MYTH_vs_REALiTY | 6 | 209 |

Congratulations to the best hackers:

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

1 | djm03178 | 30:-2 |

2 | 2014CAIS01 | 13:-3 |

3 | quailty | 5:-2 |

4 | Harmonium_Wale | 4:-2 |

5 | kimden | 2 |

110 successful hacks and 226 unsuccessful hacks were made in total!

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

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

A | jh05013 | 0:01 |

B | JerryKFC | 0:02 |

C | abrunoaa | 0:03 |

D | T______________T | 0:21 |

E | NamikazeBoruto | 0:11 |

F | Counting_Stars | 0:20 |

**UPD3**: Editorial

Thanks for conducting another div3 round!! Looking forward for participation :)

I love it when people downvote comments for no apparent reason. The community of codeforces is great :)

You know sometimes I downvote some users comments even before reading the comment, I just cant stand those users :3

yep,but i downvoted u for a reason (your sarcasm):|

Why it's not in the homepage?

Now it is :) Sorry for delay

Can't be there some provision that people with rating(1600-1899 or maybe some lower) can also participate in div3(rated for them too) rounds with a totally different rank list i.e no cushioning for them and ensuring that ratings don't cross past 1899.

And as stated during announcement of div3 rounds problems will be easy for participants in the range 1600-1899,so it will be matter of just time.

OR

Maintaining a different rating graph can also be a way.

I don't understand what the point of something like this would be. Maintaining two different rating graphs would be an enormous pain with very little payoff imo. If you really want to see how fast you can do it, just participate unofficially, it's not a big deal. Div 2 contestants get enough rated contests as it is.

Please if possible add some critical case during contest time in preliminary test. If someone didn't hack my solution and I got wa from final test that's the most sad moment. Again thanks for arrageing this time of contest like div3. It is very good for beginner.

i do not like ACM_STYLE

The high penalty always result in my larger rank!!

I have doubt on using 20-min WA penalty for all ACM-ICPC style contests. Usually, the contests on Codeforces are length of around 2 hours and have 5-7 problems. But in ACM-ICPC contests, there are usually much more problems (10+) and they have long contest time (3+ hours).

Taking this mathmetically, let's say if a contestant A needs 5 more minutes than B to solve each problem. If they solve only 5 problems, A will get 75 more penalty than B, because every time you spent on the previous problems will affect the later solved problems' penalty. But when there are 10 problems, it becomes 275. In other words, it's

proportional to the squareof the number of problems. On the other hand, the penalty from the WAs would only increaselinearly, as each wrong submissions have fixed penalty.I'm not the only one thinking this way as I saw similar opinions on previous Div. 3 or Educational rounds too. I'm much like for having just 10-minute WA penalty for 2-hour contests, especially in a Div. 3 round, considering the accuracy of the official contestants would be quite low. How do you think about it?

True

Strongly agree. It is really painful when get so many WAs in an educational round. Your rank will drop significantly. Codeforces can't just use ACM-ICPC rules without changing them according to their contests.

MikeMirzayanov, you might wanna check this comment and tell us what you think about it :)

It is good idea and likely we will adjust constant +20 soon.

Ya even codechef changed their cook off penalty to 10 min for same reason.

I smelled FST :(

What is FST?

Failed System Test

I like the term Hacked other than Failed System Test

2 hours to solve, 12 hours to hack... That's why I love CF... And then you get a "time limit" on the main test... :|

Looking for more frequent div3 contests such that beginners like me can learn! :) Best of luck everyone.

Rated or not? Maybe a silly question for others:(

Rated for those who have rating <1600

(Abbreviation of Is It Rated? :P)IIR?Rated for people having rating<1600

Thx :)

It may also be an Abbreviation of Islamic Iran Republic, which is kind of my Specialization :D :D

(worries might clash with Argentina's match)PS- Thanks for not clashing it with Argentina Vs Croatia match.Thanks for the downvotes. Will try to

improvemyself.vamos Argentina

Hmm...

And what a game!

Sad time for those with Messi profile pictures :(

A contest right after the senior high school entrance examination in China. Hope I will win the scores I lost these two days back as ratings.

Make the most of yourself. You are still new and promising, no worries ;)

Or rather, a contest right before we can see our scores.

my first div-3 contest. feeling excited!

It's raining contests. :)

Does hacking solutions increases points of the hacker?

No. Hacks don't contribute to your final score on the contest.

the predictor isn't working !

Now Working

where can I find the predictor? Thanks

Read this

What is the test case 4 of problem E

How to solve Problem E? I was using DSU + DFS, but was getting WA!!

I did BFS + greedy

Got WA in 31st test case. I used BFS + Greedy!!

I am just finding all connected components and print number of connected components-1 but keep getting WA on TC 4

Take a case : 9 7 5 1 9 8 1 2 1 3 4 4 5 5 6 6 3

Ans will be 3.

No, ans will be 3

Answer will be 3 for your test case.

Yes it will be 3.

same except i didn't summit because i got tested against a test case

2 DFSs — keeping track of finish time.

but what is wrong with my approach why is it not going to give correct answer

According to your approach the answer will be 1.

3 1 1

2 3

Your answer = 2 (1 -> 2, 1 -> 3)

Correct answer = 1 (1 -> 2)

My idea : First, run dfs on capital vertex. While running dfs, make every path as bi-directional. Now build Strongly Connected Commponents. Count number of vertices which has 0 indegree expect the one containing capital vertex.

I applied your method. Its giving wrong answer at test case #3.

ummm :| I think you should read this

Ok, I ran Dfs on capital vertex. While running DFS, i made bi-directional edge. (Thus every point reachable by capital can reach back to capital). Now i built strongly connected components.....(Correct me if i am wrong until this point). After that, my idea is to count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.

`(Correct me if i am wrong until this point)`

As long as you use correct algorithm, (like tarjan's SCC or something) I think it would be fine.

`count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.`

You can just count number of SCC vertices which has 0 indegree, but when counting, exclude a SCC vertex which contains the capital vertex.

Gotcha!! Thanks.

Kosaraju I think

I used a similar idea but I didn't find the strongly connected components that Kosaraju does.

What was your approach then?

You run two DFSs. The first time you keep track of all the finishing times of the DFSs. Then run a DFS starting from the capital city. Then, while some cities are unvisited, keep starting a DFS from the unvisited city with the highest finish time, adding one each time we do.

Its Kosaraju :P

There's no transposing of the graph.

I did it that way! never mind..

Last three problems were a little difficult for div3

That was a lot of fun! Thanks vovuh

What is wrong with test case 8 in D. Any strong test case?

how to solve E?

I did it as follows : 1.)Mark all vertices that can be visited from s(by simple DFS). 2.)For rest of the vertices run DFS and count the number of nodes that can be visited by each of them.Sort according to the number of nodes visited by a particular vertex. 3.)Now run DFS from the last node in the sorted list and count the number of components left.

Was it only me who was facing problem to submit in the last 45 min?

For E, I removed all vertices that are reachable from

s(excludingsitself), and then found the condensation of the new graph. The number of SCC's with indegree 0 (excluding the possible SCC that containssand has indegree 0) is the answer. Is there a simpler way to do it?Is this approach wrong? 1. Find out the topological sort of the graph 2. run dfs for given s mark all visited 3. In the order of the toposort, run dfs and count components. 4. answer is components-1.

Btw, if u find anything wrong, u are free to hack!!

What about cycles in graph ?

I'm marking visited, so cycles won't be a problem. Provide a test case if u find anything fishy

I mean , how are you doing topological sort if the graph has cycles

which algo you are using for topological sort kahns or ... because kahns need atleast one vertice with indegree=0 in starting

I'm marking visited, and then not visiting a vertex if its already visited. Cycles will be handled automatically I guess. Sorry that I'm not able to comprehend what u are trying to say, so u may look at the code:-

999E

I had a similar idea. But I cannot convince myself that this approach works. Can you please help me?

Topological sorting gives you an order of vertices along which if you run dfs, you will get connected components in a directed graph. Thereafter, the answer is simply numComponents — 1

if you don't mind can you please elaborate this : "The number of SCC's with indegree 0(excluding the possible SCC that contains s and has indegree 0) is the answer"?

Each vertex in the condensation graph corresponds to an SCC in the original graph. Look at the vertices in the condensation graph that have indegree 0: clearly they are not reachable from

s. The other vertices, ones with indegree > 0 are reachable from some vertex with indegree 0. Therefore, we can add edges fromsto the vertices with indegree 0, and then the entire graph is reachable froms.However, there is one corner case: when the vertex (in the condensation graph) containing

shas indegree 0, we don't want to count it since a vertex is certainly reachable from itself. The second example input corresponds to this case.thanks for the reply !

What about the case when all the SCC's(excluding the vertex s) form a cycle(i.e none of them have indegree 0) and the vertex s is disconnected from the whole graph ?

In that case, the cycle will actually just be 1 SCC. And since

sis not a part of the cycle, the answer will be 1.Yeah.. completely missed it :p

The new condensed graph where all each node represents an SCC is always a DAG.

Let

a[i] be equal to 1, if we need edge (s,i) in optimal answer. Then instead of SCC after removing all nodes reachable froms, launch dfs from every non-used nodevand assigna[i] to 0 for all reachable nodes fromv. After that assigna[v] to 1. We can do it, because instead of any edge (s,i) we can place edge (s,v) ifiis reachable fromv.For every vertex count the number of vertices that can be visited from there. Use dfs from start and then you can iterate through every of these vertices in decreasing order and just use dfs once again.

Can you please share your code ? I am not able to view your submission for problem E.

how to solve D ?

first put all the remainders with counts less than n/m in a set and then iterate on each index with value greater than n/m and for each of them find the closest element in the set and add the required value.

ohhh ... i did almost the same except that i puted every remainder with counts != n/m and hence it had greater also.

Can you please explain a little more what you did. What do you mean by "and for each of them find the closest element in the set and add the required value."

yes, sure. First put all the remainders with counts less than (n/m) into a set and then iterate over each remainder which have value greater than (n/m) (let's suppose we are currently at 'i') and notice one thing we have to only move forward so, the best we can do is to conver current 'i' to it's nearest remainder having value less than (n/m) and so just do a binary search for that and find that index.(set's lower_bound will help you). Now, it may happen that we are at 'i' and there are no index in range [i, m-1] having value less than (n/m) so, in that case we have to search for the same from front.

Hope it helps!

Yes, Your comment made it very clear. Thank you :)

Can you please tell me why we only move forward?

EDIT : I got it that we can only add 1 every time. Thanks

Why should we convert "i" to the nearest remainder having value less than (n/m)? Can't we covert it to any remainder having value less than (n/m)?

because it may happen that some of the remainders before it (nearer to the current one) has a value greater than (n/m) and so, if we convert that then we have to pay less.

Anyway, all remainders have to be filled equally. So if we convert "i" to its nearest one, then there may be some "j" which needs to travel farther and satisfy the next remainder. Else, if "i" already travelled farther and satisfied the second remainder, then "j" will just have to satisfy the nearest (first) encountered remainder. Both ways seem the same to me. Am I going wrong somewhere? If yes, please explain with a small counter case.

you forget that we can only move right!

let's aarray be 3 1 4 1 1 and we have to make all 2's.

Then if we add 3's 1 to the 4th position (instead of nearest 2nd) then we have to take the 4's 1 to the 2nd position in which we have a total cost of (3 + 2 + 4) instead of the optimal cost which is (1 + 1 + 2).

Hope it makes your doubt clear.

Did the same and got TLE in 4th test case. You can view my solution on my profile.

i thought abt it..but don't u thnk it's complexity will be O(n*n/4)??

see there are atmost 'n — m' elements that are greater than n/m and similarly 'n-m' indexes are there which have less than value n/m. So, we are inserting 'n — m' elements and for each of 'n-m' element we are doing a binary search. so, O(NlogN)

Consider every reminder c[i] a container that can hold at max n/m numbers. As you read the input you put a[i] in the container c[ a[i] % m ], if it's full: you put it in the next available container and add to a[i] the number of steps. To do it quickly the next available container is registered in another array.

Let me know if that makes sense.

EDIT: An array to store the next available container isn't good enough, a set is needed.

Hey there! I am also very stuck on this problem and your solution is not making sense to me. I have some questions, hope you will answer.

-- If C[ a[] % m ] is full, how do you decide the next bucket in the container? Why do you add a[i] number of steps?

-- At the end how do you track what the final array is?

Thanks

This is the code if you couldn't find it 39498091.

-I decide the next bucket by lower_bound(a[i] % m) in a set of buckets, every time a bucket is full I erase it

-I add to a[i] the difference between the buckets, which is how many times I have to increase it

-The final array is the original one that I changed every time

Thankss, alwerty u explained D in easy way :)

Thanks for the explanation

How to solve F?

Consider any single number of card. Now the problem is 'For given

Ncards andMpeople, each person can have at mostkcards. What is the maximum score?'orange4glace, Sorry, I didn't get. Can you please elaborate more, what's the intuition behind solving problem F with an example?

Since

his strictly increasing, it is optimal to distribute as much as favorite cards to each peraon. eg. Let 3 people likes`card 1`

and each person has 2 cards. If number of`card 1`

is greater than or equal to 3×2, just distribute 2 cards for each and leftovers are 'dont care'(any other will have it and it has no effect to score) Else if the number of cards is less than 3×2, now the problem is`distribute m cards to 3 people while maximum the score`

Thanks, got it!

can anyone help me how to solve problem D????

http://codeforces.com/blog/entry/60096?#comment-438911

Does anyone knows what is wrong with my solution(39488794) on 999E - Reachability from the Capital? :(

The ideia i've used was to find all SCCs and make a new graph composed with those contracted SCCs. The next step was to add edges between the capital and the SCCs whose had vertex with lower degree.

Thanks!

Count SCC's with zero in degree (except the SCC's containing the capital city).

Help on E appreciated, please let me know what's wrong with this approach (which fails pretest 4):

Thanks a lot for any insight!

When you remove the first element of the priority queue along with all of its childs it is possible that you change the degrees of some of the vertices that are still going to stay in the queue.

Please can you help me out to figure out the mistake.

Here is the link to solution-

I don't think it's OK to have contests in which almost all participants solve the first X problems, but then only a small percentage of them solve the (X + 1)th problem. The difficulty distribution seemed a little off for this round.

As usual for Div.3 rounds

Totally agree. There are about 2000 participants (ranked ~#500-#2500) solved exactly 3 problems.

I dont think its optimal but I dont think its unacceptable either.

Any miniature version of test 4 of E?

This test is just a complete directed graph with a 71 vertices and n * (n — 1) edges.

UPD: Woops, the fifth test was a complete graph. I was wrong. The fourth test is a just random directed graph with an 5000 vertices and 5000 edges.

vovuh Can you please tell will there be editorials for this round. They are not on home page.

The editorial will be available in few minutes =) Sorry for delay, i was on the exam today

Can someone tell why 39491266 gives WA but 39491559 gives RE for problem D.

I only changed all "int" to "long long".

maybe something overflowed and when you took the remainder you got a negative value, which then caused you to look at a negative entry of an array?

I had been debugging my solution D(39490746) for half an hour. When the contest is over and I saw the test case, I realized the result is long long. So it(39494662)passed...

I rage quited after 3WA's in E and D

After the contest I checked my E again and Saw this:

""Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:92:12: runtime error: index 5000 out of bounds for type 'int [5000]'

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:92:12 in""

I wish I would have checked my array sizes rather than rage quieting cf after 3WA's

and also wish codeforces will give RTE verdict rather than WA for these :p

Nice Problems Overall :D

Contest was not beautiful as its id.

How MYTH_vs_REALiTY solved all tasks in an hour ?

His code looks different from his usual code.

Yes totally and unless having that template gives a coder magic powers I think something is fishy.

Same is the case with BigDelta

So, this was my first contest on Codeforces and I can't seem to find any ROOM link on the top menu bar nor can I find a way to lock my submissions so that I can participate in hacking. Do first time users don't have this privilege of hacking or am I missing something?

This is Div.3 Round.

`after the round it will be a 12-hour phase of open hacks`

-there isn't hacks during the round.Isn't the round already over?

same here i cant find my room, if anyone can help us

Its open hacking. You can hack anyone's solution.

k

There isn't any rooms. Rooms are needed in rounds with hacking during them. There is such thing as CF predictor: expected results of this round

Thank vovuh for your contest, it was more difficult than last div 3 round.

Funny, it seemed simpler to me! BTW, I found the last div 3 round more difficult than some div 2 (not that I have much experience, however)

I solved only 4 problems and its my first constest, my rank will go up or down?

try this cf rating change predictor

Why My code for D getting runtime error on test 8 ?

Probably because of the "matrix index out of range"

In problem D i used a queue to store the number remainders . If the size of the remainders > n/m then we move one by one to the next container with the value (previous + 1). And keep doing that until everything is equal to n/m (only 1 needed 1 for) and traces and etc, why am i getting TLE ? and how can i fix this or maybe another approach ? Code : https://ideone.com/Z6Y8I5

It seems to me like you have nested for loops. Oouter loops iterates until m and inner loop iterates until trace[i], which (at least at first glance) seems like it could be O(n). So overall complexity would be O(n^2)?

ah okay i think i get it, so is there anyway to optimize it because i cant find a way to trace the answer

You can use something like dsu (I don't know the name for this technique) so every remainder >= n/m won't be visited again

http://codeforces.com/contest/999/submission/39476990

Correct me if I am wrong but I think your solution has quadratic complexity as well. If n = m, then the only stop condition of your

`cari`

function is that`val[x]`

is 0. So For a case like:When processing the first number you'll take 1 step, when processing the 2nd number you'll take 2 steps etc. So overalall you'll take N*(N+1)/2 steps.

Isn't the answer for that tc is 0 change? My

`val[x]`

is only incremented after I found the valid position for current number, so`cari`

will only be called once for each number (Because`val[x]`

is still 0)Sorry, I didn't notice you actually modify the

`nex`

array (also the test I wanted to type was an array full of zeroes, but it doesn't matter anyway).Nice technique bro thanks, i finally understand your code!

can someone help me to find out why the first solution was not accepted but second got accepted for problem B

http://codeforces.com/contest/999/submission/39483346

http://codeforces.com/contest/999/submission/39486399

It is not advisable to insert characters in C++ string like this s[i]=ch. You are allowed to do this in character array string.

Really? So... how did you do it in your solution?

Are both of you joking?

Maybe I miss something but...isn't the problem with s1[r--] operation? These parts of code aren't the same, of course:

compare with

Doing something with s1[-1] and s1[0] aren't the same.

changing s1[r--]=s[i] to s1[r]=s[i] doesn't make any difference. Still runtime error in testcase 8.

Oh, sorry. I was a little tired yesterday. aditya10 is right. Little more: string is an object. When you initialise "string s1;" constructor make it s1 = "".

So, when you write "s1[r] = s[i]" you just change the element with address s.begin() + r (not s1). And... we don't no, what the rubbish is there. When you are trying to change it, you can get an error.

When you print the s1 itself (cout << s1), you see that it doesn't change. s1 = "".

So...just initialize "s1 = s;". Now it has got the same number of elements as s, and all will be ok.

Doing s1[r--]=s[i]; and s1[r]=s[i];r--; are actually same. In post decrement value is decremented after being initialized.

Regarding question D

I wrote the code using lower_bound(st.begin(), st.end(), t) and got TLE but when i wrote the same code using st.lower_bound(t) it got AC. Why this happened???

https://stackoverflow.com/questions/31821951/c-difference-between-stdlower-bound-and-stdsetlower-bound

A, B, C was too easy and C, D, E was too hard. So the standings will probably depend on penalties.

""A, B, C was too easy and C, D, E"" i geuss you meant F D E and thats actually true , they are harder than most B's in div 2

I just realized I really need to practice to be a better coder.. I got the idea of d but struggled alot coding it and didn't have the time to solve it because of some annoying coding mistakes :(

Why my solution for problem C is exceeding the time limit in testcase#5 despite having linear complexity? here is the link: http://codeforces.com/contest/999/submission/39496135

I assume that

anss=s[n-1-i]+anss;may be O(N).Because it doesn't have linear complexity :)

The

`+`

operator for strings (from line`anss=s[n-1-i]+anss;`

) is not constant time, but linear (see documentation). Considering the outer for loop as well, it results in quadratic time complexity.Thank you. I overlooked it :(

Can someone explain the first test case of Problem B? In the above statements, it say in decreasing order. I try to implement the algorithm but got different results on test case 1 and 2.

the task is to decrypt, the problem description algorithm is to encrypt

Actually you are given the resultant string in the input,and you need to find the original string from where it is transformed. So basically you have to do "rocesfedoc" --> "rocesfedoc" --> "orcesfedoc" --> "secrofedoc" --> "codeforces". Opposite of what is explained. So most probably you are sorting the divisor array in descending order, sort it in ascending order,you will get correct answer unless your code is correct for reversing the string.

Hello! Can someone help me with Problem D? I saw the comment, but I do not understand it. Will appreciate if someone can explain the idea and how you reached it.

For Problem D, I did a BFS from the initial array until

onearray suceeds. This I feel is correct, but I had a memory limit exceeded within test 5.Thanks

Hack for Problem C?

Can D be solved using two pointers ?

I think its possible if you first sort the entries of the array in increasing value of the remainder mod m.

What is the effect on rating after hacking others solution in this round?

Hacking that take place after contest have no effect on rank (for hacker). So no effect on rating.

can someone explain the idea of F?

For a fixed type of cards you have

xcards andcplayers that them likes this type, so compute thedp[i][j](maximum value that you can get) whereiis the number of remaining players andjis the number of remaining cards initiallydp[c][x]=0and the answer will be indp[0][0..x]I leave the link to my solution for a better understand of this idea: 39504913Thanks for conducting another div3 round!!

Can someone explain question F to me? I've read it thrice but I do not understand.

My solution for D: 39490456.

I believe my answer is just a permutation of the correct answer ( 4 2 1 6 11 12 ). Should this not get accepted considering

anyarray satisfying the required condition is correct?The only operation you can do is incrementing an array element, changing order is not allowed.

Alright. Thank you so very much.

vovuh please check my submission for B it is not showing output on codeforces while the same is giving correct answer in my ide. This took my 40 mins. here is the code-!! :( Anyone having idea of this? Thanks for your insight!

You can't use

`scanf/printf`

with`ios_base::sync_with_stdio(false);`

You can read this blog (look for comments)Thank You! :)

Actually, that's only half true. What you shouldn't do is MIXING either

`scanf/cin`

or`printf/cout`

in the same code (since different streams aren't synchronized, there's no guarantee what will be read or written first). Otherwise, using only one from each pair is usually safe.U mean scanf and cout or printf and cin? Right?

Yes, no problem with those.

Problems A, B, C vs problems D, E, F

But really why was it like this? 100 participants with a full mark and almost all others with only three questions... Then the one who just codes faster, gets a better result. Is it a marathon or a contest???

Newbie here! Can anyone explain why I got TLE on problem C?? Problem C submission

The time complexity of your solution is O(n^3). It can be solved with much better time complexity. Link : My solution

My solution for D: http://codeforces.com/contest/999/submission/39505442. I think it's O(n) ?

can you please explain your approach?

Last two for loops where each runs m times, contain a while loop. Can you explain how its complexity is still O(max(n,m)).

each for loop runs m times, each while loop runs maximum n / m times => I think total complexity is O(m * n / m) = O(n) ?

If we look at while loop independently, it will run the number of times equal to number of elements not "in place". So say all elements have same reminder, the while loop might run, roughly speaking, O(n*n/2) times. Still I am not sure, what do you think about it?

int d = n / m;

int need = d — v[i].size();

=> need <= d

=> need <= n / m

while(need--) => each while loop runs atmost

needtimes orn / mtimes.Okay thanks. I got it now.

where i can find editorials/solution of the contest?

Can anyone figure out the mistake in this solution for E? LINK

For tc #4, it is computing 1818 as the answer instead of 1817.

Approach :Run a dfs from source and mark all reachable nodes. Now, run a dfs from every unreachable node and mark all the ones that are being traversed from some parent. Suppose, we're running dfs from 2, we will mark every node reachable from 2 as visited, but we'll keep 2 as unvisited. This way, we will know the nodes(and components) which require a path from source.What if while running the second DFS you reach a node marked by the first DFS. What do you do?

I'm ignoring it, because the nodes which can be reached from this node would've already been marked.

I am facing the same problem. And does it matter that after running second dfs if we come across the visited nodes from the first dfs,as they are already visited and reachable from s.

Check for this test case 5 4 5 1 2 2 3 3 1 4 3

Correct Output: 1

Thanks for that.

Why is this http://codeforces.com/contest/999/submission/39505722 submission of mine for A giving WA on this case: 6 6 7 1 1 1 1 1 The answer is actually 5, but in cf it is showing 4. But in ideone compiler it is giving right answer. Link: https://ideone.com/je07LC

The

posvariable is uninitialized, causing ambiguous results.https://codeforces.com/contest/999/submission/39470600 Mine is also giving a WA on 23. I have initialized correctly I guess.

Your code did not check if start and last are out of bounds.

Okay. Thanks

When all elements have values less than k, value "start" is equals n, n+1, ... , because you are have a rubbish in anon[n,∞).

why rating is not updated yet?

did all the testcases are run or some testcases are yet to be judged during system testing

Is the system testing done? If not, when?

I want know this,too

This is the only question after every round in acpc format at codeforces..

Can't believe that i have solved 5 problems!

For some reason 999F reminds me of game theory/mechanism design about auctions, when I first look at the joy level constraint I thought "oh this is a gross substitute valuation" instead of "oh it's strictly increasing"... Weird.

System testing has started now.

.

You are not checking for (start<n)

Yeah I got it now. Silly me -_- Thanks for replying.

It would be great if someone can put

editorial's linkhere. Thanks in advance.I got TLE in Java for problem C and I got very confused about my logic. But then I researched a little more and I wrote this for Java programmers:

https://letsdocp.wordpress.com/2018/06/22/java-in-competitive-programming/

I am getting MLE in problem-D test-5 here. I have made vector and map of linear order.Anyone help ?

I guess vectors do not release memory after popping up the elements. I used stack in your code hereinstead of vector and it shows TLE. The underlying approach is wrong.

all those who got stuck on test 4 of problem E can try this test case no 47: 8 8 1 3 2 3 4 4 5 5 3 6 4 6 7 7 8 8 6 ans:1 you might be getting 2...

UPD: I got the mistakeIn E, for test case 20, I get answer as 11, whereas the solution ans is 12. I even added the edges and put asserts to check that every node is indeed reachable from s, however I did not get any assert failures. Someone please point out what's going wrong with my solution, thanks! 39515068

i think you were first doing dfs of capital node and then for every non visited node ,finding all other nodes from where you can reach to that node ,by backtracking the reverse adjacent vector and doing dfs on all back nodes....

I'm not sure about that. The mistake here was I added edges as bidirectional from input, but it actually has way more issues :P

How to solve E?

First check for every vertex 'a' how much vertices can go to 'a'. Then sort vertexes by sizes of groups. Notice that for every group you only need to add one road for all vertices in group to be connected to root. Iterate groups from biggest to lowest, check if road exist before you add one. If you add one road, notice that you made all vertices that belongs to the group connect to root. If they are connected, you shouldn't build roads because they're already connected.

If you have for example root: 1 2->3 2->1 4->3 First sort groups (3 will be first, then 1 and 4)

You add one road (3->1) and then 4 becomes connected. Next up is 4, but 4 is connected trough 3 so we move on. Next up is 2, but 2 is also connected to root.

I need help, even though my solution for test 1 was right, it gives WA on problem D. Here's the submission. Mine code outputs: 3 0 2 3 8 10 13 their answer: 3 0 2 3 7 10 14

Input:

Your Answer:

You can just increase elements by 1, you can't change the order.

I am getting WA at test# 4.

I tried Solving E:

1. Did the DFS on s, marked nodes visited.2. initialized c = 0(counter: for counting connected components in Graph), then started running DFS on every node except S, forwardly(means when in the edges direction) and then took a step backwards(means run the loop to iterate over all the node which is pointing towards current node, for, eg, if 2 is current node and there is an edge 4->2, then I went back to 4.) and obviously marked the nodes visited.3. then counted all the connected components.here is my link: http://codeforces.com/contest/999/submission/39517716

Actually, my idea was simply to have the no of connected components fo graph. can someone please point out the mistake??

Your Solution Will have no of Connected Components in Undirected Graph But in The Problem The Graph is Directed.

can you give me an example?

Try This Example

The Output is 2 But Your Code Prints 1 , Because Graph is Directed But Your Implementation is to find number of connecting Components in Undirected Graph.

Thanks for the help!!!

I just couldn't understand this at all!! that why on test case 2's last line "4 1" my code is giving runtime error, and if u change it to like "5 1", it will give the answer, I couldn't understand why?

This is the link http://codeforces.com/contest/999/submission/39538352

There's Problem in dfs1 It doesn't Stop.

I think Problem is in that Line

No, I checked that problem was in Line "node[x].pb(y);" because after that it's not printing "----" and this only arouses in "4 1" case.

how this example is giving output 3 in my code?? can u explain?? http://codeforces.com/contest/999/submission/39526515

Could You Explain to me The Idea of Your Code ?

Actually the idea was wrong but thnx really for helping out!!

Your crafting.oj.uz ratings are updated, check it right now :)

Since the system testing is done and my solution for E passed the tests,though i still don't know if its correct.

My solution:Find all the cities not reachable from capital and add a directed edge from capital to it.Now for all newly added edges just remove that edge and check if its possible to reach all cities from capital.If yes, then just remove that edge and continue checking for other edges,else add that edge back and continue checking.

I don't know how to prove that this gives the optimal answer.Can someone prove it or give some counter test for this?

We know that an optimal solution is given by the following algorithm: for every SCC with in-degree zero, add an edge from the capital to some arbitrary node from that SCC.

It is obvious that the edges your solution provides includes a set of edges that can be generated by the algorithm above (in other words, your solution does add an edge from the capital to every SCC with in-degree zero).

What's left to prove is that your solution does not add any extra edges. Let's suppose via reductio ad absurdum that such an edge is added. Since it is an "extra" edge, it can fall into one of the following two categories:

1) An edge from the capital to some SCC with non-zero in-degree. 2) An edge from the capital to some SCC where such an edge was already added.

For case 1, that SCC is still reachable without this edge, so by definition your algorithm will have removed it, therefore it is impossible to have this kind of edge in the end.

For case 2, since an edge was already added to this SCC, it means that its in-degree is now non-zero, therefore it can be reduced to case 1.

We can conclude that your algorithm can not produce any extra edges, therefore your solution is optimal.

What is the solution of problem D????

For every a[i] (if number of a[i]%m is greater than n/m) find nearest x (0<=x<m) which is greater a[i]%m and number of x in array a[] is less than n/m and increment a[i] by (x-a[i]%m)

check my solution for more details

I got WA test 8 problem D, I used set and binary search but I still don't know what is going wrong? Here is my code

EDIT: Oops, fixed it!.

editorial?

http://codeforces.com/contest/977/submission/39520609 Can someone tell me where I've gone wrong? Thanks!