<copy-pasted-part>
Привет! В 23.01.2019 17:35 (Московское время) начнётся Codeforces Round 535 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</copy-pasted-part>
UPD: Я хочу поблагодарить тестеров ismagilov.code, budalnik, Arpa, filippos, eddy1021 за огромную помощь в подготовке раунда!
UDP2: Я не уверен по поводу G63-AMG, поэтому я включил в таблицу топ-6 вместо топ-5. Также я не уверен, что некоторые взломщики не читерили, поэтому простите меня, если моя информация неверна.
UPD3: Разбор опубликован!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | b31quocbao | 7 | 358 |
| 2 | GZY_AK_IOI | 7 | 455 |
| 3(?) | G63-AMG | 6 | 101 |
| 4(3?) | pushkar12 | 6 | 216 |
| 5(4?) | _DarkDawn_ | 6 | 226 |
| 6(5?) | Amooo | 6 | 229 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | _bacali | 181:-49 |
| 2 | Chiakisa | 55:-8 |
| 3 | CNH_NHI | 10:-1 |
| 4 | Cylinder | 9 |
| 5 | CNH_NSIS | 8 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | spacewanker | 0:01 |
| B | mpstxdy | 0:03 |
| C | G63-AMG | 0:06 |
| D | arpit040199 | 0:06 |
| E1 | G63-AMG | 0:11 |
| E2 | TsingTaoDaTieWang2 | 0:16 |
| F | Zhao-L | 0:20 |
I hope its not like..
DIV2<DIV3<DIV1
Maybe a Div3 = Div1 + Div2 ....
More like Div3=Div2-Div1...
Let's Increase it's value a little Div3 = (Div2 — Div1) * 1.5; ;)
i hope it won't have any useless and pointless math involved...
also may i ask will it rate my rating?
The contest will be rated for you as long as you're under 1600 (now you're 1599). If you took part in today's contest and it will raise your rating — the next Div. 3 won't be rated for you. Half of your comments are complains about maths :D I don't agree with your statement that maths has nothing to do with programming. It has a lot, especially with competitive one. All of the algorithms (e.g. graph theory) come from mathematics. Try to deal with it if you want to have fun from Codeforces.
what are you talking about i am expert
I wrote my comment before the contest results appeared and you was 1599. Now you're an expert, right. Congratulations!
thanks i feel really great now
Round by vovuh !! Always exciting to participate!
Wish a lot of AC <3
Div3 contest is like a gift for contestants below 1600.
Announcement of Codeforces Round #299 (Div. 2)?
Fixed now, I think :)
Perfect announcement doesn't exi...
[Off Topic] I am trying to practice on my hacking skills for the next contests. Is there any good blog post about how to approach hacking effectively? Some sort of guidelines/best practices on how to hack solutions.
I searched but couldn't find any
Step 1 : study for exam
Step 2 : participate in Cf round
Step 3 : loose 100 rating points because your mind was tired from studying
Step 4 : fail the exam because your mind became even more tired after trying to solve problems
problems are easy in Div3, today I'll be in TOP 20
Is div3 friendly to new people?
Yes, it's without a doubt the best contest new people can choose. But it doesn't mean it will be easy. If you have no or little experience in competitive programming, doing 2 or 3 problems will be a quite good result. Good luck.
Is vovuh nephew of Mike Mirzayanov? Why does he take every single Div3 Round?
Does it mean that participants with 1600 higher rating taking part in Div.3 would not be rated ?
Exactly. We can take part just for fun.
Oh that's amazing! Thanks a lot!
Div3's are always surprising!
Another div 3 round, which is equal to div 2. In any case, thanks for the prepared problems. Good luck, have a fun. Take care of your feet
You also take care <3
Yet again disappointed by weak pretests >:(
Sorry, I tried to make strong tests in almost all problems and just forgot about you! The only tests among your solutions are in the problem B with answers 69 and 42 :(
Bro just do it like a normal CF Round... please drop that 12-hour open hack feature.
All of your solutions are hacked.Because "if(n==69)return 0;".
swap(C, D)
C && D giving TLE in java wow in-spite being O(N) =_=
Changing the string to char array gives AC WOW! okay -
Stringobjects are immutable, which meansans+='B'requires creating a brand newStringobject and copy all characters, then append 'B' to it.how to solve E2
i think this solution is right though i couldn't find an apropriate implementation that fit in time and memory limit for it...
first you have to prove that the answer is when you choose the segments that doesnt intersect whith the maximum element.now you can fix the element that shoud be the maximum and apply all the segments that doesn't intersect with this element and get the minimum,this can be done using segment tree
I did that in E1 , assumed that each element is a maximum and chose the segments that don't affect that number
However I don't know how to do it in E2 time limit
how can it be done using segment tree ?
you have to use minimum segment tree.
but for the precise implementation,i couldn't get the accept for the problem,i fix the time limit problem by just a little spitting on my code,but that one agian couldn't fit in memory
My implementation with segment tree : 48837273
yes,you used the sweep line trick that i didn't and because of that i couldn't get the accepted
Segment Tree is to slow to fit tle
We do not need a segment tree here, check it out for my solution: https://codeforces.net/contest/1108/submission/48881765
Let min is the index of minimum in the array b, and in a we try to minimize a[i] as much as possible. So where to choose the maximum index: max ?
First thing we observe is that we should not decrease the max index in the array a. Proof : if we choose the range that contains both max and min then it makes sense not to choose it, else if we choose the range that contains only max, not min then it is wiser not to choose them.
So if we choose a set(possibly empty) of given ranges that cover the min, we shold choose the max from the left of the array a: either from the prefix [1..l] or the suffix [r+1...n] since the set of ranges we choose all have at least one point in common, which means they form a big, continuous range [l..r].
Consider that the maximum choose from the suffix. Assume that ranges are sorted according to the end bound.
So for each min = 1..n, we choose the set of ranges in the way that expand to the end of the array. Suppose the set we are considering has X ranges and cover to the r-th element of a, then we take the maximum of our current answer and:
maxright[r+1] — (a[min] — X).
Same kindof process for choosing max from the prefix.
Remember to check the corner case of empty set.
Testcase 26 Problem F?
4 4
1 3 1
1 4 100
1 2 100
2 3 1
In my opinion answer should be 0
Even i did not manage to find how to solve
You can see my submission. You can understand easily from the code itself. What I have done is processed the edges after sorting by weight and did a simple DSU.
I was trying to see the components in a single iteration. Thanks for the reply :)
https://codeforces.net/contest/1108/submission/48833560 i got WA on test 26 any help or test case
Try this
6 7
1 2 9
2 3 9
1 3 9
3 4 1
4 6 2
4 5 2
5 6 9
answer would be 1 i think
you are getting 0
Лол, серьезно? Жадный алгоритм работает в D?
А почему нет?
Я, в принципе, не спорю. Просто, немного неожиданно видеть подобное решение на задачу D, пусть даже и div3.
Need help on C. I don't know what I did wrong.
https://codeforces.net/contest/1108/submission/48833951
BTW any recommendation for E1,E2 and F???
//swap(D,C). and maybe even swap (D,B). I lost 50 mins on C and just read D and like "Uh what???"
Simply try "RGBRGB..." "RBG" "BRG" "BGR" "GRB" "GBR" and find the minimum among these choices.
So it's my first time to see a problem which has two types in Codeforces.
(And I haven't solved it/them.:D It should be an easy problem though..)
I don't know about you guys but 12-hour phase of open hacks is certanily the only thing I don't like about this Div.3 contest, why don't you leave that feature for Educational Rounds only ??? You can downvote me, I don't care about that, but I have to say it... is painful.
But this is really helpful to improve your skills.
I think that Codeforces is a site to help you improve your skills, ratings is not the only thing right?
Ok, but regular CF rounds allow you to hack as well, my opinion is that it would be better to leave the 12-hour phase of open hacks for Educational Rounds only and let this div. 3 rounds more like the regular div. 2 / div. 1 rounds. Again is just my opinion. Happy codings to all :P
Can somebody tell me what's wrong with this code on problem E2?
My submission
https://codeforces.net/contest/1108/submission/48801874 i find new thing one of the guy is submitting right solution expect for case n == 69 and he is hacking with another account . please report this user and please dont allow this to happen in future the user is @problem_destroyer420
I did try to solve the problem E1 using DP. but I did not solve the number of segment T^T...
I did try to solve the problem E1 using DP. but I did not solve the number of segment T^T...
Am I the only one who felt today's Div3 first 3 problems are more difficult than yesterdays Div2 first 3 problems?
I would say that the diffucult is about the same.
How to solve E2?
For every index of the array assume that it is not affected by any of the M updates. Apply all the other updates which don't affect that index and calculate the answer i.e. max — min.
how to do that in E2 time limit
Apply all the queries to the given array initially. Now you can do a sweepline on the updates based on which index they appear and which index they disappear. Submission
You can use sweep line technique. Iterate i from 1 to n, for each i subtract all segments [i, j], then calculate. After calculating, add all segment [j, i] so that next i won't use old segments.
Check all indices in increasing order. For each index, check all the segments and find if the index is the start of the segment. If it is, then subtract 1 from all elements in the segment, and re-calculate min and max and update the answer. Check all the segments again and see if the index is the end of the segment. If it is, then add 1 to all elements in the segment.
Can you explain in some detail why it works? Is it because you are trying to depress the value of the ith element as much as possible, and the highest element e such that e-a[i] gives the max answer can either be a part of that segment or not, if it is not a part you gain one, if it is you dont lose anything since both get devalued by 1? Please correct me if I am thinking of something wrong
Basic principle is to make each element as small as possible. So for each element, you're going to subtract 1 from all segments including that element.
If you check indices in increasing order, the only segments you need to check are the ones you enter or leave. This guarantees that when check an index, all segments including that element has already subtracted while others are not.
Yes, exactly.
Yeah, I solved E1 with that observation. But that gets TL for E2.
no you didn't, stop lying!
contest was so easy :D
Anyone tell me what happened with my solution. I just change string color = "GRB" code (WA on test 4) to color ="BGR" code and got AC?
next_permutation needs your passed array to be in sorted order, RGB is not sorted, but BGR is
what's the dp solution for probD?
State:
dp(index, prev_letter)Transition:
Please check my solution for more clearity.
can anyone tell why my code https://codeforces.net/contest/1108/submission/48851718 for problem https://codeforces.net/contest/1108/problem/E1 shows wrong answer on online ide while it give correct answer in sublime text??
Your int x in line 63 is uninitialized in those min/max functions.
OK Thanks
What is the intended sol in E2? Segment tree with lazy prop didn't pass for me. (tle #15)
UPD — AC. Missed to apply sweep line on updates.
Someone can explain me why my position in standings changes after refreshing the page? Which of these is the official one?
Hello guys :)
cheaters: same code
https://codeforces.net/contest/1108/submission/48814895
-> https://codeforces.net/contest/1108/submission/48841216
One code was sent after the end of contest.
Is notice helpful? because two of my friends are always cheating. Would anyone ban them or something?
sorry for bad English.
one for example
http://codeforces.net/contest/1097/submission/47921374
and
http://codeforces.net/contest/1097/submission/47922209
Can anybody tell me what is wrong with my E?
I tried greedy + segtree.
Like if you want to have ai as the maximum after applying the subset of intervals applying intervals that contained ai would not help and applying intervals that do not contain ai would not damage, so I just iterated over i and do the updates :P
Your idea is right. I think there're some mistakes in you code.
Can you please help me find what is wrong ?
I'll send you a private letter.
Спасибо за интересные задачи и сильные тесты
Can anyone explain problem F a little , I mean the sample test case 1.
Initially, two kinds of MST are possible. Both uses edges (3,7), (4,8), (1,2), (1,4), (2,3), (3,5). One possible MST uses edge (1,6) while the other uses edge (3,6).
If you increase the weight of edge (1,6), then the only MST possible now is the one that uses (3,6). Same for increasing the weight of edge (3,6) where only the MST using edge (1,6) remains.
If you're not familiar with MST, you'd better search for it first.
Thanks, now I understood the question :)
in B, can answer to test case
4 9973 1 9973 1
be 9973 9973 ?
nowhere it is mentioned x!=y. this solution satisfies all conditions in question.
Thanks vovuh for this nice contest. Questions were well constructed and difficulty was also gradual :)
*Questions were
Thanks for POINTING THAT OUT :(
Hi guys, i work in c++ gnu g++14. I have a problem with task B. All my solutions when tested by me output correct answers but when i submit them, program always output "0 0". Any idea why is this happening ?
You should only use one I/O library (C or C++) after using
ios_base::sync_with_stdio(false);. i.e. using onlycinor using onlyscanf.copying alert : The submissions of the a/c LightningFrenemy213 and arpan_dg are identical.
How to solve E1 ?
For every index in the array, apply every query that doesn't include that index, to the original array and calculate the difference (max-min).
How ? Any reason for this approach
What you're doing with this approach is just checking the final states of the array when that particular index is not included in any query that you've applied. There will always be a case when the difference between max — that index element and min — calculated after applying the queries, will be maximum.
This is one approach, there might be other approaches to solving this problem.
why this solution got accepted. https://codeforces.net/contest/1108/submission/48843911
Why my rating don't update?
cuz there is 12 hours open hacks
O(nmlogn) algorithm of E2 48867037
I use some method to decrease the constant, and it exits when time is up.
I can't blieve D is much easier than C,But it's TRUTH :P
nice problems :D
Weak systests, my solutions passed
This round was quicker than the previous Educational round !!
User Iamoni coded with friends.
Problem A(48801772)
Problem C(48805698)
Problem E1(48808903)
Problem E2(48822818)
Different templates, different coding styles.
vovuh MikeMirzayanov
Good catch there. Also the submission times are highly suspicious. Hopefully they will look into it.
can anybody help why my O(n^3) solution for B is wrong https://codeforces.net/contest/1108/submission/48890311
How did you get this approach?_
I tried to make all the pair of x and y from the given array and then checking for every pair whether it satisfy the given constraint for x and y , if yes then print x and y ( I still don't know what is wrong in my approach).
try tests,where x — is 1 and y — composite num
vovuh, will you publish the editorial?
In a few minutes, bro, please wait a bit :)
In a few minutes,
108 minutes ago XD
It is published now XD But it isn't work XD I don't know why XD
How to solve E by segment tree? (PS: When will the Tutorial be published?
A key observation is that there is always an optimal solution that selecting all segments covering a specific index (let us call it x). To look for x, we can use a sweep line to handle with the segments and use a segment tree to update the answer.
You can see my code for more information.
(UPD) It seems that someone has answered the same approach before :(
thx
Problem E1 https://codeforces.net/contest/1108/submission/48893961
Недостаточно прав для просмотра разбора(
Editorial Page is not working for me! does someone else has this issue too?
48837239 — what is the issue with this?
Why are you not sure about Lamoni?
Take a look on this
ok thanks.