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

Автор gritukan, история, 2 месяца назад, По-английски,

(Idea — sender , developing — timgaripov)

Tutorial is loading...

(Idea — Chmel_Tolstiy, developing — -__-)

Tutorial is loading...

(Idea — Zlobober, developing — halin.george)

Tutorial is loading...

(Idea — GlebsHP, developing — -__-)

Tutorial is loading...

(Idea — glebushka98, developing — gritukan)

Tutorial is loading...

(Idea — Elena Andreeva, developing — gritukan)

Tutorial is loading...

(Idea — Zlobober, developing — malcolm)

Tutorial is loading...
 
 
 
 
  • Проголосовать: нравится  
  • +68
  • Проголосовать: не нравится  

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

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

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

I have a simple solution for D. It has complexity O(NlogNlogX), but can be applied when (1000, 2000) bigger, and changing bonus function.

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

    Could you please explain the logic behind your solution?

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

      Assume we need to check if X is enough. Iterate a the number of whole cash paying for 1000. Clearly, we should pay b = (X - 1000 * a) / 2000 times for 2000. And We should do it for first a 1000 and first b 2000, each position we set values to 100/200. The remaining position are filled with their negative cost. Finally, add X - 1000 * a - 2000 * b to first position. If the minimal prefix is non-negative we know X is enough.

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

Can someone link to the classical problem referenced in D? I can't seem to easily find it on Google.

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

In Div2-A, when n is even, won't the answer be the opposite of what you have written? If n is divided by 4, the answer should be n/2-1 and n/2+1.

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

Div2 C can be solved with DSU which is faster

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

    Your solution isn't faster, you sort the numbers and that's the same complexity as the proposed solution.

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

Thanks for a fast and well explained Editorial....

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

How does Div2C greedy approach work? We can create a bipartite graph with the left vertices as initial times and the right vertices as final times and an edge with the weight of the cost. It is a classic assignment problem. What condition in this question reduces the problem complexity making the greedy solution optimal?

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

    Call q is a heap contain planes can depart at time t (k + 1 <= t <= n) then the plane depart at time t will be the plane with the largest c in curent heap. And go on... we will have an optimal solution. Sorry for my bad English.

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

    Let me try it. Consider we have a set of planes yet to leave. Now, if we choose ith plane to stay from our current set, we incur a penality of Ci. And we want this penality to be minimum. Now think about it and you will understand.

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

      Let's say at some point we have two planes x and y with cx = 2, cy = 5. Intially x is supposed to depart at 4 and y is supposed to depart at 3. Currently we are at 5th time unit. The total cost if we choose x first will be 2 * (5 — 4) + 5 * (6 — 3) equals 17. If we choose y, it will be 5 * (5 — 3) + 2 * (6 — 4) = 14. But the minimal penalty is given by cx at 5th time unit. That is not leading to the optimal solution. Correct me if I am wrong.

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

        I don't understand you. What we want is minimum cost and we will get it by taking cy cost first because it is bigger, and as you say this is optimal.

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

          "We will show that following greedy is correct: let's for each moment of time use a plane, which can depart in this moment of time (and didn't depart earlier, of course) with minimal cost of delay." Does this not mean that the plane x gives us the minimal cost?

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

            I am having trouble understanding the editorial. But the solution i mentioned in first comment is correct. You can refer to my solution if it helps.

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

I think there is a mistake in the second solution of A. In line 2, it should be b=(n/b)+1; not b=(n/b);

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

Can anyone please explain the solution of problem 853B - Jury Meeting more?

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

Can someone explain DIV2B.I didn't get the idea from the explanation in the editorial

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

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

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

In problem Div2D, you say that: "Obviously, each member of the jury needs to buy exactly two tickets — to the capital and back." Does it mean that two jury members can't fly in the same plane? o.O

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

    EDIT: we7d right, they obviously can't — silly me ^_^

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

      they can't because only one member in each city and flights are only from city x to city 0 and vice versa

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

        Thx for answer, now it's much simpler task.:D Previously I thought that flights like 1 10 8 5000 and so could exist. Silly me :(

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

My same solution which passed during system testing if I submit again now gives TLE. Is it that system testing servers are better or any other reason.

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

