fcspartakm's blog

By fcspartakm, history, 5 weeks ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +37
  • Vote: I do not like it

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

First of all thanks for the tutorial,

But I can't get problem C, I don't understand why looping from 0 to w will guarantee finding a solution(if it exist)

I got this observation " The crucial observation is that d wins give us the same amount of points as w draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving p points (if it is not greater than n, we can just lose all other matches) " but I can't understand the rest.

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

    Let x be # of wins, y be # of draws, z be # of losses.

    We need to prove that if there is a solution where y >= w, there will be a solution where y < w.

    When y >= w, we exchange w draws with d wins. The total points remains the same (from the observation), and we do not overshoot the limit as x'+y' = (x+d)+(y-w) = x+y-w+d < x+y <= n. Thus this will also be a solution.

    So if we keep exchanging w draws for d wins, we will eventually end up with a solution where y < w and we cannot exchange further.

    Now that it is proven, we can say that if a solution exists, a solution will exist where y < w. Similarly if there are no solutions where y < w, there are no solutions.

    Thus, we search y from 0 to w-1 to find a solution, and if we cannot then there is no solution.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      If you want to input $$$\geq$$$,you can just input:


      $$$\geq$$$

      (only one $)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am still not able to understand how did you proved that if there does not exists solution for y<w then there will no solution.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Since we proved that if a solution exists, a solution will exist where y < w, it is equivalent to saying that if there is no solution where y < w, a solution does not exist. (This is the contrapositive of the first statement)

        Proof: Assume otherwise: there is no solution where y < w but there is at least one where y >= w. However, we can say that will be a solution with y' = y-w, since (w draws = d wins + w-d losses) in terms of points. We can then also say that there is a solution where y' = y-2w, and so on until we have a solution such that y' < w.

        Hope this helps.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why can't we do the same for x instead of y?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is because it is optimal to have less draws and more wins, but not the other way round. Wins give you more points than draws.

        So we can constrain the number of draws, but not the number of wins, as the number of wins can be as large as n (10^12).

»
5 weeks ago, # |
Rev. 3   Vote: I like it -44 Vote: I do not like it

solution of problem E(translated by google translate)

The only mid-range question in this competition.

Obviously greedy.

Sort the series first.

To make the minimum value in a series +1, you need to +1 each of the minimum values in the series; to make the maximum value of -1 in the series, you need to have a maximum of -1 for each of the series. ——mangoyang's comment on XJOI (not this question)

Now let's categorize the discussion:

  • If the remaining number of operations is sufficient: compare the smaller values of the difference between the left and the right, select a smaller operation

  • If the number of remaining operations is not enough, select an operation with fewer numbers on both sides.

In a total of four cases, the code is a bit annoying, be patient

In addition, if the number of times is stable, it will output 0 directly.

code:

62540846

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

    I think you should put all the codes in a spoiler. That will reduce the size of the comments.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -45 Vote: I do not like it

      It is sorry that I don't know how to use spoiler,so i use link.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not really able to see why E is greedy.

    Suppose k was 20 and we have the following frequency table

    1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 10 7 -> 10

    Wouldn't greedily first reducing 7 and then reducing 6 be worse than increasing 1, 2, 3 and 4

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it -38 Vote: I do not like it

      Because my English is not very well,I don't quite get your question.

      greedy means "choose the less cost one that can influence to the answer"

      In fact,you can see the example 1:


      4 5 3 1 7 5

      reducing 7:1 3 5 6

      reducing 6:1 3 5 5

      increase 1:2 3 5 5

      increase 2:3 3 5 5

      then,whatever you do,the $$$Maxnum-Minnum=2$$$

      so the answer is 2

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

      You will decrease or increase whichever group of numbers in top or bot that have less quantity (just compare top and bottom groups).

      10<16 so go from top: "1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 20" now 16<20 so go from bot but because 16>k (k is 10 now) we can't do anything and program terminates.

      Python code: 62526246

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried something similar during the contest but failed. My idea was to compare which side was cheaper, but it did not work. Can somebody point out what is wrong with this logic?

    62484346

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you should first compare which cost less,then compare $$$k$$$ is enough or not.

»
5 weeks ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

solution of problem G(translated by google translate)

This is one of the four best questions (ABDG) that can be done in this competition.

Simple construction

Since the output order is independent of the correctness of the answer, we assume that one of the two sequences of the output is in the order from $$$1$$$ to $$$n$$$.

We find a property: the sum that can be made by the permutation is $$$[\sum_{i=1}^n i,\sum_{i=1}^n max(i,n-i+1)]$$$

So the output of $$$<\sum_{i=1}^n i$$$ $$$-1$$$, $$$\geq \sum_{i=1}^n max(i,n-i+1)$$$ is a fake example 2 output

Now the range of $$$k$$$ becomes $$$[\sum_{i=1}^n i,\sum_{i=1}^n max(i,n-i+1))$$$

Construction method:

Set the current unfilled interval to $$$[L,R]$$$, and fill in $$$R$$$ if $$$\leq k$$$ after $$$R$$$ is filled in, otherwise fill in $$$L$$$

code:

62537353

»
5 weeks ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

solution of problem F(translated by google translate) a bit late,sorry!

The harder one of the two questions (CF) in the competition

We found a property: if the consecutive $$$k(k \geq 2)$$$ colors are the same, then their color will not change.

Then, it will only change type like $$$\dots BWBWBW \dots$$$.

