Блог пользователя Shafaet

Автор Shafaet, история, 8 лет назад, По-английски

Hello CodeForces Community!

HackerRank is back with another World Codesprint! Join us on 21st May, exact time can be found here.

Its your chance to win upto $2000 Amazon gift cards/bitcoins and tshirts. [Note: Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.].

Contest duration is 24 hours. The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.

The challenges were prepared by osmanorhan, muratt, ma5termind, forthright48, CherryTree. I would like to thank wanbo and malcolm for helping to prepare this round.

Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. I hope everyone will enjoy the contest.

Update: The contest is in 2 hours.

Score Distribution: 15-25-40-50-60-70-80-100

Edit: Rating updated!

Winners:

jqdai0815

FatalEagle

izban

I_love_Tanya_Romanova

Al.Cash

  • Проголосовать: нравится
  • +104
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Are there any penalties for wrong submissions?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    If two person gets same score, the person who reached the score first will be ranked higher. So, time of the last correct submissions and no penalties for wrong submissions.

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
Residents of the following countries and territories are not eligible to win prizes due to legal restrictions: Antarctica, Afghanistan, Belarus, Bouvet Island, British Indian Ocean Territory,Burundi, Cameroon, Central African Republic, Christmas Island, Cote D'ivoire, Cuba, Equatorial Guinea, Haiti, Heard Island and Mcdonald Islands, Islamic Republic of Iran, Republic of Iraq, Democratic People's Republic of Korea (North Korea), Lao People's Democratic Republic (Laos), Lebanon, Liberia, Libyan Arab Jamahiriya, Myanmar, Nigeria, Pakistan, Papua New Guinea, Serbia and Montenegro,Somalia, Sudan, Syrian Arab Republic, Yemen, Zimbabwe.

WAT? How is it possible that such civil countries as Serbia or Belarus ended up in this list? Is it a joke?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    Its not that we hate these countries in the list, there are some legal restrictions to send prizes in these countries.

    The world itself is a joke :(.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      Its not you, but your partners from US hate these countries in the list.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    It's not about how civilized it is.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    It is wrriten Serbia ad Montenegro, and that country doesn't exist :P

»
8 лет назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

Another great problem set, but this one felt too simple for such contest. Too bad I was so slow.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Glad to know that you liked the problem-set. This time we tried to make the problem-set a little easier than the last one. But may be another hard problem would be better.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Very nice problems. Though, I agree with Al.Cash that it was a bit too easy.

Do you consider breaking ties with an approximation problem? Something without known optimal solution. If not then are reasons technical? Yesterday, I've completely lost motivation after seeing 3 participants with full score. I would prefer an other system but the current one is fine.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for your feedback. I didn't expect so many top people in just after world finals. I agree that the problem-set was too easy for top people but at least it problems were nice :).

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

      What about the part with breaking ties? Any chance to see tie-breaker challenge in the near future?

  • »
    »
    8 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +79 Проголосовать: не нравится

    I personally don't really like the idea of tie-approximation problem (esp, for 24h contest (I mean not several days))

    • there are already such contests (codechef, hackerearth)
    • it makes you spent much more time for the contest (instead of solving everything and go away)
    • competition transforms from [solve algorithmic problems better(faster)] to [solve algorithmic problems somehow and really-compete in approximate problem] *
    • I personally can't into these problems:)

    *I don't say that it's bad per se, but if we want competition in solving approx.problem, let's create competition that consists of approx.problem

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Contest was interesting and good. For my opinion previous one was better, but also this is cool :) In last time, longer HR contests became my favourite in competetive programming.

I managed to solve first fourt tasks and sixth. I can not find bug in my seventh task. I tried several testcases and always everything is ok, but I got 0 points :(

My opinion about problems:

First task is easy, possible the easiest one which I solved in last 2 years :D

Second task is also good, nice idea, but for my opinion it is harder then third.

Third task, another constructive algorithm, for me it was interesting, but on previous round third task was much harder.

The fourth task, my favourite on the round. I spent a lot of time to solve it. Cool for that place !

I didn't read the fifth task, I saw big statement, I will do it later :)

Sixth task is good, I spent a lot of time to solve it. My solution in dp with Catalian numbers. I can not believe there is so many good submissions. I am interested whether some great coder can solve it in case when we have 200 square brackets and 105 parentheses ?

Seventh task, for me was easier than fourth and sixth. But I had some implementation bug. I done it with dsu + priority_queue + set. Sort all edges and add one by one and check whether we get answer for some query now. If someone has free time, please look at my code and suggest me what can be wrong : solution

Last task were easier than it should be, but I think nobody expected so many top coders in ACM week :P

My advices:

You should have easier second task, one more on level as 8th problem and the last thing you should put clear subtask in each statement. It is not very big job, but for all contestants it will be much better :)

