<almost-copy-pasted-part>
Привет! В Jun/09/2019 17:35 (Moscow time) начнётся Codeforces Round 565 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
UPD: Пользуясь случаем, хочу пригласить желающих в летнюю школу программирования Сазанка-2019 (больше информации вы можете найти здесь). Осталось несколько свободных мест. Там буду я, Иван BledDest Андросов, а также приедет Михаил MikeMirzayanov Мирзаянов! Регистрация закончится 23 июня.
UPD1: Большое спасибо Um_nik, Rudy1112, nigus, _overrated_ и Temotoloraia за тестирование раунда! Также спасибо моим дорогим друзьям Ивану BledDest Андросову, Роману Roms Глазову и Михаилу awoo Пикляеву за помощь с подготовкой раунда!
UPD2: Разбор опубликован!
UPD3:
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | Yushen | 6 | 235 |
| 2 | IMRED | 6 | 293 |
| 3 | BudiArb | 6 | 345 |
| 4 | xenoframium | 6 | 350 |
| 5 | njchung93 | 6 | 439 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | nikolapesic2802 | 69:-15 |
| 2 | stefdasca | 42:-11 |
| 3 | dorijanlendvaj | 15:-11 |
| 4 | interestingLSY | 5:-1 |
| 5 | orz_liuwei | 10:-11 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | riz_1_ | 0:02 |
| B | _ekaterina_dudina | 0:04 |
| C | BudiArb | 0:05 |
| D | hxylalala | 0:18 |
| E | csts.21 | 0:17 |
| F | njchung93 | 0:32 |
It will be a great contest... Best of Luck to all...
Div3 Contest == vovuh
What a nice person!
ITS INDIA VS AUSTRALIA IN THE CRICKET WORLD CUP ....#TIMECLASH
So don't give contest
kam boll thoda
oh my god , khud tourist ke papa ji ne apne unrated account se reply kiya hai , main to dhanya ho gaya
Contest > Cricket
I think that "copy-pasted part" is just a dead meme, let it go
No! It's a tradition! It will forever be there!
Love div3!
Let me think :
$$$ Div.3 \Leftarrow \Rightarrow Div.(1+2) $$$
so why not rated for someone whose rating is more than 1600
mathematics 100
Let me rethink :
so why not rated for someone whose rating is more than 2100
mathematics 2100
A further thinking:
so why not rated for someone whose rating is more than 1600 and less than 1900
Div.3 participants are very lucky
Div.3 ⇐⇒ Div.(2 + 3)
Also can take a part in Div.2 contests
the next prepare many DIVs for you,the div3 is for the rating lower than 1600
The trick is to get lucky, this is the second time I fall from expert to specialist and the next round is DIV3.
haha
cheer up
Wish everyone have fun!
I just want to say I appreciate the Slay the Spire problem.
What is the solution for F? I can't understand why my dp solution didn't work. I had dp[i][j] that means maximum cost for the first i rounds if the count of the total cards we use is j modulo 10.
I had the same idea and it got AC https://ideone.com/rRrMmW
Well I still don't get it my solution is wrong. I almost did the same things as you. Can someone please check my code?
I think the cause of the problem is this code:
int t; if (j % 10 != 0) t = 1; else t = 2;Check, for example, this test case:
The answer is 13 while you program prints 12
Ah, shit. Thanks for you help, the problem was the case when new 10'th is created. Now I fixed it T_T
My solution had the same idea also and it fails on testcase 2. Did you take into consideration that you can reorder the cards of each round however you want?
I've got accepted with this idea.
55365600
This is the solution for F, maybe you made mistake in considering the different cases.
Choose only one three cost card (if exists)
Choose one two cost card and one, one cost card (if exists)
Choose one two cost card (if exists)
Choose 1-3, one cost card (if exist)
Choose no card.
Instead of considering multiple cases we can do the following:
Why is this TLE?
TLE
There can be up to $$$2*10^5$$$ test cases in the problem with graph containing only one edge (1, 2). Your solution creates so many arrays of size $$$2*10^5$$$ each, and it leads to quadratic complexity of the solution. Replace all arrays with vectors of size $$$n$$$ instead of $$$2*10^5$$$.
Same happened with me. But vovuh I have declared a global array fo all test cases. Why does this give TLE? Shouldn't the memory allocation be just once for all test cases as I have used a global adjacency list??
55377706
In your case the problem is in the adjacency lists. Where do you clear them between test cases? I think your bfs works too long overall. I don't know how it passed the first test lol.
I was completely surprised by how hard these Div3 tasks were..
I dont know. As for me, it was not too hard. A,B — quite standard problems. C — binary search, D — Sieve of Eratosthenes, E — vertex paint. But maybe i'm wrong
C can be solved in O(n).
How?
https://codeforces.me/contest/1176/submission/55341035
There's absolutely no need for O(logN) complexity when the constraints are within O(NlogN) bounds.
C can be solved in O(n). It's seems pretty easy. See my submission---! ! ! ! ! ! 55354250
n*logn
No. It's O(n) . No need to consider log(n) for map . You can also take 6 variable for count insted of map.
hey can u plz explain your logic I see your code but I didn't get it...plz!!! thanks.
O(n): https://codeforces.me/contest/1176/submission/55357808
> O(n)
Uses std::map
It's still O(n).
You're not wrong at all, its my fault that I didn't get these, but the fact that on the previous Div2 contest I got ABC and I couldn't even get Div3 B now is stupid from me. Looking at the solutions, the solutions are pretty clear, but they didn't seem pretty clear to me when I was trying to create one by myself. I'm just venting because I've tried really hard to come up with a solution but I couldn't do it because of simple restrictions in the problems that I just couldn't overcome.
Dont worry, just keep training
Can you hack my randomized solution for E? 55348371
I was not able to solve a single problem in this contest. Any direction to improve this. I was stuck in question number one itself for more than 1.30 hrs. in the last minute I got a correct solution for the test cases but forgot how to take input from multiple newline.
Any direction would be helpful.
Whats number of the taks?
The best and straightforward answer is just solve more problems. I've started CF 2-3 months ago, and I'm better now than I was then purely because I've simply solved more problems.
I managed to only solve A in this contest when I usually do ABC in Div3, but that attributes to me mostly not solving enough problems that are similar to this.
All other advice pale in reference to the first I provided you, but its also nice to know that Div3 ABC and Div2 ABC can almost always be solved greedily (they just require implementation/data structures and not complex algorithms like graphs or dynamical programming).
In fact, A was not as easy as it should be. I solved it by trying in which order the three operations should be applied. But I still dont know why the one I finally submitted works, and others do not. B was less problem for me than A. As a suggestion, try to keep calm if it does not work out as expected.
How do I delete a comment
You can't delete your comment after two minutes.
Why is this approach wrong for the problem E:
For every edge, if a vertex is not taken and is not visited by a previously taken vertex then I will take this vertex. Any sample case to prove that I might take more than n/2 vertices.
Example from awoo:
If you'll start coloring from the vertex $$$5$$$, you cannot take less than $$$3$$$ vertices to cover all vertices (vertices can be reordered so the vertex $$$5$$$ will be vertex $$$1$$$ or something like this).
Consider a chain of length 3. If you start from one end, you will need to color 2 vertices which is more than 1.
If both nodes are unvisited I was taking one with a greater degree so this case was being covered but the example from vovuh is what I was missing.
maybe smth like 1 -- 2 -- 3 -- 4 -- 5, you get 1,3 and 5?
getting runtime error in problem D but working fine on local ide.
For D, you need to sort the array and then look at the largest number, say L. If its kth prime, then L can't be part of original array, so we add k as one of the elements of original array. We remove L and k after this from array and repeat. If L were composite, then it definitely gets added to original array and we remove L and its highest divisor from the array. The highest divisor can be found easily if you store for every number what is the smallest prime that divides it. Use seive smartly.
For E, just color the graph with alternating white and black colors. I know it may not be bipartite but its okay. Then if white nodes are more than N/2, we chose black nodes.
I am getting a runtime error in Problem E. Can someone help fixing it. Link to Code
Logic: I do a BFS starting from the node having largest degree and proceed to add nodes in the answer which are present at odd levels with respect to the root.
https://codeforces.me/contest/1176/submission/55374222 i have done the same !! why it giving me tle ?
Memset color giving u tle, because if there are 2 nodes and 10^5 test cases that gives u 10^10, u need to clear color just size of n, also clear graph size of n
Sir, I love your videos regarding competitive programming and always get motivated
We can find the distance of all nodes from root(1). (using simple DFS)
Then we can select even or odd distance nodes which fulfill ( N/2 — condition) .
What is wrong with this approach for E : I will consider all the nodes which has only 1 adjacent node and take that one adjacent node into the answer set(not the node which has only 1 adjacent node).Then go for the the existing nodes one by one and if not adjacent to any node that i picked already I will take that too.
Testcase 6 in problem C ?
May be smth like this: 12 4 8 15 16 23 42 4 8 15 16 23 42
My code is showing answer as 1.
12 is not possible as an array element I think?
12 is the value of n.
Did you interpret meaning of subsequence right? I thought it might be an error.
https://codeforces.me/contest/1176/submission/55357081 please check my code.
I think those break statements messed it up a bit, instead incrementing index was better choice, what do you say?
Number theory and Graph theory? it seems really difficult for div3
Can anyone tell why I am getting TLE in Problem C at TC:7 https://codeforces.me/contest/1176/submission/55371060
maybe due to the use of remove function. I was doing the same at first attempt .
What is wrong with this solution 55346608 of B?
rem[1] -= min(rem[1],rem[2]); rem[2] -= min(rem[1],rem[2]);
when you subtract from rem [1], the result increases as the already subtracted rem [1] is subtracted from rem [2]
You are changing the value of res[1] before calculating min(res[1],res[2]). Store the value in some other variable and then u can use it later. I have corrected your code : https://codeforces.me/contest/1176/submission/55376346
Thanks...
That was such a foolish mistake
What is the hacking test case for Solution E ??
Is it legal for codeforces? If so, it seems to me unfair
I meant share hacking test with others
The contest is already over and I think any discussion about only seems useful
How is it unfair?
Nobody is being awarded any marks for hacking other's submission.
In my case: My solution got Hacked because of using memset(visited,0,sizeof(visited)); for each test case. The size of visited array in my soln was 2e5. So if the number of test case is 2e5, it will give TLE. :/
This is really strange behaviour I have observed. My solution is absolutely correct but still giving tle. can someone look into this. Thanks in advance.
My solution
It is really annoying to see people with the same approach pass the solution. where as my solution fails.
Soulution with similiar Approach that passed
Aonther Such Solution
And here one more
I kindly request community to help me figure out the issue. Correct solution being hacked due to some disgusting silly tight time constraint is really frustrating..
you use memset T times
Using memset T times: giving TLE. Even my solution got hacked due to same reason :/
I guess that's really awful. getting tle for absolutely correct solution. what say?? Such silly tight time constraints shouldn't be entertained. Even if one puts up correct solution, getting unsuccessful verdict for this is really not done.
Well, I think that we should have been more careful about it. It was clearly written that the number of test case are till 2e5. We could've done without using memset. Check my latest submission.
I don't see anything awful. Maybe you see this for first time. But doing something unnecessary should not be entertained and that's what problem author has done! When you don't need $$$2\times 10^5$$$ nodes in each test case then why using memset? You should know about the functions before using them.
Will an unsuccesful hacking attempt affect my ranking?
not in div 3
Can you explain me why is it working as it is working?
55375918 this solution gets OK
55375854 this solution get TL
But the problem is, the asymptotic is the same.
The difference is that in first submission we check from 2 to x-1
and in second from x-1 to 2.
Am I missing something?
The number 1530169 = 1237 * 1237 is not a prime, so in the first program you will iterate from 2 to 1237, but in the second program you will iterate from 1530168 to 1237.
Will an unsuccesful hacking attempt affect my rank?
No
I am curious about how to do for minimum number of vertices in question E, anybody can help?
Asking for minimum number of vertices is NP-hard. Wikipedia page
Ok thanks
For a tree u can calculate that value using dynamic programming and problem is called minimum set cover
When you get WA on C.
PS: Those who have watched Lost will relate.
When you get WA on submitting C.
PS: Those who have watched Lost will relate.
Indeed, this number sequence is the one used in "Lost".
How come I am getting TLE? Problem E
https://codeforces.me/contest/1176/submission/55377412
WTF !!!
Memset gave me TLE in E.
I think it's because you use memset in the beginning of each test case. Which is around 1e5 test cases, and you use memset for an array with a size of around 1e5, so its basically a TLE.
Yes, I realised that later.
is using memset inside the test cases loop making E questions wrong ?? Hard Luck to those who have not taken care of it.
yes, someone hacked my solution using TLE verdict. :(
How to solve problem E ?
You can DFS or BFS start from node 1 to build a tree of the graph. Now if the number of nodes which have odd degree is <= n / 2 then the answer is all of them, otherwise the anwser is all the nodes which have even degree.
Notice that this problem can be solved on a tree this way:
Now, we can notice that removing edges from our graph without breaking it into multiple connectivity components does not affect the solution correctness (if we satisty all conditions with less amount of edges, we still satisfy it for any additional edges). This allows us to delete some edges from our graph without breaking connectivity. So, we can delete all edges and only leave a spanning tree of our graph (we can do it with DFS) and solve problem on a tree.
understood ! thank you very much.
how i can get a tree by delete some edge?i do not understand you
We can find an edge that does not break a graph connectivity and delete it from our graph. If we will repeat this operation until there is no edge left that can be removed from the graph without breaking conectivity the graph will become a tree. This happens because we can only delete an edge that is included in some cycle in a graph and when we will eliminate all cycles in given graph it will becaome a tree. Such tree is called spanning tree of our graph.
But in practice it is not efficient to build spanning tree of a graph by iterativety deleting edges and checking connectivity after this. We can utilize some graph traversal algorithm here, such as DFS or BFS. These algoriithms have an important property: they visit each vertex only once. So, we can track the edge that was used to come to each vertex for the first time (except for the starting vertex). Obviously there will be no cycles in choosen edges, so we will get a tree that connects every vertex that can be reached from the starting vertex. So, we get a spanning tree of our graph.
These trees are also called DFS-tree or BFS-tree and have some additional useful properties along with being a spanning trees of a given graph.
Hope this explanation helps.
thank u
if anyone wants to hack plz hack my solution of E i want to know whether it is correct ??
Try resubmitting it.
Bop it!
Hey guys, I have made a new app Coding List which contains all live, upcoming programming competitions from hackerearth, kaggle, codechef, codeforces, topcoder, aigaming, hackster, codinggame, hackerrank, projecteuler, atcoder and many more.
A must have app for programmers. Please rate and review it. Try it here https://play.google.com/store/apps/details?id=io.github.vikasgola.coding_list
ss
Can anyone please tell why am I getting TLE in Problem E: 55381696 Thank you..
check answers above before commenting.
How come I am getting TLE? Problem E
https://codeforces.me/contest/1176/submission/55377412
Did C using recursion(dfs style). But I guess many did in iterative way. Anyways complexity comes out to be $$$O(n)$$$.
Here is the Code
Hey guys, can anyone tell me what's wrong with my solution for C (https://codeforces.me/contest/1176/submission/55357077) ? I fail test 7 and I don't see why. Maybe someone can tell me a counterexample for my approach.
i don't know if that is the main problem or not .. but test like this
fails in your code .. you pop from the queue whenever you enter the function even if the sequence isn't right so you affect the following sequences.
Can someone tell me why this TLE plz? Thanks! Code
you define vector t times with size MAXN.
Editorials?
did it rating?
Not it
okay
The writer of F( Destroy it!) must be a Slay the Spire player !
Can someone check my code in Problem D? I have no idea about why it got Memory limit exceeded on test 5.
your bug is in finding maxD. actually you're finding greatest prime factor! and cause of this you may erase something which is not in multiset(st.end()) from it and you get memory limit in this case
I get it. I should read the problem description closely. Thank you!
I think you're incorrect fill maxD. maxD at your logic is max prime divisor while you need there to just max divisor.
You can fix it, if replace maxD with minD and try to find p / minD[p] instead of maxD[p].
Good contest with less number of hacks :)
Can someone help me? Problem C, my code I am getting answer 65 in test case 65 instead of 64.
I suggest you read my_solution for problem F(Destroy it!). I have dp[N][10] that dp[i][j] is maximum sum if we have get x cards from first i round and x mod 10 = j. and it's easy to see that in each round we may use only 3 strongest card that cost 1, strongest card cost 2 and strongest card cost 3 so by a mask on these(at most 5)cards you can update dp easily. if you have shorter solution please tell me
I think this is intended solution. I have something similar but I didn't debug yet. And I really doubt there is something shorter
In problem E why an output of:
2
4 5
wrong for the test case:
5 8
2 5
2 1
5 1
4 5
1 4
2 4
3 4
3 5
For this test case your output is correct. But in test#2 there are 40057 testcases. You just wrong output in some other testcase.
P.S. Your solution is incorrect for graph-chain. Lets imagine graph 1-2-3-4-5-6. There are 6 vertexes. And you output n / 2 vertexes with smallest degrees. There you can output vertexes 1, 6, 2. And vertex 4 remain unconnected.
Yes, thanks.
your solution isn't correct let's try this:
1
7 6
1 2
1 3
1 4
2 5
3 6
4 7
Sorry if this question is trivial but I don't relly get the solution of C. I think that we just need to find the number of subsequences that can be formed from the given array by finding the minimum frequency of 4, 8, 15, 16, 23 and 42, right. But that solution fails at test 6, which I don't understand why because clearly we can have 13 subsequences in this case.
Your solution doesn't respect order of numbers.
As said in task:
"Examples of bad arrays:
[4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,42);..."
Can someone please have a look at my code for problem D. I can't understand why it is giving WA on test case 20. Thanks
Editorial please
Can somebody help me out here? This submission for problem A where i used map to store results gets TLE whereas this one which uses brute force doesn't. Shouldn't the former just reduce complexity?
First solution does three recursive calls, second always does only one.
Oops, I didn't even notice that i used
ifinstead ofelse ifthere, this was quite stupid to even ask, Btw Thanks mate.for problem A why do you choose this order of operation 4*n/5 , 2*n/3 , n / 2 ?
I don't think the order matters in this question, as the number of steps depends on the prime factors of the number itself. Let's take 60 for example, here 60 = 3 * 5 * 2 * 2 ; so it will always require 2 operation 1, 1 operation 2 and 1 operation 3 and as second and third operation multiplies 2 and 4(2 * 2) respectively, we would need to apply first operation 3 more times. Hence, the answer would be 1 + 1 + 2 + 3 = 7 irrespective of the order of operations applied.
let's take n = 10 and order /2 , 4/5 ,2/3 then n is 10 , 5 , 4 this outputs -1 so order does matter if u do it this type of operations but i think you to wanted to get its factors so you do /2 , ans ++ , /5 , ans+= 3 , /3 ,ans+= 2 ,
Dude, for 10 if you apply 1st operation first then it would go like this 10 -> 5 -> 4 -> 2 -> 1 (applying 1st operation two more times when n was transformed into 4). if you apply 2nd operation first then it would go like this, 10 -> 8 -> 4 -> 2 -> 1. Number of operations remains same irrespective of order (in this case it is 4). And this should hold for every number as number of operation depends solely on the factors of that number.
that's wrong !
How is that wrong? can you elaborate?
I misread the statement , sorry .
Getting WA in problem D. My logic:
First, I sorted the given array in descending order. If a number is composite, I printed it and removed this number and it's highest divisor. Finally, The array contained only prime numbers and printed lowest half of prime numbers. My submission.
Your algo is correct
But, why getting WA ?
"The array contained only prime numbers and printed lowest half of prime numbers" — I think this is incorrect.
3
2 3 3 5 5 11
Correct answer: 2 3 5
Your answer: 2 3 3
Can you please make an editorial for this contest?
Editorials?
Div.1⇐⇒Div.(2−3+3-1)
Hello, I have no idea how a girl @hdude0164 managed to copy my solution during the contest. I don't know her by any chance whatsoever. I don't use any online IDEs, I use dev cpp on my laptop and submit the solutions on codeforces. I don't know what else could be provided as proof to prove my innocence. I had submitted the solution 15 minutes prior to her. Plus i did some research, her original account is @chhavij and this is surely some fake account. Please look into it.
Are there editorials?
Also, can someone explain why is C a binary search problem?
When will the editorials be published?vovuh
Никто не знает когда разбор? Хотелось бы узнать решение задачи F. Я дальше алгоритма укладки рюкзака не придумал(ва2)
По сути там и есть рюкзак.
dp[n][i] — максимальный урон после n ходов, если использовалось кол-во карт, остаток которого на 10 равно i.
На каждом ходу есть всего 5 возможностей выбрать карты. А дальше все тот же рюкзак.
Hi
I saw you need editorial so i wrote this my self i hope it's useful for you
problem about link is just fixed
In problem E how can we find the minimum number of nodes to be chosen to satisfy the given condition
Wow such an amazing problem!
But it seems to be NP hard cause I think if we can solve this we will solve that type of SAT that want minimum sum of variables.
thanks bro
https://codeforces.me/contest/1176/submission/55406758 Can someone explain me why is it failing?
Why is this solution right solution ? 55421378
Best of Luck for your first contest as a problemsetter.