Every time you change, the left and right ends will become the final color, and the other middle will become a different color($$$B \rightarrow W,W \rightarrow B$$$).

Then we can simulate directly.

The time complexity of the simulation is $$$O(min(n,k))$$$

why?

For each operation (time complexity is $$$O(1)$$$), it must change the value of two characters, and each character changes at least once.

Code:

62554014

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

The greedy for E:

The idea is to sort the array, and start with the initial maximum difference, and try decreasing it while we have operations left.
We need only 1 operation to decrement answer by one, if we increment the leftmost number. We can keep incrementing it until it becomes equal to the next number. After that, we need 2 operations (increment both of them) to decrement answer by one, and so on.
The same is symmetrical for the right side too.
So, we greedily move towards center from both ends together, minimizing the answer at each step.
62586395

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had come up with something similar, and it seemed to work on whatever examples I could find, but I can't prove correctness. Could you prove intuition on how I would go about proving this is always optimal? Thank you.

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

      Look at it like this,

      1) let's agree that it's always your best choice to either increase the minimum number or decrease the maximum number since those are what bring you your result.

      2) does it matter if you choose to increase the minimum by one or decrease the maximum by one ?

      • the answer is No since both will make the final answer decrease by one

      3) so now we're at the point where we must choose to either increase the minimum or decrease the maximum what will be my greedy choice is the number or occurrence of each

      say we have 5 5 7 8 9 9 9 9

      If we choose to increase the minimum we will need 2 moves to decrease the final answer by 1 ( 1 for each 5 )

      If we choose to decrease the maximum we will need 4 moves to decrease the final answer by 1 ( 1 for each 9 )

      hence it's always optimal to choose the once with the minimum number of occurrence

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

Please someone explain me how to solve Problem C using Linear Diophantine Equations.I read this Comment but his ans is not clear to.

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

    From extended gcd we get (x0, y0) such that ax0 + by0 = g = gcd(a, b). We then scale this to satisfy ax + by = p; x = (p/g)x0; y = (p/g)y0

    We can now shift our obtained solution to (x + kb', y - ka') where a' = a/g and b' = b/g [you can verify this]

    Now we have 3 inequalities:

    • x >= 0 or k >= -x/b'
    • y >= 0 or y/a' >= k
    • x + y <= n or k >= (x + y - n)/(a' - b')

    Just pick a k which satisfies all the inequalities or return -1.

    ---
    Keep in mind that scaling will lead to an overflow in cpp. We can overcome this using the fact that there's a solution with y < w' from the editorial.

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

How is the solution gauranteed to have minimum cost?? Problem D

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

Can someone please take a look at my code for problem D. I can't figure out why is giving runtime error. 62637783 or wa

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

I am new in trees. How can we implement D? Please help.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you are using c++ then tree/undirected acyclic graph can be represented as array of vectors. if tree contains n nodes represent it as vectorvec[n+1]. to make the n-1 connections in the tree number=n-1; while(number--) { ll int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } for more basic info refer to hackerearth theory section regarding graph.

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

Editorial for F?

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

What is s in the Staircase problem?

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

fcspartakm editorial for f ?

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

Why L or R must belong to the same array. Can someone explain it in more detail.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How'd you go about implementing D?

Assume you've initially marked the last edge of the input with 2 colors, how do you find which vertex to run the DFS on? Anyone got their solution they could link me to? Would be p cool

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, " The crucial observation is that d wins give us the same amount of points as w draws" i didn't get this. Can someone please explain?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a very peculiar doubt in question C.

I got the part "_The crucial observation is that d wins give us the same amount of points as w draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving p points (if it is not greater than n, we can just lose all other matches_"

But why are we comparing y ans w to get the solution?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, if i am doing the same thing for x =0 to d-1 then why it is giving WA? It should be correct ?

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

has anyone implemented problem D with the second approach told in the tutorial?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem E's editorial, can someone explain the 2nd para with an example ?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    consider sample:

    10 12
    1 2 3 6 7 8 9 13 14 15
    

    2nd paragraph tells you that if there is answer that reach $$$(min, max) = (4, 12) = (L, R)$$$ then there are same amount of numbers that you need to increase, so there are also answers $$$(3, 11)$$$ and $$$(5, 13)$$$ but among them are those with $$$L$$$ or $$$R$$$ from input array. Now, other sample:

    9 11
    1 2 6 7 8 9 13 14 15
    

    Think of $$$(L, R) = (4, 12)$$$ again. It require $$$5+6 = 11$$$ to make it. It's not optimal because there are two numbers that we increase, and three that we decrease, so we can move $$$L$$$ and $$$R$$$ up by one to $$$(L+1, R+1) = (5, 13)$$$, so each decreasing number will need one step less, and each increasing number will need one step greater. So, total difference will be $$$\# L - \#R$$$, where $$$\#L$$$ is number of increasing numbers, and $$$\#R$$$ is number of decreasing numbers. And, because $$$\#L < \#R$$$ this difference is negative, so result will be better. It was requiring 11 and $$$\#L - \#R = 2 - 3$$$ so it will require $$$10$$$. By anology, if $$$\#L > \#R$$$ you can change to $$$(L-1, R-1)$$$.

    And... of course in this case $$$(4, 12)$$$ is not answer, because this is reason why answer must have one of bounds if amount of increasing and decreasing numbers are not equal. If they equal, then answer may have bounds from initial array or not, but there is always answer that has $$$L$$$ or $$$R$$$ from initial array.