See you on Week of Code, I hope another great problemset !

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are there any ideas for "Travel in HackerLand"? It seems to be more difficult than the last problem.

  • »
    »
    8 лет назад, # ^ |
    Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

    You need to binary search the answer for each query. To speed it up, you need to do these binary searches simultaneously.

    My Code

    Complexity: O(mlogm + logm(qlogq + nlog2n + m + qlogn))

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      You wrote loq instead of logq. It's O(N * log3(N)) bro, don't kill the latex :(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Iterate over roads sorted by cost. Find&Union with adding smaller CC (connected component) to larger one, to amortize complexity. For each CC also store (in "set" from STL) set of queries where both xi and yi are already in this CC. Such set of queries should be sorted by the required number of types of buildings. After merging two CC's you need to check the first query from the set (the one with the least required number of types of buildings) and check if maybe there are enough types of buildings now.

    My code (there is some small bug and it didn't pass 2 small tests. I resolved it by submitting it again with brute force, run if the input is small)

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I remember few informations when merging subtrees:

    • remember history of parents for each node and the minimum cost of edge which caused that merge — cM
    • for each merge resulting in increased number of types, in the root add the new number of types and cost of edge which caused that merge — cP

    I answer query online:

    • find first common parent of (x,y) — check the cost of that merge = cM
    • check each common parent and find first which got desired number of different types, compare the cost of that edge cP, with cM and print max

    More or less — I think answering query is O((log^n)^2).

    So the total complexity:

    time — O((n+q)(log^n)^2 + mlogm) memory — O(n lg n).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is there something better, than:

Y3log(X) + TY2log(X) in 6th task

q*sqrt(nlogn) in 7th tash

in 8th task?

  • »
    »
    8 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    6th: Y^3 + T * Y

    7th: NlogN

    8th: NLogN. I think problem 8th can even be reduced to O(n)

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

    I did the 8th task in O(n), using DP. Given the answer for v, we can calculate the answer for each of its children, using some values. If col[v] == col[par], ans[v] = ans[par]. Else ans[v] = ans[par] — A + B. A is the number of nodes in the subtree of v which can be reached from v without encountering any node of color col[par]. B is the number of nodes above v, which can be reached from par[v] without encountering any node of color col[v]. Hope this helps. :)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, actually the solution is how to count these A and B values? Which I didn't figure out.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 5   Проголосовать: нравится +23 Проголосовать: не нравится

        Okay. So, you can calculate both using the same parameter arr[]. arr[i] denotes the number of nodes in subtree of i reachable from i without encountering any node of color col[par[i]]. Initially arr[i] = subtree_size[i]. Now do a DFS. Whenever you're at a node v, find its most recent ancestor having same color (let it be a) and subtract subtree_size[v] from its immediate child which is an ancestor of v. At the end of the DFS, arr[] will have the necessary values.

        Now, regarding A and B. You can directly get A from arr[]. For B, find the most recent ancestor of node v which has same color, and then go to its immediate child which is ancestor of v. There you get the value of B. Also, the case when a node has no ancestor of same color has to be handled separately. I hope this makes it clear. :)

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks for the explanation :)

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks for the explanation. Wouldn't the solution be O(nlogn) due to finding ancestor of same color for every node.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            I believe you can remember the position for each color on the stack.

            So when you enter the vertex of color c, you add it to the stack S[c]. You also remove it from S[c] when you exit dfs.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Ah right. But that can again be reduced to O(1) using a method similar to how we found the nearest ancestor having the same color.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How to count the number of nodes in the subtree of v which can be reached from v without encountering any node of color col[par] in O(1)?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    There is an O(X + Y + TlogMOD) solution for the 6th problem.

    Related paper

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    There is a formula for 6th task. My solution looks like this

    int solve(int x, int y) {
        int n = 2 * x + y;
        int val = Comb(n + y, n) * (n - y + 1) % MOD * pmod(n + 1, MOD - 2) % MOD;
        return catalan[x] * val % MOD * factorial[x] % MOD * factorial[y] % MOD;
    }
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Can you please explain a bit about how you derived this?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        I started with counting sequences where parentheses and brackets are non-distinguishable.

        Then I noticed that if we fix some correct brackets sequence then we can insert parentheses sequences into it in 2x + 1 positions. In each position we can insert sequence of length li (Σ li = y), and there is catalan[li] such sequences.

        These considerations lead me to the easy dp to count number of ways to split y items into 2x + 1 groups, which could be computed in O(Y3logX) using matrix exponentiation. But it was too slow.

        Then I printed answers for different inputs and noticed that output is very familiar sequence: it was a catalan's triangle with well known formula to compute ;)

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I did the same, but I didn't recognize these values. Instead I noticed some pattern how to compute each cell in O(1) based on the 2 already computed cells.

          My algo was O(X*Y^2), after pattern notice reduced to O(X*Y).

  • »
    »
    8 лет назад, # ^ |
    Rev. 10   Проголосовать: нравится +15 Проголосовать: не нравится

    i did 6th in O(sqrt(N) * M * M + M * T) . Basic idea was dp(i, j) = number of ways to place J pairs of brackets in I slots . Answer is dp(2 * n + 1, m) * catalan[n] * factorial[n] * factorial[m]. This has complexity O(N * M * M). To optimize this i precalculate answer for all dp(N, m) where N = i * sqrt(n) for integer i and also dp(i, j) where 1 ≤ i ≤ sqrt(n) . With this precalculation takes O(sqrt(N) * M * M) time and each testcase takes O(M) time.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This trick is pretty amazing. There are so many unique solutions for each of the harder tasks of this contest :D

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится +30 Проголосовать: не нравится