can someone explain the greedy proof in div2 C could not understand it from editorial like in this statement "Let x be plane with minimal cx, such ax ≠ bx. At any moment greedy algorithm takes avaliable plane with lowest cx, so ax < bx. " what is the proof for ax<bx.?

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

    I think there is a better explanation. You can think about this, how to get the best answer? Supposing that we have an initial arrangement, how to optimize it. First of all, we will come up with an idea to swap some planes' departure time. If plane i departs at ti, plane j departs at tj, then the cost of them two is ci * (ti — i) + cj * (tj — j) = ci * ti + cj * tj — ci * i — cj * j, and ci * i — cj * j is a constant. So our goal is to minimize ci * ti + cj * tj, and it's obvious if ci > cj, ti > tj, we should swap ti and tj. So for every moment t, we should choose the highest cost from those who can take off at this time. And this is my code.http://codeforces.com/contest/853/submission/30136836

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

In Div1C : can anyone please elaborate how to find the number of points in the query rectangle efficiently?

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

    Try persistent segment tree, where root[i] represents the root of segment tree for all elements having a row <= i.

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

      You can also solve the queries offline and you won't need persistent tree.

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

        can you please explain how we can answer the queries offline?

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

          Sort the queries and marked squares from left to right(column),and use segment tree to maintain it.When adding a suqare(i,p_i),add 1 to p_i in the segment tree,and you can find the answer when asking a query.

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

Div 1 B can be easily solved in linear time.

  • Fix a window [l, r] of size K. Then all the jury must go to city 0 before time l and must return to their cities after time r.
  • So let's find L[i] = minimum cost of making all jury travel to the capital at time i or less and R[i] = minimum cost of making all jury return to their cities at time i or later. Since all times are  ≤ 106, we can keep a list of flights for each time. First, go in increasing order, processing flights and keeping the minimum value for each jury as well as the total minimum cost. Then do the same, but in decreasing order of time. All this process is linear.
  • Once we have calculated L and R, we simply try out all possible windows [l, r] of size K. The cost for a fixed window is L[l - 1] + R[r + 1]. Checking all windows is also linear.
»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

In Div1-D, what is "next after i interesting day"? Did you mean "the interesting day next after i"?

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

Spent two hours to debug 1C, just to find out that p[i] is supposed to be row p[i] column i instead of row i column p[i]...

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

is there any explanation about "2d-tree" or whatever you use to reach O(q·logn) complexity in 1C/2E ?

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

    Yes, actually with a 2D Tree, you get O(Q * log2N). To reach O(Q * logN), you can use an approach similar to sweep line supported by a BIT. The process would be as follows.

    • Sort the queries by top row.
    • Process queries from top to bottom row by row. For each row, do the following in order: Query the BIT for every query in this row, add column of this row to BIT. To query the BIT, consider we're at row i, and we're processing query (i, j1) -  > (i2, j2), then we'll query the BIT in the range (1, j1 - 1) (squares up and to the left of query rectangle) and in the range (j2 + 1, N) (squares up and to the right of query rectangle). Since we only add the column of a row once we've processed all queries of that row, and since we're processing rows from top to bottom, we know that all data in the BIT will be from rows above the current one.
    • Sort the queries by bottom row now and do the same as in previous step but this time from bottom to top.
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone provide a formal proof that Div2C accepts a greedy solution? for instance, using a matroid?

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

Опять русские авторы и английские разборы?

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

in Div1-C I tried persistent segment tree to solve the queries in O(n*logn)

but I failed at test 4 , any help or hint please code

UPD : problem solved , I had to swap rows and columns from the input ...

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

Why is Div1C offline search O(qlogn)?I think it should be O(qn)process time and O(1) query time.

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

http://codeforces.com/contest/854/submission/30213879 Please help,why runtime error on testcase 49,although allocated memory properly :(. Thanks

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

Can anyone please explain Div2-D/Div-1 B. I'm not able to understand much from the editorial.

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

I can't understand the proof for Div. 1 D. Why is it always optimal to have x_i <= 3000?

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

854 B
Please Explain this part.
Otherwise, if k > x, assume that apartments with indices 2, 5, 8 and so on are occupied, so any room has at least one inhabited room adjacent to it. Therefore number of good apartments is equal to number of vacant apartments and is equal to n - k.

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

    One neighbour can cover two adjacent apartments. If there are more than x occupied apartments, one can divide the apartments in groups of 3 and assign them to the middle of each group (hence the 2 in 123, 5 in 456, etc.)

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

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

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

Actually Div.1 C can be solved in O(q log^2 n) and get Accepted...

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

    haha you're right, I have just changed oset for a vector and got accepted