Hello everyone,
The problem set of the 2019 PSUT Coding Marathon will be available in Codeforces Gym on Apr/30/2019 18:00 (Moscow time).
You will be given 5 hours to solve 11 problems of difficulty similar to Div.2 contests. The problems are sorted by their estimated difficulty but we recommend reading all problems.
The problems were written by Reem and Hasan0540. Thanks to Jester, Vendetta. and Dark for helping us in preparing some of the problems.
Errichto will be solving the problems in a live stream soon (the time and links will be posted here later). We believe it would be a great learning opportunity to participate in the contest and try all problems and then to watch the stream.
We hope you enjoy the problems and we welcome all feedback!
UPD: Errichto will do the live stream tomorrow, more details here.
Reminder: contest starts in 30 minutes.
How to solve C? my solution is like this: if n <= 5 print -1 else for even i swap a[i] and a[i+n/2] ( without reswaping if it's already swapped) , but i got WA on pretest 3 ( n = 6 I guess)
n = 5 is possible. One way is to have
1 2 3 4 5
become
1 3 5 2 4.
I'm also not sure how your algorithm works. Did you try it on n = 6 case?
With your algorithm,
1 2 3 4 5 6 becomes 4 2 6 1 5 3
but here 1 and 6 are adjacent in both cases.
I forgot to mention that this method fails with the last element only, so i added an extra loop to swap last element with another without breaking the rule code
It doesn't only fail with the last element: in the example I posted above, 3 and 4 are adjacent in both cases.
how to solve I,i try a O(n(logn)^2) approach but it fail
When solving for a project type $$$p$$$, sort all the nodes of that type according to their dfs start time. Say the order is $$$u_1, u_2, ..., u_k$$$ Now you can simply do this,
Short explanation : Suppose you have got the answer of $$$u_1, u_2, ..., u_{k-1}$$$ and you add a new node $$$u_k$$$ in the set. Now you are just adding the distance to $$$u_k$$$ from root, but some part of the path might already be taken previously. And that part is basically lca to the previous node. This works because we sorted all the nodes by their start time.
Thanks, first i think like that but i consider that we will have inclusion exclusion principle
Please provide editorial
I've been trying problem D but I'm getting a wrong answer on test 16, can anyone help me with this?? my code link https://www.codepile.net/pile/ZaE7XZN3
Your code will fail at this type of test case
your code is printing -1 but answer will be 5 7 7 7 7 6.
mistake is in compare function where you are comparing only on the basis of l but if l is equal you have to compare on the basis of r as well.
Thanks man!!
How to solve problem F
Failing solution: let dp[i] be maximum log(prefix). AC solution: let dp[i]=max log(prefix[i]) — max log(prefix[i-1]). 54271985
Solutions for problem J (Graph to Grid):
We will place the graph on an grid of two rows and completely stretched, then compress it.
Since compressing the blocks of cycles into single nodes gives a tree, we can actually use the same method of finding the longest path in a tree to get the longest shortest path of this graph: Start BFS from any node, then do another BFS from the farthest node found in the first BFS. You may do this on the original graph without compressing anything, as the shortest path will always be equal to the Manhattan distance between the ends of the block.
To avoid changing the row in the middle of a block of cycles, we want our path to change its row at the first column of the block, if needed.
To do that, we will just sort the nodes in each adjacency list by their degrees. This way the same BFS we implemented will prefer the boundary paths.
You will see why this is useful in the next step of the solution.
We will start placing the nodes from left to right, starting at the first row. For every three consecutive nodes on the path: $$$i-1$$$, $$$i$$$, and $$$i+1$$$, if nodes $$$i-1$$$ and $$$i+1$$$ have a common adjacent node other than $$$i$$$, it means we should change the row of node $$$i$$$ (go down instead of go right, then place $$$i$$$).
This works because we have a boundary path.
For each column from left to right, if there's one filled cell, and that cell has an adjacent node that is not placed yet, place it in the empty cell of the same column.
Now we have a solution, it's only problem is that it is stretched and may not fit inside our grid of $$$c$$$ columns.
Start from the first column that has two rows filled, then every time we have 4 consecutive columns with one filled cell, we alternate the row of the second last node to the end, and set the count to 1.
Note that at the end, if the counter is more than 2, move the last placed node to the previous column and change its row.
Now do the same for the prefix (before the column we started from), going from right to left.
Make sure to handle the case when there are no cycles properly.
Complexity: $$$O(c)$$$
Code: https://ideone.com/Y0GjEk
You can solve the problem using Backtracking.
First find the farthest node of any node using BFS, we will start placing the graph from this node at the top-left cell.
List the nodes in BFS order, and start placing them in a recursive function. Every node will have at most two possible positions to place them, try both of them. If that option is invalid, you will find this while placing the next node or the one after it as you will have no options for that node.
Note that to get a compressed solution you should try the option that stays in the same column before the other option.
The fact that you will backtrack too soon and go with the correct option makes this solution work in $$$O(c)$$$, but it can be a bit slow due to implementation details.
We don't have an implementation for this solution but I think Radewoosh and Tutis are doing something similar, you may check their solutions.
You can watch Errichto solving this problem here: https://youtu.be/NtQH0at4Lnc?t=10405
The stream collaboration thing is great. I wish it happens with more contests.
Hasan0540 Today I was doing this contest and by accident I found a bug in your checker for problem D.
Check submission 59608300 test case number 9, I forgot to terminate the code after printing -1, resulting to printing extra numbers. It looks like your checker stops when a user prints -1.
However, I was expecting interesting contest and problems and I was not disappointment all all. Thanks lot :D
Thank you for pointing that out, I've fixed the checker: 60780298.
Glad you liked it! :)