Hasan0540's blog

[GYM] PSUT Coding Marathon 2019 (with Errichto's solving stream)
By Hasan0540, 6 years ago, In English

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.

UPD: PSUT Coding Marathon 2019 — solving with commentary

  • Vote: I like it
  • +134
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Reminder: contest starts in 30 minutes.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It doesn't only fail with the last element: in the example I posted above, 3 and 4 are adjacent in both cases.

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve I,i try a O(n(logn)^2) approach but it fail

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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,

    int ans = dist[u[1]];      // dist[u] = distance to u from root
for(int i = 2; i <= k; i++)
  ans = ans + dist[u[i]] - dist[ lca(u[i],u[i-1]) ];

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, first i think like that but i consider that we will have inclusion exclusion principle

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Please provide editorial

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your code will fail at this type of test case

    6
5 7
6 7
7 7

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Failing solution: let dp[i] be maximum log(prefix). AC solution: let dp[i]=max log(prefix[i]) — max log(prefix[i-1]). 54271985

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Solutions for problem J (Graph to Grid):

First solution
Second solution
Third solution
→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The stream collaboration thing is great. I wish it happens with more contests.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply