Hasan0540's blog

By Hasan0540, history, 7 years ago, In English

Hello Everyone,

The problem set of the 2017 PSUT Coding Marathon will be available in Codeforces Gym today at 17:00.

You will have 10 problems and 5 hours to solve them (prepared to be an individual contest).

The problem set was prepared by Hasan0540, Vendetta., SaMer, and Maram Tuffaha.

UPD: Please note that the description of part B (and C) of each problem depends on part A.

Good luck!

Announcement of 2017 PSUT Coding Marathon
  • Vote: I like it
  • +35
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Hasan0540 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Will editorial be published ???? Can someoneo help me in problem Roads(A)??

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

    Hint: If you fix some node, all the shortest paths between it and all the other nodes will use all edges except for one (the one coming after the farthest node). Also, if you find the farthest node from i, the farthest node from i + 1 must be found afterwards (or it could possibly be the same one as the farthest node from i).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will anyone help me to solve the "Smiley Faces (B)"?? Getting WA on test 29, :( :( :( will anyone tell me the procedure to solve this and what can be the worst case??

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

    facing same problem :(

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The problem can be solved by doing prefix and suffix sum on the smiley faces. For each prefix find how many smiley faces will appear if you mirror it, and for each suffix find how many smiley face does it have. (from that index till the end)

      Now, you can try mirroring each prefix and check the maximum value of (Pre[i] + Suf[i+1]). Note that you need to check if after flipping the prefix there's a new smiley face at the edges between the prefix and the suffix (i and i+1). Good luck!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve I and J?

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

    Problem I: First if N is odd and there's any cheating pair then the answer is -1 by default (figure out why). Otherwise, when two friends are a cheating pair, this means in an optimal solution one of them sits in an even position and the other one in an odd position. This also indicates that if we construct a graph where two friends have an edge if they're a cheating pair, and we couldn't make it into a bipartite graph then the answer is also -1 since there's a conflict. If not, we would have many independent components each divided into 2 parts (let's call them first and second). The solution is as follows: if we can select from each component either the first or second and the number of nodes we took in total is N/2 (note that the ones we didn't take are also N/2) then we can put those non-cheating nodes together in even seats, and the other N/2 in odd seats and we will have our solution. If we can't do that then the answer is also -1. This can be done using dynamic programming (check the limits).

    Problem J: I'm not really sure about the proof, but the solution is as simple as: If the sum of distances of each marble with its corresponding home spot is divisible by 7 then the answer is "yes", otherwise "no". Though I'm not really sure of the proof to be honest.. If anyone could share why this is always right it'd be great :D

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

      Thank you! Shall try problem I :)

      We coded that logic for problem J and surprisingly got AC xD But yes if anyone could share the proof, that would be nice :D

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem E-Roads(B)?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    since there is always at least one road that is destroyed, we can shift the cities and roads such that the destroyed road connects the new city at location 1 and the new city at location n, now our array is no longer cyclic and we can run dp on it.

    let dp[i] denote the minimum cost such that all the paths that start in the interval 1..i — 1 are cut.
    dp[1] = 0.
    when we want to calculate dp[i], there will be two options to do with the road (i — 1, i).
    1- keep the road: now consider all the paths that pass thru this road and let j be the maximum beginning of all those paths, dp[i] = min(dp[i], dp[k]) for j < k < i, because if we take any k <= j, then the path that starts at j wont be cut.
    2- destroy the road: similar to the above, consider all paths that do not pass thru this road and let j be the maximum beginning of all those paths, dp[i] = min(dp[i], dp[k] + cost) for j < k < i, since we are destroying this road, any path that pass thru it should be cut and if we take any k <= j, then the path that starts at j wont be cut.

    you can also denote by dp[i] the minimum such that the road (i — 1, i) is destroyed and all paths that start before i are cut, the transaction should be very similar to the above.
    this dp can be calculated in O(N2), but we can also do it in O(NlogN) with segment tree or in O(N) with minimum sliding window technique(using deques).
    my code using deques.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved problem G with Segment tree but i had a wrong answer on test 9 can anyone help? this is the submission: 61525218 Hasan0540

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Test case

    The answer for the last two queries is 5 5 5.

    UPD: Actually from query 3 the answer is wrong.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there any formal proof for the solution of J?