<copy-pasted-part>
Привет! В 07.03.2019 18:05 (Московское время) начнётся Codeforces Round 544 (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>
UPD0: Я также хочу поблагодарить Stresshoover, dreamoon_love_AA, budalnik и nhho за помощь в тестировании раунда!
UPD1: Разбор опубликован!
UPD2:
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | MoNsTeR_CuBe | 7 | 340 |
| 2 | try_agian | 7 | 370 |
| 3 | HurmousDay | 7 | 396 |
| 4 | AyaOtonashi | 7 | 404 |
| 5 | mohanraghug | 7 | 437 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | greencis | 72:-31 |
| 2 | jhonber | 30:-1 |
| 3 | celesta | 16:-3 |
| 4 | Milkdrop | 22:-15 |
| 5 | MarcosK | 12:-5 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | friendly_potato | 0:02 |
| B | OFAKMKOFZ | 0:04 |
| C | Mbah1937 | 0:03 |
| D | AyaOtonashi | 0:08 |
| E | nvwa | 0:22 |
| F1 | elevendigit | 0:15 |
| F2 | G_MIHAI | 0:21 |
Div 3! Must be the time for high rating!
Please make Div 3 rounds as frequent as Div 2. It is really good from the competition point of view. Otherwise Div 2 rounds include upto 2100 rated competitors on the ranklist which push coders like me to the bottom of the ranklist. Its really hard to even get to the top 1000
Div. 3 rounds are rather educational than competitive, and CodeForces team with no doubt does an amazing job in terms of number of educational contests (both Div. 3 and Edu. contests).
Also, I believe that if you want to be in top N, then much better idea would be to study more and get into overall top N than to chose last N and find yourself in the top N (out of those last N).
I agree with you but all I am saying is competition should be among equal ones. You seem to say there shouldn't be even div1 and div2.
It doesnt matter at all . If ur wishes r granted then u may rank top but ur rating wont go that higher . But if u compete with stronger ones then ur will rise much higher for the same position .
I think rating doesn't matter at all. Be a better version of yourself that's all matters.
I am really excited about my first unofficial contest.
Good to know I am not the only one feeling good about doing contests unofficially :P
6 | 7 | 8 = 8 . only 6 r enough
6 | 7 | 8 = 15
15 problems, nice :)
This round will be much easier than the previous one :) At least, I hope so...
Depends on the hardest problem of the contest.
Well, I think, I was right
I hope there will not be any misbehaviour from the community side this time. :D
Is there any possibility to make contest duration 2:15 or 2:30 ?vovuh BledDest MikeMirzayanov
I already had a rank of 1900, so the round is not ranked for me?
Standings are showing that this its rated for me..I've become expert in previous education round... Figure it out please..
I can see one of my "Specialist" friends is considered as non-official participants in this round(He was 1600+ before previous round). I think both situations are from same reason.
I liked problem D, it's very creative.
What is testcase # 37 in D?,..T_T..
To solve the case37, I change my double into long double.
OMG... i got AC to change long double .. T^T
Hi. I forgot to adjust registration types (official-unofficial) after the educational round rating update. Sorry, I'll fix. Is it good idea to exclude from rating those, who should be official but was indicated unofficial incorrectly? They can be sure that they are unrated and solve problems carelessly.
P.s. I'll fix from Oman. I'm in a trip now.
Hats off! Sir. It's great to see that someone still working when he is on a trip!
Why is the following output incorrect for problem F1 example 3?
1 2
1 6
2 3
2 5
2 7
3 4
5 6
What is pretest 5 in D ?
i think it is ai = 0 and bi = 0
maybe handle case like
3
0 0 5
0 0 5
answer here is 3
daaaaamn how I didn't see that we can multiply 0 with anything
how the equation is a * d + b then when b == 5 if i choose d == 0 then c = 5 not 0 i-->1 -- > 0 * 0 + 0 == 0 i-->1 -- > 0 * 0 + 0 == 0 i-->1 -- > 0 * 0 + 5 == 5
-1*0+0=0 and -1*5+5=0
What can be the test-case 35 of problem F2
i think it's something like
5 6 2
1 2
1 3
1 4
1 5
4 5
2 3
cheak this
My solution of D passed in C++17 but gave wrong answer in C++14. Can anyone explain why? submitted in C++14 : https://mirror.codeforces.com/contest/1133/submission/50944202 submitted in C++17 : https://mirror.codeforces.com/contest/1133/submission/50953520
it is problem with double, it outputs large numbers like 1.32e+10
Yeah got it. I changed to long double and it passed
I'm facing something like that in problem D 1133D - Zero Quantity Maximization. Could you please help me?
TLE in test case 42 C++ 17 51011108
TLE in test case 45 C++ 11 51012754
TLE in test case 23 Clang++17 Diagnostics 51012897
TLE in test case 45 C++ 14 51013012
Your solutions got a few issues:
double/long double/etc. if you're to maintain the exact value of a rational number. Consider storing it in other alternative, like a fully-reduced fraction (to avoid ambiguity, the denominator of the fraction should be positive).unordered_mapin C++ is a poor idea. This is a hash-table-based data structures, with average $$$\mathcal{O}(1)$$$ complexity for accessing/modifying, however the complexity can rise up to $$$\mathcal{O}(n)$$$ when collision occurs. In this case, the default C++ implementation of the hash function is incredibly weak that there are many testcases have been made to specifically counter it. Either use amap(a bit slower with the logarithmic complexity, but much more stable), or implement your own truly random hash functions for yourunordered_map.P/s: A few reference for you, if you insist on re-implementing the hash functions. Pretty helpful.
"Blowing up unordered_map, and how to stop getting hacked on it" by neal.
Test Case 5 in D? Kept getting WA. I kinda knew my solution wouldn't work. But there was a probability it would. CODE
You have to check if both of ai and bi is equal to zero, in this case every d is correct
3
0 0 5
0 0 5
answer here is 3
How to solve F2 ? My approach — run dfs to find all articulation edges in the graph with one of the ends as vertex 1. Let this be art(1). If degree(1) < d , then straightaway answer is NO. If art(1)> d, then again answer is NO. Otherwise, include all neighbouring vertices of 1 connected via articulation edges and remaining d-art(1) vertices from left out neighbours and simply run bfs. However, this seems to give WA on test 16.
I don't know what "articulation" means, but at least there are 2 groups connected to vertex #1(One is consisted of vertex 5 only, otherwise included all vertices except #1, #5).
So the minimum degree required for vertex #1 is 2, so the answer is NO.
By articulation edges, I mean the [bridges](https://en.wikipedia.org/wiki/Bridge_(graph_theory) ). Sorry for the confusion.
It is indeed wrong my friend.
The simplest counter-test
There are no articulation edges, but two components connected to vertex 1.
The soltion doesn't include finding articulation points. You should remove vertex 1, find connected components. Afterwards make sure to reconnect vertex 1 to found components.
Oh I see now. Thanks a lot.
Please Makes me official. <3
My rating is below 1600.
What is test case 58 of E? :/
Task D:
Attempt 1: eps = 1e-4; WA
Attempt 2: eps = 1e-7; WA
Attempt 3: eps = 1e-9; WA
Attempt 4: eps = 1e-18; WA
Attempt 5: eps = 1e-18; WA
Attempt 6: eps = 1e-25; WA
Attempt 7: eps = 1e-300 AC
you can use GCD and map rather than division so you don't need to use eps
Yeah, I mentioned this but I thought that two fractions a/b and c/d with difference less than eps would also be one d.
Lol I was thinking that way when i wrote eps = 1e-300
I'm facing something like that in problem D 1133D - Zero Quantity Maximization. Could you please help me?
TLE in test case 42 C++ 17 51011108
TLE in test case 45 C++ 11 51012754
TLE in test case 23 Clang++17 Diagnostics 51012897
TLE in test case 45 C++ 14 51013012
just use map rather than unordered_map , AC
Surprised!
But why did it make the change? Can you please explain? However thank you!
Because unordered map insert and delete operation may work in O(N) time in some situations because of collision, meanwhile map works O(logN) time.
Excellent
Can we really use map with double index ?
I thought that this is why I'm getting WA so I tried using Gcd
You can use map with any index you like
I know but if it's a result of fraction it may give wrong results
Use a map with a pair as index, the pair being Ai and Bi reduced to their lowest ratio. So no need to use any fraction whatsoever.
I passed D with
long doublebut I'm not sure if this solution will survive after hack wave.F2 was perfect
what's the test case 37 in F2 ?
No ideas
I got WA on tc 37. When I selected edges starting for 1 randomly.
Simple counter tc for this was -
4 4 2
1 2
1 3
2 3
1 4
You should select 1,4 and 1,2 or 3.
You will get WA if you select 1,2 and 1,3.
I'm getting correct answer this case , my output is (1,4) (1,2) (2,3) .
Bonus: Can F2 be solved if the problem asked if any vertex can have degree D instead of specifying the first vertex
I have a trivial doubt.... What do u mean by first vertex ?
Is this a correct approach for the bonus question posted above?
First, check the number of connected components for a vertex with degree greater than or equal to D using articulation points DFS. If that value comes out to be less than or equal to D then use this vertex as the start point. If no such point exists then the answer is NO.
Code = https://pastebin.com/deATp7x6
Microsoft Visual Studio 2010 hasn't the "long double",I can't accept the problem D!!!!! My attitude booms !! And I feel very unfair!
Actually, it is possible to solve D without using double, long double or any floating point number.
It was one of the coolest Div.3 rounds i've seen! Thanks a lot to creators!
How to solve E?
For every index , find the the max element which can be inserted in current set, now we have n different ranges (n , different teams ) out of them we need to select k teams such that students count is maximized (remember that a student can be in at most 1 team ) ! This can be done by dp , selecting the current range or not selecting (kind of knapsack problem ) !!!!
Sorry，i mindlessly clicked the "i do not like it".
no problem !
Q-D my answer works similar to other c++ users but I am getting TLE i am even using pypy, any optimization suggest, please!
Problem C: int arr[]=new int[size]; // getting Time limit exceeded vs Integer arr[]=new Integer[size]; // working perfect
why??
read this
I loved problem D, it was extremely innovative.
Я не знаю, читал ли vovuh мой пост про сложность, но сегодняшний div3 явно был гораздо ближе к третьему дивизиону по сложности, чем предыдущий. Спасибо.
Я видел ваш пост. Я каждый раз стараюсь сделать как можно более сбалансированный раунд, но иногда не особо получается все подогнать так, как нужно.
surely the best div3 round ever!!
Again failed to cross 1200. "APNA TIME AAEGA"( My time will come).
Yes, keep solving problems: It may take years but we'll get there!
how to solve f2?? i am getting wrong answer on test case 35,here is my submission https://mirror.codeforces.com/contest/1133/submission/50987588
i think 35 test case is similar to this case
Why grid approach doesn't work for E ?
Can someone elaborate on dp approach E, what does i and j means in dp[i][j]?
Depends on your interpretation, on mine DP[i][j] is the solution for the problem on the interval with indices [i,N) given j groups available
So, given a state (i,j), the best solution is made by either using the group that starts with the i-th element, or not using it.
This is DP[i][j] = max(DP[i+1][j], DP[next[i]][j-1] + next[i]-i)
Where, if the group that starts at i is [i,k) then next[i] = k.
nice, thank you
For problem E : Many solutions have failed on TC:58 if they have used greedy approach i.e.,for each k, calculating maximum length of range for which given condition is true( using binary search ) and then adding them.
code which failed on TC 58 : https://mirror.codeforces.com/contest/1133/submission/50976279
This approach is wrong because it is possible to obtain even higher number.For this we need to apply concept of DP.
for eg: consider TC : n=8, k=2, array a={ 3,5,5,5,5,9,9,13 }
By using greedy approach, we get maximum length for k=1 as 6 for {5,5,5,5,6,6} and then for k=2 (i,e., after removing elements from i=2 to i=7) we get maximum length as 1 (for 3 or 13).
so total number of students using greedy approach = 6+1=7.
But this is not most optimal as the best way is
for (k=1) take range as {3,5,5,5,5} = 5 for (k=2) take range as {9,9,13} =3 so total number of students using optimal approach = 5+3=8.
So DP approach (correct approach) :
Tabulate a dp[i][j], ( we will use bottom up approach i.e., first kth team filled then (k-1)th and so on...)
where dp[i][j] --> maximum total number of students included till now (i.e.,from team 'k' till team 'j') such that jth team is filled with val[i] and (j+1)th team is already filled with optimal value(computed in bottom up approach ).
dp[i][j] can be obtained by using the forumula
dp[i][j]= val[i] + max( dp[ i+ val[i] ][j+1], dp[ i+val[i]+1 ][j+1],......,dp[n][j+1] );
where , val[i] denotes length of longest range for which condition is true from ith index. i.e., for array a={3,5,5,5,5,9,9,13} val[]={5,6,5,4,3,3,2,1}
val[] can be precomputed using binary search in O(NlogN).
ans= max ( dp[i][1] ) for i=1 to n.
Time complexity : O(n*k + nlogn) for bottom up tabulation and precomputation of val[].
ACCEPTED Code : https://mirror.codeforces.com/contest/1133/submission/50989079
Not really relevant, but calculation of val[] can be done in O(n) using two pointers: 50991120
Hi! Please tell me what's wrong with my solution. I've used two pointers approach. Code
I just noticed a test in A contradicts what was said in the description
the 23:59 00:01 one because the description said the competition happenned on the very same day
It does happen on the same day, it starts at 00:01 and ends at 23:59. Its total duration is 23:58, and half of it is 11:59. Therefore, the middle of the contest happens at 00:01 + 11:59 = 12:00. It would be incorrect if it was 23:59 and 00:01, but it is 00:01 and 23:59 (notice that the order does matter in this case).
I assume you are talking about the 5th test case for problem number one. It is : 00:01 23:59 and not 23:59 00:01.
It is clearly mentioned in the question that the first time denotes the start and the 2nd the end time of the contest, considering this the input it valid.
For problem F1, I've used Kruskal's algorithm but picking all edges coming out of the maximum degree vertex first and then add other edges which satisfy the spanning tree property.
This resulted in a TLE. Time complexity for the code I have written (in PyPy 3.5) is O(m+n). How can this be improved?
F1, doesnt require Kruskal or Prim's algorithm. Just a simple dfs is enough. Find the vertex with the maximum degree, S. connect it to all it's neighbouring vertices and marked them visited except one vertex.
Just do the dfs from S. Link
Python or PyPy is poor to use in this platform. Many competitive programming platforms never respect slower languages such as Python, etc. So use C++ instead.
yeah mine also got TLE at 44th case and cpp passed them all
See to the rankings where trusted participants include people above 1600 ratings
Previous contest rating update haven't included in current standing yet. It'll be fixed soon.
When will the system testing start? Can it finished before the next compitetion
Hello everyone, I am quite new to Codeforces, I tried to submit solution to problem C, after seeing top submissions but I am getting TLE from the same logic in JAVA. Can anyone help me.
My code: http://mirror.codeforces.com/contest/1133/submission/50999444
The code I referred: http://mirror.codeforces.com/contest/1133/submission/50935270
i have waited system testing for 2 hour :(
can anyone tell me what is wrong in my code it is giving wrong answer for test case 4. i have just iterate it over all the edges Your text to link here...
In question F1
Can anyone please tell why I am getting TLE in My solution. https://mirror.codeforces.com/contest/1133/submission/50969866 The time limit given in this question was 2 sec.
I think it works
O((n - 1) *(n + 1) / 2)time, which is bigger than 10 ^ 10.How many operations can we perform in 2s?
Almost 10 ^ 9 opearations in two seconds
I want help in question D(Zero Quantity Maximization) can somebody give me a hint for the problem
its easy to say if ai*d + bi =0 ==> d=-bi/ai we make a map for d then take the d who solve to many equation so we take the biggest frequency of d in the map you can save d as pair<int,int> or long double
В задачах С и Е, можем ли мы бинарным поиском находить для каждого a[i] первый элемент, который строго больше a[i] + 5(или к), и считать дистанцию между элементами? O(nlogn), должно сработать.
what wrong in my code of B 50962881 it failed on test case 22
this is your bug in test case 22 if(k==1)return cout << n << endl,0; you can fix it by make n even if(k==1)return cout << (n — n %2) << endl,0;
Can someone help me understand why my code is giving RUNTIME ERROR on test case 18 in problem F1? http://mirror.codeforces.com/contest/1133/submission/50972145
editorial plz
How to solve E?
My solution: Find the team with the maximum number of students and then remove those students from the vector. Repeat until all students are in some team. Then pick the largest k teams. But it gives WA on test #52
i think you need to implementation DP approach rather than greedy one
Can F2 be solved by finding articulation edges / bridges in the graph and as soon as we find bridge edge we merge them and after that we pick any random adjacent edges of vertex 1 so as to make its degree exactly d. and after make the whole tree connected using kruskal type algorithm? Here is my submission for reference of what i am talking. Pls tell if i am wrong. Thanks
Hi! Please tell me what's wrong with my solution to problem E. I've used two pointers approach. CODE
Why there isn't any tutorial for this round and I want someone to explain problem E dp approach