2-SAD's blog

By 2-SAD, 3 weeks 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 2-SAD. 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  

»
3 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Reminder: contest starts in 30 minutes.

»
3 weeks 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)

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Please provide editorial

»
2 weeks 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

  • »
    »
    2 weeks 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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F

  • »
    »
    6 days 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

»
5 days 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
»
4 days 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.