The 7th task (Travel in Hackerland) can be done in O(NlogN) and we can process the queries online as well.

I built the reachability tree for each connected component of the graph.
Now a query (u, v, k) reduces to finding the lowest common ancestor of u and v that has  ≥ k distinct values in it's subtree. We can precompute number of distinct values for every subtree in the reachability tree in O(NlogN). Answering each query can then be done in O(logN) using binary jumping.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Editorials are available for all problems except the 4th question, please make it available. Thanks.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone explain the merging part of the 6th question in a bit more detail than in editorial?

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I can try:

    • We should notice that if you have X [] pairs, then you have 2*X+1 positions where you can insert () pairs:

    1 [ 2 [ 3 ] 4 [ 5 [ 6 ] 7 ] 8 ] 9 -> I showed 9 positions for the sequence [ [] [ [] ] ], which has 4 [] pairs.

    The number of such ways equals Cat[X], so now let's pick one and think in how many ways we can insert Y () pairs.

    We have Y () pairs and 2*X+1 positions to insert them. In each position you can insert between 0..Y pairs of () and the sum over all positions must be equal Y. Moreover if you decide to insert k pairs of () on one position, you can also do that in Cat[k] ways.

    So for example, you have 3 positions and 3 () pairs, you can insert them in the following ways:

    Cat[0], Cat[0], Cat[3]

    Cat[0], Cat[1], Cat[2]

    Cat[0], Cat[2], Cat[1]

    Cat[0], Cat[3], Cat[0]

    Cat[1], Cat[0], Cat[2]

    Cat[1], Cat[1], Cat[1]

    Cat[1], Cat[2], Cat[0]

    Cat[2], Cat[0], Cat[1]

    Cat[2], Cat[1], Cat[0]

    Cat[3], Cat[0], Cat[0]

    So now you have the following question: given Y pairs of () and 2*X+1 positions, compute the number of ways in which you can insert pairs into positions. And a lot of papers and formulas in this thread were devoted to explain how to compute this efficiently.

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Does anyone know how to get a T-shirt in Hackerrank? A month ago I won a T-shirt in another contest. However, it seems that the organizers have not informed me about the T-shirt.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I will use this subject to voice my opinion.

The problem I am seeing during Hackerrank contests is discussing different ideas/approaches of the problems during contest. It looks like nobody is actively monitoring that forum — people are asking about complexity, programming techniques used to solve the problem, etc. Even though during Week of code it is theoretically forbidden to post even test cases.

I also pointed that problem out to one of the task author during contest but there was no reaction. Would it be possible to actively monitor the discussions or disable them at all (not the best solution though)?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    This is one problem I am aware of. I agree that its very bad when someone posts a spoiler, corner case etc. I try to monitor the contests I manage but I can't monitor 24 hours. We will try our best to figure out a solution for this before the next contest.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +38 Проголосовать: не нравится

      Moderated comments maybe? So, comments are hidden by default and only a moderator can reveal them.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Maybe you can at least try to do something with this during current contest? People are describing the solutions in the discussions...

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +73 Проголосовать: не нравится

Yes yes I am jqdai0815.

»
8 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Is there anyone who hasn't got their BTC? Mine in April and May Codesprint one hasn't come.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Yep, still waiting for the May prize. And their support ignores messages.