PikMike's blog

By PikMike, history, 3 weeks ago, translation, In English,

1251A - Broken Keyboard

Idea: BledDest

Tutorial
Solution (Ne0n25)

1251B - Binary Palindromes

Idea: adedalic

Tutorial
Solution (adedalic)

1251C - Minimize The Integer

Idea: Roms

Tutorial
Solution (Roms)

1251D - Salary Changing

Idea: Roms

Tutorial
Solution (Roms)

1251E1 - Voting (Easy Version)

1251E2 - Voting (Hard Version)

Idea: Roms

Tutorial
Solution (Roms)

1251F - Red-White Fence

Idea: Ne0n25 and BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

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

in c tutorial what does thirst means ?

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

    I think it's first rather than thirst.
    Maybe just another typo...

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

Can someone please explain the DP solution of E1?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Sort all the voters in the order of non-decreasing values of $$$m$$$

    Let $$$dp[ind][team]$$$ store the minimum amount of money you need to spend to make first $$$ind+1$$$ voters vote for you, when already $$$team$$$ number of voters are voting for you. So our final answer will be stored in $$$dp[n-1][0]$$$.

    Now let's see the transitions from $$$dp[ind][team]$$$

    • if $$$ team+ind>=voter[ind].m $$$ then it is possible that in the future, we'll be able to take him for free, move to $$$dp[ind-1][team]$$$
    • just pay him $$$voter[ind].p$$$ and then move to $$$dp[ind-1][team+1]$$$

    value of $$$dp[ind][team]$$$ will be the minimum of all these three. For our base condition, when we have only one voter to consider $$$(ind=0)$$$, then we'll have to either pay him or not, depending on the number of voters we currently have with us.

    The 1st transition works because, that state will be filled only when all of first $$$ind$$$ voters have agreed to vote us.

    Implementation: 63362330

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

      Actually, you don't need the first transition at all. Taking a voter for free is covered by the second transition, and cases when team value for some states is larger than needed are handled by the nature of DP automatically. You only decrease the number of extra votes by paying the voters (as in the third transition).

      The successful submission of your code without the first transition http://codeforces.com/contest/1251/submission/63500118

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

      could you explain why team + ind > voter[ind].m means its possible to take said voter in the future ? I don't understand that part.

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

Can someone please help me finding bug in my solution for the problem E2. It's giving WA on test case 3, the test case is really large so I'm not able to find out which input is giving WA.

Link to my code

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

    may be you need lower_bound instead of find, and totalcost+=cheapest.f for adding the cost

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

My approach for F is very dirty. (I gave up to code this)

Let's make some definitions:

  • $$$R$$$ is the height of red board.
  • $$$Q$$$ is the query number.
  • Let's define unique whiteboard which whiteboard has unique height.
  • Let's define non-unique whiteboard which is whiteboard but not unique whiteboard.

Suppose there are $$$x$$$ unique whiteboards and $$$y$$$ non-unique whiteboards, and you picked $$$x_{1}$$$ unique whiteboards, $$$y_{1}$$$ non-unique whiteboards once and $$$y_{2}$$$ non-unique whiteboards twice. ($$$0 \le x_{1} \le x$$$, $$$0 \le y_{1} + 2 y_{2} \le y$$$)

Then you have to satisfy this formula: $$$target = \frac{Q}{2} - R - 1 = x_{1} + y_{1} + 2 y_{2}$$$

Since $$$y_{2}$$$ non-unique whiteboards should be at both side, the side of $$$x1$$$ and $$$y1$$$ boards only matters. So there are $$$2^{x_{1} + y_{1}}$$$ cases in state $$$(x_{1}, y_{1}, y_{2})$$$.

Now for $$$y_{2} = [1, 2, 3, \ldots, \frac{target}{2}]$$$, calculate number of possible $$$(x_{1}, y_{1})$$$ pairs, and add it. And you have to apply dirty casework to calculate this fast.

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

How to prove Monotonicity in D?

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

what if we get a mid such that only mid < l is there for all salary ranges, since that will be an invalid median how do we check that we should go higher or lower?

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

    the ans must large or equal than the median of all salary's li

    so you could calculate the value of median of all salary's li ,then start binary search

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

What's the dp sol of E1?

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

I cannot find a way to prove the correctness of gready algorithm in E2. If we are considering voters with m = i, and we need more voters with m >= i. Suppose that we pick a voters with m = x, so the need of additional picking of this voter before may be not neccessary. I don't know how it can effect to the process of greedy?

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

    let's notice to the inverse iteration of i. If we are considering voters with m=i, we can still use voters with m=x>i because those voters (with m=x>i) were inserted into the multiset before (in the order of iteration) and notice that if they are not chosen to pay money, they will be still in the multiset. HUST student!

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

In E2, when pref[x] + cnt < x we can buy additional x−pref[x]−cnt votes or buy all the members of the group x. But in the solution buying all the members of group x is not considered. I don't understand why. Can someone explain please?

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

    because the limit mi is 0<=mi<n

    so we could leave a person for every mi ,and the person would vote since the vote number of other person is great or equal than mi

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

    If we are considering $$$m_i=x$$$, the number of $$$m_i=x$$$ is $$$s$$$, the number of $$$m_i<x$$$ is $$$p$$$.

    First people whose $$$m>x$$$, we have already considered it, denote $$$y=m$$$, obviously $$$y>x$$$ and $$$p+s+cnt\ge y$$$

    Consider $$$x$$$, $$$need=x-p-cnt$$$

    $$$s-need=s-x+p+cnt=y-x>0$$$ so $$$s>need$$$

    Proved.

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

