UPD: Спасибо Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву и Артему Rox Плоткину за помощь с подготовкой раунда!
UPD2: Разбор опубликован!
<almost-copy-pasted-part>
Привет! В Oct/22/2019 17:35 (Moscow time) начнётся Codeforces Round 595 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
vovuh
I wish you all good luck
hope this contest becomes my last official participation in DIV3.
I hope become pupil
Believe yourself!
You'll get it if you solved A,B and C.
try
Good luck to everyone. I hope this round will be an exciting contest without dots attacks and lots of hacks. Finally I hope the problems will be solvable and understandable.
Div-3 is Love... True Love... Pure Love...
Love Vovuh's Contest
Easy to understand hard to solve!
i Love vovuh's too
Fitness challenge: I'll do one pull up for every rating point lost and I'll do 3 pushups for every point won. Feel free to join the challenge under your conditions.
5000+ push and pull ups for vintage_Vlad_Makeev lol
qwq
orz vintage_Vlad_Makeev
I think you should take part in some contests to become master. It's more beautiful ^^
Why Div3 get so little upvotes :(
Are we just used to them?
Which problem has two subtasks? @vovuh
Look, I really don't think it is important information before a round. I prefer vovuh will spend time improving problem statements and tests.
Why do Vovuh conducts only Div.3? I don't like him.
Hi! I decided to simplify one of the problems and divided it into easy and hard versions. That's why I increased the round duration to 2:15. Don't afraid of formally too many problems in the round. You shouldn't think about easy/hard versions as about two independent problems. And good luck!
Very good idea to divide problems into parts. Sometimes, even after solving the problem, it requires additional data structures or optimizations. This way even partially correct solutions that are slower than intended get partial points.
Another idea is creating one problem with different types of tests. Solutions can first get tested on small tests, and then on bigger numbers. And if it passes small tests, contestant can get partial verdict. This has been done in several rounds, to it is possible. It is just easier to navigate this way, instead of solving 2 same problems
I will AK this contest !
HaHaHa !
aren't you HYH.AK.IOI
No, I'm not. I'm IOI_AKer-HYH!
F** you duplicate account bot that ruins genuine div 3 people's fun
Vovuh, the half-quarter!
Good luck!
I want to improve myself~
There's an expert participant in the trusted participants rankings, by the way.
That's probably because he registered to the contest before he became Expert, so he was marked as an official participant.
His rating was updated too.
Contest is over. It was a good contest.
Don't agree.
I solved 7 problems for the first time. Feel amazing >__< !!
I solved 6 but still. Which 6 did you solve?
I didn't solve D1, D2 and F. Is D1 just straight bruteforce? I didn't try because it seems like it'll be something like O(n^4) :(
I believe you can see his submissions
Oh ye. Problem E is awesome, I tried a dp-greedy method and it worked. I can't even convince myself that it is true, but complexity-wise it passed.
dp[i][elevator?(bool)] = Minimum total time to reach ith floor, with last move taking the elevator (or not, depending on the bool)
dp[1][false] = 0, dp[1][true] = c
dp[i][false] = min(dp[i — 1][false], dp[i — 1][true]) + a_(i — 1)
dp[i][true] = min(dp[i — 1][false] + c, dp[i — 1][true]) + b_(i — 1)
output *(min(dp[i]) for i in range(1, n + 1))
Can someone prove this .-.
Ummm I used Segment Tree with Lazy Propagation for D1 & D2. (Segment Tree is really useful >__<!!
But I think there will be more easy way (maybe)
I thought adding Persistent Segment Tree for D2 at first, but I'm so scared to coding it, fortunately it was solved by priority_queue.
yeah there is an easy way of solving d1 and d2 refer my sol for hint sol: 63150473
I solved 7 problems too. I wish this contest is rated.
I hope we can all be Blue-coder Kkkk
Yes.I'm looking forward to rating update.
Can somebody explain test case 2 in F?
Thanks
How to solve C2 ?
It's just ternary numeral system.
My solution:
precalculate all values 3^n (0..38 powers), it's 100..000 preseentation of number
next I check first X that 3^0 + 3^1 + ... + 3^X (presentation of 111..11) >= n, if yes subtract from n 3^X, and add to result same number
do while n > 0
What about n = 10^18? In the first test the answer is 1350851717672992089, but 3^38 > 10^18 and less than test's answer
You are correct (10^18 — 3^38) < 0 and loop stopped.
But first I compare with (3^39-1) and subtract (3^(39-1))
upd: sorry, not 3^X-1, but 3^0+3^1+..+3^X and if this value greater or equals than n I subtract 3^X from n and add to result
How to solve D2?
I solved it using line sweep algorithm. Iterate through the points [1,2e5]. Keep a set that includes current line segments. Whenever you find a condition where the number of line segments exceeds k in the current set, remove the line segments which have higher ending point.
wrong code
What was test case 14 of D1?
Also, how where you supposed to solve D2? I thought using a BinaryIndexedTree, but I wasn't sure how to implement.
What is Test 11 for Problem E?
Isn't Meet in the Middle expected solution for C2. My solution got TLE on test 7
while (q--) {
} isn't a good idea when q can be 10^18
N can be 10^18 not Q. So it's not a bad idea.
yea my bad
I have greedy solution with prefix sums
This 63197085?
This 63198485
Actually both are same :)
Hey !
This is not a Meet In The Middle problem. In fact the intended solution doesn’t require bitmasks at all.
Here’s what should be done
Yeah! I did this :)
I solved only 2 problems. Will my rating will increase or decrease? The problems were easy but I couldn't cope up with the constraints leading TLE
You can use the CF-Predictor browser extension
How to solve F?
dp on tree
dp[i][j] is the max sum can be obtained from the subtree of vertex i
with the nearest picked vertex from this subtree is at distance j from vertex i
I think this round is easier usual Div 3 round.
Any Penalties on Unsuccessful Hacking Attempts?
Don't know because there was no points table shown like other Div.1 and Div.2 contests. Even which problem contains how many points is also unknown.
There is no any fixed scoring distribution in Div3 rounds.
no
The moment I realized that the comparator used by me is wrong in D1/D2 after printing all the values for an hour...........
Anyone tell me why this code gives TLE? 63189145
this is fixed code. 63190824 when you call functions, vector<vector > v would be copy. it makes tle.
What's wrong with this solution for F — dp[node][level] = answer for subtree rooted at 'node' such that among all selected nodes the smallest depth is at 'level'? This recieved WA-3
After seeing constraint I thought greedy won't work for C2 so wasted one hour to implement Bit Mask+ Meet in the middle.Lesson learned. -_-
My Meet in the Middle got TLE on test 7
Can you describe better, what was your Idea behind meet in the middle algorithm?
Divide the powers of three into two vectors. Then each vector contains all possible numbers which contain distinct powers of three. Iterate through the first vector and binary search on the second vector for number >= (n — number in first vector ).
Don't divide power of three into two vectors of almost equal size, try keeping powers from 0-15 in first one, and 16-38 in second one (i.e one you use in binary search).
I tried that too but no luck. You can check my recent submissions I tried all feasible combinations.
Check my solution. I have also used meet in the middle technique. The difference is I am not iterating through the whole set while answering a query. You can only check certain cases and get the correct answer.
https://codeforces.net/contest/1249/submission/63178411
Submission with (16, 23) sizes of subsets.
My solution for $$$F$$$:
Root the tree at node $$$1$$$. Let $$$dp[i][j]$$$ be the maximum subset weight for the sub-tree rooted at node $$$i$$$ if the nearest node in the subset to $$$i$$$ is at distance $$$j$$$ from it. Let $$$mxdp[i][j]$$$ be $$$max(dp[i][k])$$$ for $$$k$$$ from $$$j$$$ to $$$n$$$.
How to fill $$$dp$$$?
$$$dp[i][0]=a[i]+\sum_{c}mxdp[c][k]$$$ where $$$c$$$ is every child of $$$i$$$.
$$$dp[i][j]$$$ (for $$$j$$$ from $$$1$$$ to $$$n$$$) $$$=max(dp[c_1][j-1]+\sum_{c_2!=c_1}mxdp[c_2][max(k-j,j-1)])$$$ where $$$c_1$$$ is every child of $$$i$$$, and $$$c_2$$$ is every other child of $$$i$$$.
The answer is $$$mxdp[1][0]$$$.
Shouldn't the answer be mxdp[1][0]?
Sorry, it is a typo. fixed now.
I think it should be $$$dp[i][0] = a[i] + \sum_c mxdp[c][k]$$$
Yes, another typo. Fixed.
In D why remove segments from longest to shortest length is wrong?
Imagine three segments [1, 1000] [1001, 2000] and [1000, 1001] and k = 1. There are two points that have k = 2 : 1000 and 1001. If you remove longest segments, then you will need to remove both of the big ones. In another case, you can just remove the third one and m = 1
thank you now I understand
Сложные у вас задачи в Div 3, несколько лет назад такие в Div 2 давали. F точно лишняя, да и D и E далеко не подарок, если за новичка катать. Может, Div 4 надо делать?
Толсто, чел. Между делом, я помню, что ты как-то хотел сделать свой "образцовый" Div. 3, чтобы показать этим саратовцам, как их нужно делать правильно. И что-то я его до сих пор не вижу.
Что толстого-то? Эти соревнования позиционируются как соревнования для новичков, а чтобы решать D и E с сегодняшнего, надо не меньше года заниматься.
Толсто то, что ты не видишь корреляции между количествами AC в Div. 2 и Div. 3. Сколько ни занимался, почти во всех Div. 2 раундах закрывалось несколько официальных участников и около сотни-двух решало все задачи, кроме одной. Можешь посмотреть по ранклисту, что и в этом, и во многих других Div. 3 раундах именно так и есть. Неужели ты предлагаешь сделать Div. 3 такими, какими они были в самом начале, где закрывалось 600+ человек и про них начали говорить "о, очередной Div. 3, ну это изи 1600+". В чем смысл этой затеи и в чем проблема со сложностью сейчас?
Мне кажется, что не круто, когда новичок впервые заходит в Div 3 и решает в нем 1 из 6.
Отвечая на предыдущий коммент, я не хотел сделать образцовый Div 3. Его уже сделали, смотри: Codeforces Round 481 (Div. 3)
А если человек решает в "изи 1600+" раунде все задачи, почему бы и не дать ему эти 1600?
Ладно, возможно, у меня уже едет крыша, но я почему-то помню предложение то ли от тебя, то ли от кого-то другого, что "я сделаю нормальный Div. 3 и залью его в тренировки". Но это не важно.
Если новичок приходит на раунд и решает одну из шести, учитывая, что задача B1 из сегодняшнего раунда — это задача "просто напиши хоть как-нибудь то, что сказано в условии", то, может быть, ему стоит задуматься, правда ли он знает хотя бы основные конструкции языка? Потому что единственное, что нужно было, чтобы сдать B1 — это знать циклы и массивы. Тогда, возможно, это должно мотивировать становиться лучше, чтобы решать хотя бы те задачи, в которых просят просто написать.
Видимо, ты хочешь превратить сайт с олимпиадными задачами по программированию (часть сайта) в курс "научись писать хоть какой-то код"? Какой в этом смысл?
И чем раунд, на котором закрывается 200 человек, а еще 300 решают все, кроме одной, так хорош, когда он почти никак (кроме скорости печатания) не может отделить топ-500 участников друг от друга?
Is there anyone else, who used meet in the middle in C2. my solution
how to solve B2?
use dfs, to travel continuously until u get end point of cycle.then update all the travelled value to max distance you have travelled until now.see my code.submission
You could use disjoint sets too... Just put i and arr[i] in same set (union) and like size find size of each set, the answer is same for all the elements in the same set, ie, size of the set.
i was getting wrong answer using mn_diff=LONG_MAX, is it wrong to use LONG_MAX for std::min function in c++, but also it gave correct answer on my compiler.
LONG_MAX gives you a "long long" value, but you are storing it in an "int".
no when i used mn_diff=1e18 it gives AC
1e18 is different that LONG_MAX. Both will give you different values, and if you don't store that values in a "long long", LONG_MAX can give you a negative value and 1e18 can give you a positive value (depends on the compiler).
Sorry for my poor english xd
ex:Codeforces submission
Ideone submission
but i never used int, u could see above its long long.
Sorry, I didn't see the "ll" :c Your code on my compiler prints the correct answer too.
UPDATE :: never use LONG_MAX on codeforces as LONG_MAX is same as INT_MAX on Windows, and codeforces uses 32 bit windows, so always use LLONG_MAX it is universal (2^63-1).
For problem E, could anybody tell me why PyPy 2 TLEs but PyPy 3 ACs?
because Python 3 is much faster than Python 2 (especially more recent versions)
Python 3 is still slower than Python 2 on most counts, especially in competitive programming.
It seems like it's only PyPy 2 that's slow. Even Python 2 ACs.
Just added my fast io got accepted in PYPY2 . Do check my submission
https://codeforces.net/contest/1249/submission/63196194
Had it helped you ?
Thanks for making my submission work. I've never seen output buffering in Python like this before, will have to look more into it.
My approach for problem D1 is keep removing the segments intersecting with maximum number of bad points .Is this approach correct ? My submission is giving wrong answer though My Submission
I got WA on 9. Switched to iterate from left to right on bad points and keep removing segment with largest end point, and that passed.
Your approach is also nice.Still wondering what is wrong with our first approach .
I found out whats wrong.
Take the following case
5 1
1 2
2 5
3 10
7 14
14 15
Here if we try deleting segments with most bad points, we will first delete 3 10, then 2 5, then 7 14. But the correct approach is to delete 2 5, and 7 14.
You are right . Thanks !
Hack case for B?
The problem-set contained better stories than all of my films combined.
In problem C2
This is my AC Code63196491what is wrong with this line my[i] = (int)pow(3LL,i) ;
Overflow, my[i] can be greater than INT_MAX
But I have defined int to long long
Oh sorry, I saw it later, below comment is correct
pow returns double, which can't represent all values of a long long (think about it: both are 64 bit types, therefore pigeonhole principle etc etc)
I could suggest you one thing, if I may.... Don't use inbuilt pow function, it's very deceptive sometimes..... Just to be on the safe side, you could make your own pow function using fast exponentiation....
pow(x)returnsdouble, which is not enough for1e18. Try usingpowl(x), which returnslong doubleinstead.P.S. Both
powandpowlare inaccurate, try to avoid using themthanks for this amazing contest:)
thanks for this amazing contest :)
Sorry for my bad english, but the user named AHR9N has cheated, he asked me for the code of the problem B2, but I did not send. I think he needs to be severely punished
Oh,I can't get problem c2,problem c2 and problem e by using m2.codeforces in this contest. It told me that the statement is available.
Can anyone give me the solution of Problem B2 using DSU?
refer my submission: https://codeforces.net/contest/1249/submission/63209409
In question https://codeforces.net/contest/1249/problem/A A. Yet Another Dividing into Teams from equation it means that difference should not be 1. Statement says difference should be strictly greater than 1. And test cases are aiming just for difference not equal to 1. There is a bit ambiguity . As for input 1 1 1 1 1 1 Answer should be 5. In test cases answer is either 1 or 2.
All students have distinct programming skills!
The second line of the query contains n integers $$$a_1,a_2,…,a_n$$$ ($$$1≤a_i≤100$$$, all $$$a_i$$$ are distinct), where $$$a_i$$$ is the programming skill of the i-th student.
Is the round unrated? Why the ratings are not updated ?
Cause you are not rated in this round. You have to participate at least 3 contest in div2.
and your solution was skipped-- probably you have break any Terms of agreement of codeforces.
Problem F is basically the same as BOI 2017 day 2 "Cat in a tree"
Edit: I was mistaken, please ignore.
There's a typo in problem F:
"Output
Print one integer — the maximum total weight of the subset in which all pairs of vertices have distance more than $$$k$$$."
I think you mean "distance no more than $$$k$$$"?
No, distance between any pair of selected vertices should be greater than
kOh right, I misread the prose in the problem description and thought there was a contradiction.
If I modify problem A to..like find minimum number of teams you can form if no two students i and j such that |Ai-Aj|<=k may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than k).
So if N be the no of students then I can solve it in O(NlogN + Nk^2). is there ant faster approach if any one can suggest???
Maintain a sorted array. Pick the first element(lets say a), then find the upper bound of a+k. Keep on doing the same thing for this new element until you reach end of array and also maintain the elements which have been allocated a team. Pick the next element in the sorted array which has not been allocated a team yet and repeat the above steps and increment the number of teams. This approach should be O(NlogN).
No worst case complexity of your idea is O(N^2) Consider the case of N consecutive numbers with k=N;
How?
just apply your idea and see... pick your a(first element of sorted array) in search of a+k (i.e. a+N here) you will traverse the whole array(end of array) but you will not find it.. Note1 you have picked just 1 element in 1 traversal do same for 2nd, 3rd and so on... so N(N+1)/2... O(N^2)complexity……. also Note2 you can't say here for this very case to use binary search(however here may work) bcz in general solution binary search will not work.
I won't traverse the whole array. I would just binary search and why would it not work in general?
not work means complexity will become even worst bcz at every such a+k you need to do binary search prev=a; curr=a+k; next a+k+k;..... so on and every time cost is logarithmic time. Also there might be case that a+k doesnot exist but a+k+2 or a+k+5 exist here these will be included in the same partition but then how you will handle those cases using binary search.... Just think once what is your complete idea and check the complexity... once done I will be thankful and love to know that.
I think Brute_Forced approach is O(NlogN)
Why have the rating changes been temporarily rolled back ?
https://codeforces.net/blog/entry/70793
Oh.. ! Great that it's being taken so seriously !
Stop naming test cases as "queries", ffs.
This is not the first time you are saying this. But I don't think it makes any difference. It is okay until and unless it is not creating any confusion in the problem statement. Isn't it?
And it does create confusion because queries usually mean something else.
So when on earth can our rating be back?
It's back for me.
I got plagiarism mail for the following solution coincided https://codeforces.net/contest/1249/submission/63187125 with another guy solution. However my first accepted solution for this problem was https://codeforces.net/contest/1249/submission/63184980. So the thing of plagiarism, I guess is completely irrelevant.
Don't use IDEOne for coding.
Is there any way to restore my credits for this round, I was unaware regarding Ideone thing.
Try appealing to the problemsetters and the organizers. I tried a few contests back, didn't help. Now I only use my personal IDE.
Is it ok, what a few participants 1600+ rating got it updated after contest?
i try to solve D1 by using activity selection problem but it gives me WA on test case 14.
so i would do activity selection for K times and of course for each activity selection it will gives you as many as segments which not intersect with each other.
if you do it for K times then you will get points which covered at most K times, i couldn't think the corner case for my solution.
Can someone please check my F code. Its failing on the 38th case. https://codeforces.net/contest/1249/submission/73195435