Привет! Надеюсь, вы скучали по мне :) Насколько можно судить по словам некоторых людей, из-за скопированного анонса этот раунд не будет интересным. Но правда в том, что сейчас я очень болен и я очень рад, что вообще смог приготовить этот раунд. Надеюсь, он вам понравится. Удачи всем!
<copy-pasted-part>
Привет! В 31.03.2019 17:05 (Московское время) начнётся Codeforces Round 550 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров п о взломам.
</copy-pasted-part>
UPD: Разбор опубликован!
UPD2:
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | WNSGB | 7 | 206 |
| 2 | kaixinqi | 7 | 335 |
| 3 | _sys | 6 | 188 |
| 4 | Moririn2528 | 6 | 206 |
| 5 | CarusoX | 6 | 212 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | wanderer163 | 21 |
| 2 | tokitsukaze | 14 |
| 3 | Fe4RLess | 6 |
| 4 | smit.mangukiya | 4 |
| 5 | chandak_vikas | 4 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | anurag918273 | 0:02 |
| B | probIem-solving | 0:07 |
| C | Shuba_realniy_krasav4ik | 0:05 |
| D | vnquynh_hac_am | 0:12 |
| E | probIem-solving | 0:28 |
| F | lxr_love_yxh | 0:16 |
| G | IZONE | 0:20 |
Скорейшего выздоровления, vovuh!
Привет! В воскресенье, 31 марта 2019 г. в 16:05UTC+2 начнётся Codeforces Beta Round #86 (Div. 2 Only) — очередной Codeforces раунд для третьего дивизиона.
Даже скопированную часть мы читаем!)
Забавно, что это только в одном месте из четырех (2 в английской версии, 2 в русской). Забыл одну четверку в номере соревнования :) Спасибо большое, что заметили! Исправлено
It hardly matters if you are sick.
Your rounds are always good enough vovuh
Выздораливайте поскорее, ваши div3 контесты делают меня счастливее =))
what is mean by copy pasted round ????
Sometimes some members of community says that, the announcement of div3 round is always identical. vovuh just pointing out this by saying "copy-pasted announcement"
Div 3's are always a great way to boost up the ratings.
Будем надеяться, что задачки (для людей с рейтингом меньше 1600) будут интересными!) Спасибо большое vovuh, и желаю выздоровления!
Could you make the contest late 1 or 2 Hours cause I Have an exam And I want enter the contest I'm travelling so i Can't get in time I Would be grateful. Thank you :) vovuh
Better try virtual. Community love Codeforces' professionalism.
I want to enter it life and also get good rate so i'm asking that if he could make it late only for 1 or 2 hours so that i can get in time thanks for replying me :)
There are thousands people who want to take part in the contests, all over the world. There will never be a time that is good for everybody but there is another contest tomorrow and more contests coming up in the few weeks. There are lots of contests.
A time that is good for you will be in the middle of the night for somebody else. A time that is good for someone else will be a bad time for you. This is because this planet has more than one timezone. It is not possible for all the contests to be at a good time for you.
In the meantime, why don't you try practice problems so that you will get a better rating in the next contest that is a good time for you? There are some ladders sorted by difficulty to help you get stronger. That's what I'm doing.
Thank you for your time but to get straight I'm practcing so hard and i know what are you talking about I Respect you all geys and hope haigh rating for you all ❤
Good luck! I hope there will be a contest at a good time for you soon, and wish you a high rating too.
Thank you ❤❤ I will try my best to finsh the exam quickly so that i can participat in this contest with you all :) i wish to get in time .
I hope you can finish the exam quickly to enjoy the contest
all times are good for middle-east .. hahahah
I hope this round will focus on your problem solving skills rather than speed :) Really love your contests Vovuh :)
Wanna refresh your algo paradigms? Go for a Vovuh round :)
Will there be any interactive problem?
Bug happened! Hope it will be solved soon
refresh,because I haven't seen it on my computer
Refreshed but still visible in my screen
Can you tell us about the exactly number of problems? Don,2019-03-31't tell me 6 or 7 or 8.
7 problems this time. Hope this information will help you, but I don't know, how it can help.
I wish you can tell us the number of problems in the round like other rounds.
this is a mind game bro
I am outside and may not participate in today's contest or can't join in time. Though the contest is not rated for me, still I am hurt and that's the love for contest not for rating.
And if this was a rated round for me I must postpone my work to participate in the contest, that's the love for codeforces rating.
My CF account automatically logs out sometimes. Anyone else having this problem? Someone might miss a last minute submission during contest because of it.
Yeah was facing the same issue, to deal with it I had clicked on "remember me for a month" during last login, and now its working fine for me .
What is the testcase # 8 in D ??????
Maybe something of this form:
5
1 2 5 2 3
What's the answer for it, 3?
YES the answer is 3. 1 1 2 2 3 2 2 5 4
Yes, the answer is 3
2 3 4
1 1 2
2 5 4
How to solve E and F?
F looks like bipartite
F:
For every node, either all edges can be directed towards it or directed away from it. So, set the orientation of edges on any random node say X, which will also set the orientation for all other nodes as the graph is connected. Check if the orientation is consistent or not. If not, change the orientation of X and check again. If not, no orientation of edges is possible.
WAT. I thought the solution is always possible and couldn't figure out how to do it. Jokes on me for not reading it properly.
There is no need to change the orientation after it is found that it is not consistent in the first go.
Right. It's unnecessary, didn't strike me during the contest.
E: treat s and t as base-26 integer, then ans = s + (t — s) / 2
You mean s+(t-s)/2
Just (s+t)/2 will also work
How is it possible to represent it as base-26 int when the strings can be as long as 2*10^5 ?
store digits in array.
F: Here is a pretty simple solution. Use dfs to color every node with white or black so that no two adjacent vertexes have the same color. Then iterate each edge to see whether the color of the vertex on that edge is the same. 52118506
What's the logic for D. I thought of max repeating element as the no. and got the wrong answer at TC: 8
Notice that the function basically makes 2 adjacent numbers equal to one of them. Then, find the most frequent element and make all the numbers in the array equal to this number.
How to solve G?
Maintain two sorted arrays. For a new element $$$x$$$, if it can be appended to only one of the arrays, do it. If it can be appended to neither, the answer is no. If it can be appended to both, check the next element $$$y$$$, if $$$y \gt x$$$, then append $$$x$$$ to the increasing one, otherwise append $$$x$$$ to the decreasing one. One can prove this is always optimal.
could you prove it!?
If $$$y \gt x$$$ and instead we append $$$x$$$ to the decreasing one, we can only then append $$$y$$$ to the increasing one, which is obviously worse than appending $$$x$$$ to the increasing one and $$$y$$$ to the decreasing one. The case when $$$y\leq x$$$ can be proved in a similar manner.
I am also from Nanjing（秦淮区）
sir, can u provide the code... ur idea is different and easy to understand but I can't implement it...plz!!!! Thanks..
https://codeforces.me/contest/1144/submission/96759936
Thanks.
Another solution using LIS. Find the LIS and the rest of numbers should be Decreasing, if not we can prove that you only need to swap one number from LIS with one of the rest and there are a few valid cases for swap. 52133834
Why is it possible with only one swap? any intuition?
UPD: So basically that I meant in the previous revision is that exists one LONGEST Increasing Subsecuence such that after eliminating it the rest of elements are decreasing or not exists any solution.
I will try to make the explanation more clear:
Let $$$DS$$$ be the rest of the elements that are not in some $$$LIS$$$.
If not:
You can't transfer two or more elements from $$$LIS$$$ to $$$DS$$$ (because you put a increasing subsecuence in the $$$DS$$$)
So at most one element from $$$LIS$$$ should be changed to $$$DS$$$:
The elements that you need to swap are (it's easy to see that if you not swap these elements, then the solution still invalid):
How is 1. Invalid??we can add element from lis to ds.
If DS is invalid (not is a decreasing subsecuence) and you add one element to this, then DS still invalid because you doesn't remove the elements that maked it invalid
A contest of applying sorting algorithm :3
To be honest, this was the most balanced problem set, in recent contests. Even though yesterday's one was also quite balanced, this one was a perfect set.
I code in C++ and I was having a little trouble in Problem A. When I tested my code on my own compiler (I use the GNU GCC Compiler on CodeBlocks) for the given test case, I obtained the correct answer. However, when I submitted the same using the G++14 compiler on CF, the judgement showed a wrong answer for test 1.
After the contest had finished, I saw that the answer printed by the CF compiler was different from that printed by the CodeBlocks compiler. Since then I have tried all C++ compilers available on CF and none of them gave me the desired answer. Does anyone have any suggestions on how I can fix this problem?
Oh, ok. Thanks a lot!
Your code is currently a mess, especially the I/O. Just learn how to do it in C++ instead of mixing C I/O with C++ I/O. Here is an example of your code rewritten in C++. Also
Never use gets(). The problem is that gets can write outside the allocated memory so you should never use it. "The function provides no means to prevent buffer overflow of the destination array, given sufficiently long input string. std::gets was deprecated in C++11 and removed from C++14." link
Btw I suspect that the actual reason why your code fails is because fflush(stdin). Depending on the compiler it can be undefined behavior. If you switch fflush(stdin) with cin.ignore() everything does work.
Cool, got it. Thanks for the help!
Really great contest! Enjoyed the problems a lot.
Can u please tell the mistake in logic for my code: https://codeforces.me/contest/1144/submission/52126510
The number of changes you make does not matches with the jury answer. So clearly the line "pn(n- max)" is faulty. I copied some section of your code to see if you are calculating "max" correctly, and my code passed. I don't know anything about java. So best i could advice is, use dictionary or frequency array to find the most frequent element.
There is not a mistake in logic, if you change:
For:
It works.
Can u please tell why == is giving problem because its a char array so it must work.
== compares references, not the values
Check this
Can u please teel the mistake in logig for my code: 52106504? Failed on test case 7.
How to solve F?
Just check if the graph can be Bi-colored, if is not possbile then print 'NO' otherwise for each edge assign '1' or '0' depending on how you have colored the nodes 'u' and 'v'.
Когда будет опубликован разбор ?
I forgot to put abs around (odd.size() — even.size()) in problem B. Go ahead challenge it. https://codeforces.me/contest/1144/submission/52089891.
It will pass the sys test.
Underflow is a wonderful thing.
Could somebody tell me what is traversed edge in problem F, I had think some time but fail to work out it, I just want to know what’s the traversed edge mean,Thanks
I don't know how to hack my second solution of problem G.52114369
My first solution is to find the longest increasing subsequence and check if the remaining numbers satisfy the decrement. Or find the longest decreasing subsequence and check if the remaining numbers satisfy the increment. If not, it is No.
The solution was hacked by test 30:
6
1 2 100 3 101 4
Because [1 2 3 4] was found when looking for the longest increasing subsequence. When looking for the longest decreasing subsequence, I found [101 4].
Then when I look for the longest incrementing subsequence, after the penultimate number, I find the largest number and replace the last one with it. This finds [1 2 3 101], which just passed test 30. In the same way, when looking for the longest declining subsequence,find the smallest number and replace.
This is my second solution.I think there are still some mistakes,but I don't know how to hack it.
If it is correct，can someone tell me how to prove it?
Is there any way to boost this python solution for E? I think the time complexity is good enough, just the problem is in the performance of Python itself.
In no way is that a problem with Python. What you've written there is essentially a $$$O(n^2)$$$ algorithm. Every time you mult by 26 or divide by 26 it has to do the calculation on the entire integer. As the integer is already $$$O(n)$$$ big every operation takes $$$O(n)$$$.
There are ways to get around this. Python's
int(str,base)allows you to read a number in the base 26 in $$$O(n)$$$. But unfortunately there isn't any built in way to print a large integer in base 26 in $$$O(n)$$$ as far as I know.I see, thank you.
for problem g is this correct approach? let say i have two array X(increasing),Y(decreasing) and A is Merge(X,Y). Find the longest increasing sequence of A this sequence will contain X and atmost one element of Y and after removing that element from Y Y will still remain decreasing.
The solution is correct in the case where the length of $$$LIS$$$ of $$$A$$$ is equal to (length of $$$X + 1$$$). The reason for this is, as you said, after removing one element from $$$Y$$$, it still remains decreasing. But, when $$$LIS$$$ of $$$A$$$ has length equal to length of $$$X$$$, then the remainder sequence $$$R$$$ (after removing $$$LIS$$$) may not be decreasing. Consider the case where $$$Y = [4, 3, 2]$$$, $$$X = [2, 3, 4, 5]$$$, $$$A = [4, 2, 3, 2, 3, 4, 5]$$$. $$$LIS = [2, 3, 4, 5]$$$, $$$R = [4, 2 ,3]$$$
hello, in the statement of problem 'D', I didn't understand this line:: "Note that after each operation each element of the current array should not exceed 10^18 by absolute value."
Could you please elaborate it??
Is is possible to have multiple solution for problem F..
help please ?