In E why is this strategy wrong? we choose the minimum m value each time having maximum price. Then we try to buy people such that cnt(no of people that have been voted for us till now) becomes greater than current minimum m value choosen. We'll buy diff = min(m)-cnt cheapest people i.e. we choose diff people from remaining set of people having minimum price. I'll maintain two multiset for it. One with comparison on m value first and other with price. Moreover, I could understand what editorial is trying to say but the accompanying code doesn't seem to do the exact same thing that has been explained.

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

Problem D has a greedy tag on it. Can anyone please provide a greedy solution?

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

in problem D, could someone help me find out what will happen if $$$mid$$$ is not in any salarie $$$[l_i, r_i]$$$? Thanks! :)

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

    mid > ri ---> The salary of people must less than median

    mid < li ---> The salary of people must large than median

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

C no is a very nice problem ...

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

Can someone explain me the solution to c problem

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

    Since you cannot swap two adjacent odds or even digits, make two separate lists one for odd and other for even digits in the order in which they appear in the original string. Now when we merge these two, compare the elements from odd and even lists since they can be swapped. We maintain the order in which the digits appear in their respective lists.

    Python solution: 63358004

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

Could someone please explain problem D solution? I am having a hard time getting the editorial.

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

    I can explain my solution which is similar. I'm assuming you know about binary search and sorting.

    Let $$$ok(mid)$$$ be a function that returns:

    -1 if $$$mid$$$ is impossible to make as a median because it is too low.

    0 if $$$mid$$$ is possible to make as a median in some way.

    1 if $$$mid$$$ is too big to make as a median (there isn't enough money).

    Then we can binary search $$$mid$$$ to find the maximum such that $$$ok(mid)$$$ returns $$$0$$$.

    How will the function $$$ok$$$ work? Assume that we will assign the number $$$mid$$$ to some interval. Also, let initially $$$k = s$$$ from the statement (the total money). Subtract $$$mid$$$ from $$$k$$$, since that's the cost to assign the number $$$mid$$$ to the interval that will be the median. We can put the $$$i$$$-th interval $$$[l_i, r_i]$$$ into 1 of 3 groups:

    1. $$$r \lt mid$$$: the number we assign must be smaller than $$$mid$$$ (no other choice). Let the count of these numbers be $$$cntsmall$$$. Also, since we want to use as little money as possible (greedy), might as well assign $$$l_i$$$ to this number. Don't forget to subtract that from $$$k$$$.

    2. Those with $$$l \gt mid$$$: the number we assign must be bigger than $$$mid$$$ (no other choice). Let the count of these numbers be $$$cntbig$$$. Do the same stuff as with the previous group.

    3. Those with $$$l \le mid \le r$$$: for these numbers, we will choose whether we assign a number less than, equal to, or more than than $$$mid$$$ (whether they will be "before" or "after" $$$mid$$$ in the sorted list of numbers).

    Now, if $$$cntsmall \gt \lfloor n/2 \rfloor$$$ or $$$cntbig \gt \lfloor n/2 \rfloor$$$ we can't use $$$mid$$$ as a median because we must always have exactly $$$\lfloor n/2 \rfloor$$$ numbers left and right of the middle element (the median). So return $$$-1$$$ if there are too many bigger numbers ($$$mid$$$ is too small), or $$$1$$$ is there are too many smaller numbers ($$$mid$$$ is too big).

    If everything is alright, then we need to assign numbers to the intervals from the 3rd group.

    From the first group (smaller numbers), we need to assign $$$\lfloor n/2 \rfloor - cntsmall$$$ numbers (The first $$$cntsmall$$$ numbers were forcefully assigned, now we care about the remaining numbers). Since we want to minimize the cost, we should sort all intervals so that their $$$l$$$ is increasing, then assign $$$l_i$$$ for the first $$$\lfloor n/2 \rfloor - cntsmall$$$ of these numbers (again, by assigning we mean subtracting that number from $$$k$$$, the total money remaining).

    From the second group (bigger numbers), we need to assign $$$\lfloor n/2 \rfloor - cntbig$$$ numbers. Since they will come after $$$mid$$$, they need to be bigger or equal to $$$mid$$$. Obviously, it's best to use as little money as possible, so we assign $$$mid$$$ to all of them, so the total cost for this part is just $$$mid * (\lfloor n/2 \rfloor - cntbig)$$$.

    Now, all intervals have been assigned a number. If $$$k \geq 0$$$, then we had enough money to do it, so return $$$0$$$. If $$$k \leq 0$$$, then we didn't have enough money, or in other words $$$mid$$$ was too big, so return $$$1$$$.

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

Can someone explain E2 solution better? I don't understand the two cases, and also why we iterate from x=n-1 to x=0.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Excuse me for interrupting you.

I think the Tutorial of Problem D may have something wrong.

The ok function has two return values.

if(need > v.size()) return false;

It is because var mid too small.

return sum <= s;

It is because var mid too large.

So how to keep monotonicity?

May someone help me? Thanks for your kindness.