<almost-copy-pasted-part>
Привет! В Dec/12/2019 16:35 (Moscow time) начнётся Codeforces Round 605 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
UPD: Огромное спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за тестирование раунда и помощь с исправлениями ошибками! Артем также предложил одну из задач на сегодняшний раунд!
UPD: Разбор опубликован!
Hope to see non-black IDs win this contest(for whom this isn't first contest)
Winner is a pupil ;)
Oh yeaaa great lol
Непривычно видеть vovuh желтым :)
Anyways I hope high ratings to all the non-black handles
The only real black handle is MikeMirzayanov :)
Oh actually bro had said that for top reds who make new handles in each contest just to win in lower divisions and absorb the ratings of others
Agnimandur Whats about Una_Shem ? if MikeMirzayanov only Black !
vovuh one love
Orange vovuh![](/predownloaded/d4/29/d42912084061131554724248b6f869f869eabc88)
I think it is the first round made by vovuh as a Master . Good Luck and I hope the contest will be nice .
Add the information to the right to capture the audience.e.
will 15 december held two contest?
After a long time Codeforces arranged a contest. I am waiting for this contest. I think, the contest will be nice and interesting for me and also for others. Thanks to MikeMirzayanov and vovuh for arranging the [Codeforces Round #605 (Div. 3)] contest.
hoping to qualify for Codeforces platinum!
What is Codeforces Platinum?
I think he means Usaco Platinum xD
Do you have a crush on Nightmare05 or what? DreamR
Not that lucky bro xD
А где регистрация или ее нету?
Регистрация открыта. Перейдите, пожалуйста, по этой ссылке.
Is the scoring (points per problem) known?
"The round will be hosted by rules of educational rounds (extended ACM-ICPC)"
Thank you for the answer.
perticipantes are ranked based on the number of problems they solved and the time.
So, importance of all problem is same.
codeforces server seems to be broken same code giving diffrent output on my macinhe and server on my machine my code passes the same code while on server produces wrong ans i got 3 penalities due to that still not able to submit ..
Use custom invocation on cases like that, and then debug.
+1 the main website was broken and I wasnot able to open it until the contest was over.
Yup site was broken for me too. Took part from m1.codeforces.com.
Can anyone hack this solution 66706230?
UPD: Hacked, thx dead_blue!
How to solve D? I kept going in circles thinking about stack and non-positive difference...:(
I can't tell you how to solve it in English, but you can check my solution, maybe it will help you. https://mirror.codeforces.com/contest/1272/submission/66702493
Maintain 2 arrays, Increasing and Decreasing. Increasing[i] will store maximum increasing subarray till ith element, similarly Decreasing[i]. For each element check if (i+1)th element is greater than (i-1)th element, If true, then we can delete this element and updated ans=max(ans, Inc[i-1] + Dec[i+1]).
Elegant Solution, can you explain why this holds?
I didn't use this dp approach. The following is the algorithm I came up with. First find all strictly increasing continuous subarray and store each such subarray's start and end index as an interval. Update the max length for each interval.
Then iterate through all intervals and check every two adjacent intervals and do the following. 1. if the current interval only has 1 element, remove it, get the next interval if possible and check if the previous interval and this next interval can form a longer strictly increasing subarray. Update max length if necessary.
The above solution fails on test 14 by a difference of 1. Can you help explain why this solution is incorrect? My submission is 66729847. Thanks!
Your idea is almost same as me.
I stored all strictly increasing sub_sequence block.
Then updated result by comparing all block size.
After that i took 2 consecutive block each time. If 1st block has size > 1, then we compare the 2nd element from last of 1st block with 1st element of 2nd block. if a < b then we have a length of block1+block2-1. Similarly i checked by ignoring 1st element of 2nd block.
https://mirror.codeforces.com/contest/1272/submission/66754733
Yeah, I think our idea are similar in general, except that I made the mistake of comparing value with index in one of the if statement, if only I could realize that during contest :(
Thanks for replying though, without comparing your code I probably wouldn't even realize that bug in my code.
do dp. dp1[i] = maximum length of increasing contigous subarray having the element of i from 0 to n. dp2[i] = maximum length of increasing contigous subarray having the element of i from n — 1 to i. Find out max length of subarray without removing element.Initially, this is the ans. And then, for every i from 1 to n — 2, check if(dp1[i — 1] + dp2[i + 1] > ans && v[i — 1] < v[i + 1]), if yes, then ans = dp1[i — 1] + dp2[i + 1]. That's it.
Let pre[i] be the maximum possible length of strictly increasing contiguous subarray of array a from index 0 to index i
Let suf[i] be the maximum possible length of strictly increasing contiguous subarray of array a from index n — 1 to index i
Loop from i = 1 to n — 2, if a[i — 1] < a[i + 1], then ans = max(ans, pre[i — 1] + suf[i + 1]).
very similar to this problem: PIBRO
This AtCoder Problem is also an interesting one that you can solve using the above technique:
GCD On Blackboard https://atcoder.jp/contests/abc125/tasks/abc125_c
I've made a string of
0
and1
of length N-1, where1
means $$$a_i < a_{i+1}$$$.Then applied a regex
/ 1+ 0 1+ /x
, and checked elements near matched0
if they increase after one deletion (i.e. if exists $$$j$$$ that $$$a_j < a_{j+2}$$$, where $$$j$$$ is near0
). Perl code 66779749.How to solve F? LCS and some post-processing?
No, it is dp.
I tried dp, but tbh, backtracking in dp made it quite implementation heavy.
Same feels. I coded a dp solution with backtracking for around 240 lines. Couldn't fix the bugs within the contest time. Got it accepted after contest.
You can find my submission here.
Simple DP in $$$O(n^3)$$$. Notice that the answer's length cannot exceed $$$400$$$ and do dynamic programming. $$$dp_{i, j, bal} = $$$ minimum total length of the string with the first $$$i$$$ characters processed in the first string, $$$j$$$ first characters processed in the second string and the current balance is $$$bal$$$. Transitions can be made in a straight-forward way (nested loops) but you should do them carefully or by bfs/recursion.
Out of curiosity, is there a solution faster than cubic, or is the n^3 solution the fastest intended solution?
I tried to come up with some faster solution but failed :( Maybe some cooler guys found something interesting.
You are the coolest! :D
Actually, because problem limits were low, I just used dynamic programming.
My state was (current unincluded character from S, current unincluded character from T, current bracket prefix). For some reason that I do not quite understand, the bracket prefix will not go above 200 and thus my state is 200^3=8000000 which is good.
My transition is "add open bracket/add close bracket" depending on whether they are possible operations. I store which transition is better so that I can backtrack later to construct the bracket sequence.
It passed the tests, so I think it's probably correct, but that was one of the ugliest case-check DP I have ever coded. Very unlikely to be official solution.
In my solution, there is no case-checking: pastebin
Any hints for E?
Multi-source bfs on the transposed graph.
What is the need for the transpose of the graph ? why a normal graph ( edje from i to a[i]+1,a[i]-1 ) will not work ?
Read this to understand
Yes I read it after posting the comment. Nice question.
Take 2 additional nodes, and reverse the graph...Think about it afterwards.
Form a graph from a[i]-i to i and a[i]+i to i.(a[i] -i >=1 , a[i]+i<=n) traverse the adjacency list and insert points on the other side of the edge in the queue if parity of both points are diffrent. (these points will have minimum distance which is 1). perform bfs.
Hello ; I constructed the graph in the same way ; but then I was doing DP on this graph...
What I did was that let say node u has immediate child 'v'. Now if parity(arr[u]) != parity(arr[v]) ; then ans[u] = 1 ( This means that we may reach from u to v using only 1 step ).
Else ; from all children of node u ( Which will be all v ) ; we may find the answer to node 'u' as ans[u] = min ( ans[u] , ans[v] + 1 ).
But this gives me WA. Do you know what might go wrong in this approach ?
CODE
There may be a cycle. So it might possible that you are not updated the current node and it calls again from its child.
Could you please elaborate a bit..
I understand that there are cylces. I understand the the child might have an edge that is directed back from child to parent ( Or in general from child to some ancestor ).
Doubt : When we came to that child ; we will come only after visiting the parent ( ancestor ).
So even if there is an edge from child back to the parent ; we won't go over there again as the parent is visited ; and we don't re-visit the nodes in dfs.
Clearly I have not understood something ; can you please elaborate a bit more...
Thanks !
Let take a node having three children{p, n1, n2, n3}, and there is a cycle b/w p and n2. Now your value of p = min(n1, n2, n3}, but when you go to n2, p is already visited but its value is not updated as it depends on value returned by n2.
Ah I see... So you mean that by this we will never update the value of n2 as it's value would have been updated via p ; but P is itself not updated yet as it will get updated in the backtrack move of dfs.
Have I followed?
correct. check this, it is easy to understand
Thanks a lot for the help :)
How to solve E. I thought of bfs + dp but couldn't implement.
Check this comment.
That comment answers F.
There is no constrain in problem B that length of string cannot be zero. Empty space should also be taken as correct input. Attempting to use this testcase for hacking shows invalid input. Is this intended?
There are no empty strings in every test and empty strings are not allowed to input at all. Seems like it would be better to mark this in the problem statement more clearly.
66723421 ohhhhhh, I should go to E when my D's solution is wrong that taken too much time to debug.
Am I the only one who accessed CF from http://m1.codeforces.com after solving A ?
The main site did not open for almost 2hr.I thought Round will not be rated but since 2200 users solved d, i think it will be rated.
Every day I have headache there is got to be a CF round SMH.
and I think I'm the only person who solved E but not D.
https://codefoces.com not working during the contest and I was thinking that my internet stopped working wasted my 10minutes
Yeah mine also, code forces stopped working after solving A .
It is from your side site was running perfectly ok :)
The server was down throughout the contest. Did I only face the issue??
Organizers please make the contest unrated as the site was down during the contest.
Not a valid reason because m1 website was up for the entire contest.
How would I know about it?
General knowledge
this is not at all a valid reason for contest to be unrated .I also face the same problem , but then i shifted to m1 .
I think the internet issue / connectivity was the problem and not codeforces "down"
Need help in E. I thought of the dp solution, i.e let's start visiting every element and finding whether the given conditions satisfy or not. 66716159
MikeMirzayanov it is a request. I wasn't able to access the codeforces website after 9 minutes and hence wasn't able to continue with the contest after a wrong submission of A. This is leading a drastic rating drop for me. It is hence my humble request that if it be possible then please do not allow for my rating to change. As a proof that I could have done it, I have submitted another solution of A with a minor tweak. It works just fine and I was ready with it after a minute of my wrong submission but wasn't able to access codeforces due to unavoidable circumstances. I hope you'll help me in any way if possible.
Why you did not continue with any of the other options the management has given ( m1 , m2 , m3 websites ) ?
i got a small problem in my code in problem F if someone can help me i just did dp[curr positions in s1][curr position is s2][diff between open and closed brackets] i will represent it as dp[curr1][curr2][val] i can made transitions just if after the transition the val will stay non-negative and then i know the length of the answer is less than or equal to 400 so if length > 400 or the val is > 200 i will just return inf that is my first submission 66726623 which just returned inf and that is my other submission 66727771 which i just return when siz > 1000 and it got accepted can someone explain the what is the problem please ?
Thank You vovuh I Loved this contest and I Love Div Three <3
Still after being hacked ?? :))
it's ok :(
Please give hint for F.
Think of a dp with transitions similar to LCS and more state parameters.
You can find my submission here. :)
I felt F was implementation heavy for those who are comfortable with top-down dp, especially the backtracking part.
If you can't wait to see the official editorial, come to see My Unofficial Editorial :)
Like to see comments and responses from you guys!
I think A can be solved on much easier way.
just calculate sum of current distance from given input. Let say it d. Then max(0,d-4) is answer.
Movement for friend who is in the middle doesn't make any change. Moving left one right will reduce distance by 2 similar for right one. You can reduce at most 4. Finally check reducing making it negative or not.
Can anyone explain how to approach problem B?
Hint: Try the move in a rectangular path.
If you go one step right then you also need one step left to come back ,similarly for up and down ...another case is if you can't move up of down then you can't move left and right more than 1 ..hope its enough for this problem
How would you do E? I tried BFS with adjacency vector, but no avail :(. It gives TLE on test 8.
UPD 1: I tried again this time with an array that stores the closest node with opposite parity to make my code faster. Also TLE on test case 8.
66742260
After moving to position 10, you can make 1 more move to position 6 (10 — 4 = 6), position 6 has value 5 which is odd. So that is why the answer is 3.
the answer for 10th position is 1. the answer for 8th position is 3 because : first you move to (8-4)=4th position which has value 6 which is also even (val(8)==4) so you have to move again to pos (4+6)=10 which has value 4 . then you move to pos 6 which has value 5 that is odd . 3 moves
"Can't read or parse problem descriptor"-Anybody else having this problem?
Same
what is the idea for problem D
See https://mirror.codeforces.com/blog/entry/72086?#comment-563624
For each element, remove it and then maximize the ans. For this we try to maintain two arrays(st[n] and ed[n])
st[i] will store the length of contiguous subarray starting from pos i.
ed[i] --------------------------------------------- ending at pos i.
Now if you remove the i-th element check the answer after merging left subarray and right subarray if possible to merge(left element < right element) and maximize the ans.
My solution
Better Implementation
oh ..really it was not hard one ...
thanks
There are only two situations:
So the easiest idea is just to implement this two process, and then take the longer length as the answer.
What is the logic behind problem E
I still can't figure out why this code gives a negative result for problem A.
Somebody help me finding the bug which I can't find. Here's the code 66703687
Changing your array decltype from Long[] to long[] gave AC
I just noticed something like that for my very first time. It works for values to 127. But after that from 128 it doesn't check the equality normally. For example,
1
127 127 127
This test case goes fine. But
1
128 128 128
This doesn't go fine.
Don't compare objects using ==. Use equals().
Java has a cache of numbers in range [-128, 127], that's why small tests work.
Thanx. I noticed that too. I just didn't know "Java has a cache of numbers in range [-128, 127], that's why small tests work."
Already updated the code 66762318 Now it worrks. I submitted this 4 times during contest and lost my precious 1 hour. My bad.
And if you use IDE, you can't make such mistake.
Eclipse didn't notice it!
![](/predownloaded/d6/f0/d6f0953d2b53d8cf8f5fd010b85d82ea8db1e2c6.png)
Seriously dalex you are using android studio!!
I use Long[] instead of long[] when I need to sort the array so that it sorts in guaranteed O(nlogn) time complexity. For primitive array java sometimes give O(n^2) time complexity for almost already sorted array. That gave me TLE in a previous contest problem.
Why are you so worried about time complexity when your array has length only 3.
You can not compare two object Long using != always.
You can look here for details
Can I know why I got skipped
maybe you submit two answer that get accepted?
Actuallly Igot skipped from the whole contest
idk man,that's unfortunate.
My rating should have increased by 9 according to CF Predictor but instead it decreased by 5??
when the editorial will be published...??
Is there some error in rating change? The rating predictor predicted a +102 while I got only +74. How such a huge difference?
According to predictor my rating should have increased +9 but instead I got a -5
No. You might have checked predictor before system testing.
It is showing +102 now too.
You are absolutely right. In my case, it predicted correctly. I believe there might be some issue with the predictor.
Low tests in D problem :( My submission got passed but then failed at test 39.
Автокомментарий: текст был обновлен пользователем vovuh (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by vovuh (previous revision, new revision, compare).
The editorial update at the top is looking a little weird and confusing as compared to other contests' blog.
I pinned it at the top because I thought that it would be more visible. If it's weird I'll post it as usual at the bottom. Sorry.
Yeah I think that'll be better of you post it at the bottom. Just that I have been used to looking at it at the bottom, and I believe other people too. That's why I found it weird.
Problem D is very similar to this problem.
Screencast of my testing is available
please help to find out what's wrong in my solution of problem E https://mirror.codeforces.com/contest/1272/submission/79720918