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

Автор dalex, 7 лет назад, По-русски
  • Проголосовать: нравится
  • +147
  • Проголосовать: не нравится

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

Do we have the solutions for these problems?

if not, can anyone tell me how to solve problem L :) Thanks.

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

    Do 3 BFSes. Let G be the graph formed by the dependencies and G' be the same graph, with all its edge inverted. (changed direction)

    Now, note that each correct labelling must "meet" at some point u (This may include 0, a or b), so the answer is the minimum possible value of this over all possible u :

    Distance from 0 to u in G + Distance from a to u in G' + Distance from b to u in G'.

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

      Is it guaranteed that the graph formed by dependencies is a connected one, or at least that A and B are in the same connection component?

      If so, could you please tell me where it is mentioned/implied? Thanks)

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

        you can find this description in the Input section.

        It's guaranteed that it's possible to acquire all (n+1) talents given the infinite number of talent points.

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

          Well, for instance, if we take a graph with no edges at all, wouldn't it suit this condition? We will be able to acquire all the skills, and we would only need 2 points to directly purchase A and B.

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

            You might have misunderstood the problem but you looks smart because you tried to understand the statement carefully. Maybe, you've thought you can immediately get some skill which doesn't have any skills need to master in advance.

            But here is a description which can correct your understanding.

            A talent can be acquired only if a character has at least one of the talents it depends on.

            If a skill has no skill it depend on, you can't satisfy the condition "at least one of talents..." and you can't get the skill. Such a case violates the constraints.

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

              Understood it now, thanks a lot! :)

              I thought exactly like you wrote before) Didn't consider this sentence restrictive while reading the problem description.

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

      I tried doing a downward DFS from 0 storing at every node the minimum distance to A below it in the DFS tree, minimum distance to B and minimum distance to both A and B (means the no. of skill points needed to get both A and B if we have the current node.)

      For a given node n, a_val[n] = min(a_val[child] + 1) for all children of n. b_val[n] = min(b_val[child] + 1) for all children of n. ab_val[n] = min(ab_val[child] + 1) for all children of n.

      if(a_val[n] + b_val[n] < ab_val[n]) ab_val[n] = a_val[n] + b_val[n];

      The answer is in ab_val[0]

      The code is given below Solution Link

      Could anyone please tell me why it's failing? (Test Case 18)

      Thank you

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

    im

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

    up

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

What about D?

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

    This is a max flow problem. A similar problem has appeared before ( Kyoto University Programming Contest 2016 — Problem E ), the difference is that the squares are weighted, we only need to block one square and we have to provide a certificate.

    I've explained the solution in the link above. The only modification needed is the capacities of each square (change it to the respective weights). To construct a possible solution, we just have to find the minimum cut.

    My code : here (I've used min cost flow as initially I thought that min cost flow is needed, but it turns out that max flow is sufficient)

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

Can you please tell me the solution of B and C?; I got WA in B, and RTE in C;

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

    Problem C: Call the output array res[]. For all number a from 0 to p-1, we calculate b = a^2 % p. Then res[b] = a.

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

    B: Sort all dragons by (a — b), then do simulation from the end: imagine you have zero warriors at the beginning, then you fight dragons in sorted order, and after each fight you resurrect some warriors. If you don't have enough warriors, add some to be able to fight next dragon (you need (a — b) warriors to fight dragon because we're resurrecting warriors, not killing them).

    There's some reasonable explanation why it works: if we sort dragons by amount of warrioirs needed to fight them, then total amount of warriors after all battles with dragons in sorted order will be minimal, it's greedy algorithm. Try represeniting dragons as oriented segments from a to a — b in number line to see why it works.

    Well, I actually had more reasonable explanation when I was solving this problem, but that was 1.5 months ago and I already forgot it :D

    My solution: http://pastebin.com/snwTke9g

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

Официальный разбор задач на Youtube:

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

Can anyone share the proper solution to question K?

During the contest, I observed that the answer is independent of rotation, and scaling the initial distance by a factor of D increases the safe area by D^2. Since the case for distance 1 is given in the test case, I just multiplied the squared distance between the dragon and the palace by 0.916297857297023. It works, but is highly unsatisfying.

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

    It seems like 0.916297857297023 came from but idk why this is the answer either.

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

    What you described was an intended solution.

    Jury got the answer using this article: https://en.wikipedia.org/wiki/Radiodrome and some binary search and numerical integration. It calculates 7 correct digits in 1 second.

    There is also a math solution, here is a document (in Russian, but you should be able to read formulas): https://yadi.sk/i/-BcFxkTry7mZm

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

      That's actually slightly "bad" question setting (in a twisted sense), since technically the sample solution could only be correct to 10e-6 absolute error (hence not 10e-6 relative error) and larger solutions would WA (We would need to guess slightly more and slight less than the sample solution for 100% confidence of AC).

      Thankfully, it seems the sample solution is correct.

      Thanks for the links as well :)

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

what is the solution procedure of problem G?

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

    Scanline. Events are: zork and axe. Sort all events by weight (for zorks weight is minimum axe weight they need), then go by events in reversed sorted order (from biggest weight to smallest). Maintain a set where you store curvature of all avaible axes. When you meet axe, add it to the set. When you meet zork, give him axe of minimum avaible curvature he can take (in other words axes.lower_bound(zork.curvature). Try imagining all events as points (x: weight, y: curvature) on coordinate plane to see why it works.

    My solution: http://pastebin.com/j7JtgWZu

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

      I came up with the same solution but It's RTE on test 24

      can you find what the bug on my code

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

Thanks for your contribution man~ !

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

Problem K. I think it's rare problem where if you do not know solution, you can use the answer of 1st test to generate other answers. And Jury can't hide answer to test 1, because they must show a least one. E.g. 22061070

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

    Solution "multiply answer from sample by square of distance between two points" was intended by jury. Read dalex comment above.

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

Can you give me a hint for problem A ?

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

what is the test number 6 for H? I got 6 times wa for this.

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

Solution for I and J please. Thanks

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

    I: find vertex of minimum degree and place policemen in all verticles except vertex of minimum degree and its neighbours.

    J: every time a[i] > a[i-1] it means that there're a[i] — a[i-1] photos beginning at building i. So you have to find sum of max(a[i] — a[i-1], 0) for all i = 1..n (a[0] = 0)

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

How to solve M?

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

    Simulate a direct elimination table with the n people. Every time you get i < j, store i in the vector of all people that lost against j. When you only have one guy left, then you now it is the guy with the highest rank. This needs n-1 queries.

    Then, simulate another elimination table with people that lost against the guy with the highest rank. This needs O(log(n)) queries. Therefore, you will always need strictly less than n+24 queries.

    Note that, if you search for the guy with the highest rank naively, than the second part may need O(n) queries in the worst case, which is not good.

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

Can anybody tell me how to solve problem H or give me some tests? I still got wa on test 6.

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

    Let tab[i] the number of '('s that are necessary in the first i characters in order to get a valid sequence, then compute t[n], tab[n-1], ... tab[1] (this is actually dynamic programming).

    Then, using this array, replace '?'s greedily from left to right in the sequence.

    Then, check whether the resulted sequence is valid or not.

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

Can anybody give me some tests on H's test 39? I get WA on it...

The algorithm is quite like that of noelnadal's. But I do not know what is going on...

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Problem H, test 39
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me why problem B we have to sort a-b descending order ?

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

How to approach F?

My fail attempt
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    F
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry for necroposting, but could I have a solution for problem L, really thanks!