Привет!
21 июня (четверг) в 17:35 (Московское время) начнётся Codeforces Round 490 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 задач и 2 часа на их решение.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
UPD: Также спасибо step_by_step, kevinsogo и nhho за помощь в подготовке раунда и его тестирование.
UPD2: Таблица результатов!
Поздравляем победителей:
| 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 |
Поздравляем лучших взломщиков:
| 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 успешных взломов и 226 неудачных взломов!
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Problem | Competitor | Penalty |
|---|---|---|
| A | jh05013 | 0:01 |
| B | JerryKFC | 0:02 |
| C | GrayGlobe | 0:03 |
| D | T______________T | 0:21 |
| E | NamikazeBoruto | 0:11 |
| F | Counting_Stars | 0:20 |
UPD3: Разбор
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
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.
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 square of the number of problems. On the other hand, the penalty from the WAs would only increase linearly, 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?
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
IIR?
(Abbreviation of Is It Rated? :P)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
PS- Thanks for not clashing it with Argentina Vs Croatia match.
Thanks for the downvotes. Will try to improve myself.
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.
Объясните пожалуйста, чем в итоге отличается достоверный участник от недостоверного, разве это поможет борьбе с неспортивным поведением? Ведь в итоге он рейтинговый для всех. Смогут ли недостоверные взламывать?
Кажется, админы сами не поняли, что ничем не отличается.
Недостоверные участники не попадают в таблицу официальных результатов. Они делят таблицу результатов с неофициальными участниками. Таким образом, они почти незаметны для "достоверных". С одной стороны это понижает дискомфорт для честных участников (это всегда неприятно видеть выше себя нескольких новичков, которые, наверняка, участники из первого дивизиона), а с другой — уменьшает мотивацию читеров так себя вести. На взломы и подсчёт рейтинга это разделение не влияет.
Спасибо, теперь почти всё понятно. У достоверных и недостоверных разные комнаты?
Нет. Может и да, но ты об этом не узнаешь.
Они просто появляются, когда тыкаешь "показывать неофиц." и отличаются тем, что имеют звездочку рядом с хэндлом
IbragiMMamilov, я не прав.
Мы будем исключать из официальной таблицы результатов Div. 3 раунда и помещать в отдельную комнату всех тех, кого достоверно сложно назвать реальным участником.
https://codeforces.net/blog/entry/59228
my first div-3 contest. feeling excited!
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
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
2 DFSs — keeping track of finish time.
but what is wrong with my approach why is it not going to give correct answer
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.
Last three problems were a little difficult for div3
Спасибо за контест , задачи интересные были;
Особенно начиная с D
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 (excluding s itself), and then found the condensation of the new graph. The number of SCC's with indegree 0 (excluding the possible SCC that contains s and 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 from s to the vertices with indegree 0, and then the entire graph is reachable from s.
However, there is one corner case: when the vertex (in the condensation graph) containing s has 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 s is not a part of the cycle, the answer will be 1.
Yeah.. completely missed it :p
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 from s, launch dfs from every non-used node v and assign a[i] to 0 for all reachable nodes from v. After that assign a[v] to 1. We can do it, because instead of any edge (s, i) we can place edge (s, v) if i is reachable from v.
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.
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 :)
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.
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
How to solve F?
Consider any single number of card. Now the problem is 'For given N cards and M people, each person can have at most k cards. 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 h is strictly increasing, it is optimal to distribute as much as favorite cards to each peraon. eg. Let 3 people likes
card 1and each person has 2 cards. If number ofcard 1is 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 isdistribute m cards to 3 people while maximum the scoreThanks, got it!
Четкие задачи, но резкий скачок от C (3372 успешные посылки) к D (381 успешная посылка) — это мощно)
can anyone help me how to solve problem D????
http://codeforces.net/blog/entry/60096?#comment-438911
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.
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.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 ?
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.net/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
carifunction is thatval[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, socariwill only be called once for each number (Becauseval[x]is still 0)Sorry, I didn't notice you actually modify the
nexarray (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.net/contest/999/submission/39483346
http://codeforces.net/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.net/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 lineanss=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 :(
Че-то у вас уже второй раз нифига не див 3 получается.
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 one array 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 x cards and c players that them likes this type, so compute the dp[i][j](maximum value that you can get) where i is the number of remaining players and j is the number of remaining cards initially dp[c][x]=0 and the answer will be in dp[0][0..x] I leave the link to my solution for a better understand of this idea: 39504913
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 any array satisfying the required condition is correct?
The only operation you can do is incrementing an array element, changing order is not allowed.
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/printfwithios_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/cinorprintf/coutin 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.net/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 need times or n / m times.
Okay thanks. I got it now.
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
Why is this http://codeforces.net/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 pos variable is uninitialized, causing ambiguous results.
https://codeforces.net/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.
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.
Need editorials!
.
You are not checking for (start<n)
Well I got TLE for C problem due to Java. That is why I am providing a link which could be helpful for Java programmers:
https://letsdocp.wordpress.com/2018/06/22/java-in-competitive-programming/
It would be great if someone can put editorial's link here. 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 mistake
In 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.net/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.net/contest/999/submission/39538352
There's Problem in dfs1 It doesn't Stop.
I think Problem is in that Line
how this example is giving output 3 in my code?? can u explain?? http://codeforces.net/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!!
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?