chokudai's blog

By chokudai, history, 3 months ago, In English

We will hold AtCoder Beginner Contest 188.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +62
  • Vote: I do not like it

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

[After contest]

How to solve D?

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

    First i calculated ans by taking service for each day(c[i])

    then i calculated for how many days i will be paying x amount of cost using prefix sum technique(Prefix sum using maps).

    Then working smartly i store cost for day intervals(like x to y) in a data structure.

    Then simply calculated if using C yen from day x to day y is useful or not.

    for better understanding see this code below https://atcoder.jp/contests/abc188/submissions/19339488

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

      Nice Explanation

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

      Instead of that initial C consideration for all days, if we try and add min(interval*c, interval*cost) to the answer, it gives WA. why is that? I dont get how they're different? WA AC

      Sorry for the wrong link. lol. WA this is the right one.

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

        I think in WA you are paying C yen more than 1 time for same days. Check in your input loop.

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

          Thanks, i got it. It was because, mp[prev] (that is the cost) could be 1e14 and interval could be 1e9. So that caused an overflow. We can avoid this because c ia at most 1e9. So if we consider c instead of a huge sum, it won't overflow.

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

E was easier than D . How to solve D and F ?

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

    To solve D, I use Sweep-Line algorithm

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

    for D I use coordinate compression,

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

      I understood the sweep-line solution , Could you please explain how coordinate compression can be used to solve the problem ? Or share your submission ?

      If it's similar to the one given here isn't it same as sweep-line ? We are adding and subtracting from index (which are mapped to larger values and thus it can be said that they are "compressed") but it's same as adding and subtracting in map and traversing through it.

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

    D seems pretty standard iteration over all discrete point boundaries and since for each range the minimum answer is the same for each day, we can add its range * minimum answer for the range to the final answer.

    For F, I came up with this solution : Decide how many multiplication operations one will use (iterate on it, because it's max around log2(y/x) +- 2, say 'i' is the pointer). Now if we use these many multiplications, subtract contribution of original value * 2^(i) from the final required value. Now take the absolute value of the difference. We now need to arrange subtraction and addition operations in the original multiplication operations so as to make difference = 0 while minimizing total operations. Here we an observe that if we move optimally, there are at max 2*i + 1 distinct values that will be assumed by the difference if we start reducing from the highest bit. You can understand it like this : We either just reach the particular value or just exceed it using our difference operations at every bit. It doesn't make sense to go too far from the given difference. We can find these by taking modulo of difference, say m, with (2^j) making m and (2^j) — m as the optimal values for all j from 0 to i. Now we can run a dynamic programming from these values to get the minimum answer for i as dp[difference] + i. Minimum over all i is the required answer.

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

How to solve problem D?

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

    Push the start/end of each service into a priority queue sorted by day, go from lowest to highest, keep track of current sum of separate fees and you can calculate Ans += min(sum, prime fee) * elapsed days

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

      But how to judge that there are multiple services at the same time?I think it may cause time limited error.But I think you have better way to solve this problem,could you tell me ? Thank you.

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

    Put beginnings and ends into one array and sort by their time (keep track to which interval they belong to and whether they are start/end of the interval). Then scan along this array and compute the current price for one day. This price holds for the whole interval from the current processed event (beginning/end of interval) to the previous event. Of course, instead of this price, we can choose the price C (the whole subscription). So we add the chosen price multiplied by the time since the last event to the result.

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

how to solve F?

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

how to solve D ??

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

Can someone tell me if what I'm doing for F here is right or wrong? I'm passing 48 out of 49 cases

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

    What is your logic?

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

      I was basically working with the closest differences of x with y if we keep multiplying x by 2. But its wrong, this would miss some cases

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

    Try this one: 1 47. The answer is 7 = (1x2+1)x2x2x2x2-1

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

I am getting one test case wrong in D. My Code Please let me know that case.

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

    I was also getting the same verdict which was due to the integer overflow. Try to look for that.

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

      Got it, thanks.

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

        Suppose N is given 1e5 and all the ranges are starting from 1 and ending at 1e9 with the value of 1e9.

        Total number of days = 1e9

        Value of cost each day = 1e9 * 1e5 = 1e14

        So total cost = days * cost per day = 1e9 * 1e14 which is the reason for integer overflow

        So what you should do-

        take min(cost each day, c) whose max value can only be 1e9 which is the max value for c.

        Now total cost = 1e9 * days = 1e9 * 1e9 = 1e18(max)

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

          Thanks a lot, but i did figure it out some minutes ago. xD

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

Anyone please help me in my submission of E my submission

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

    Your DFS doesn't seem to be working in linear time. For example, consider

    1 2
    1 3
    2 3
    

    Let's say your DFS starts from 1, then visits 3. Then it will backtrack to 1, and visit 2. Then your DFS again visits 3, even though it is already visited. So this can time out for large graphs.

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

      is there any way to fix it? ( because i think we have to see by backtrking is there any good option availiable. so if we use vis array it cant be fixed)

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

        Try not to go to the same state again, if a state is visited use the already computed value for the state. In my case a state holds the max value of all elements from that state to end. You could do something similar

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

          thank's alot for helping me out in this : )

          May Codeforces be with u

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

            Or just use dijkstra instead of dfs

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

              Dijkstra also requires to record the already visited vertices, so it's essentially the same, I think

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

I tried my best to solve E, but I can't. Can anyone give me a hand?

Here's my submission

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

    Try to solve with Dijsktra's Algorithm. There are better solutions but using Dijkstra works for this

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

Only one test-case is failing for D, can anyone figure out the mistake?

https://atcoder.jp/contests/abc188/submissions/19339643

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

    long a=pc*d;

    long b=k*d;

    This line is causing use WA due to interger overflow. Try to do —

    long val = min(pc, k) * d;

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

C was very easy but , question statement was very confusing , am i only who feels like this or really it was confusing.

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

    It's funny. Cause I first read the statement and sure not able to solve it then try to match the test cases in a rough implementation expecting WA and it works

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

For E, I tried finding the maximum value in subtree of a node and tried that value with current node value. Why is it wrong? Can someone explain please?

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

    One possible bug is if you include node into its subtree, but Example #3 should rule this out. Also if you use dfs for a subtree max and don't use dp then you get quadratic solutions which TLEs. Other possible bugs include wrong initialization of dp (for example, initializing best answer to 0 instead of -inf or initializing subtree max to something nonzero).

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

      Thanks for reply :) . Sadly I couldn't find anything among them :( . Here is the submission in case needed.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        At least two mistakes

        You should use min in dfs, not max,

        and then you need arr[i] — values[i], not values[i] — arr[i]

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

          Why though? Wouldn't I want maximum selling price for current node? Also, isn't selling price equal to values[i]-arr[i](Selling Price — Cost Price) ?

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

          Nope, you are talking about a different solution with 'reversed' graph.

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

            Well, True, I solved it with the reversed graph and didn't think there was another approach, my bad

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

        If you have edges $$$1 \to 3$$$ and $$$2 \to 3$$$ then $$$3$$$ is in subtree of $$$2$$$ but you won't go to this subtree because $$$3$$$ is already visited after processing $$$1$$$. Lines 16 and 17 should be outside of the if statement. Got AC: https://atcoder.jp/contests/abc188/submissions/19358632

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

    If by sub-tree you mean all nodes reachable from current node , then your logic is correct , there must be coding mistake . Usually sub-tree word we use in case of tree but that was not the input .

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

      Yea. Sorry about that. U r right.I meant nodes reachable from current one.I linked my submission above.

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

I ignored in E that Xi<Yi, so I tried to implement using bfs (and dfs, too).

The idea is, to find the minimum possible buying price foreach vertex, and collect the max diff of each vertex price minus the minimum price. But that failed for all implementations. What is wrong with that aproach?

Example, dfs: https://atcoder.jp/contests/abc188/submissions/19357783

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

    You need to reverse the edges to calculate values starting from the selling point (largest numbers)

    If you do it your way, you can loose some values on the way

    say roads are 1->3->5 and 2->3->6

    If you start from 1, you will update values for 3 and 5 from 1, values from 2 will never reach 6 because 3 is already visited

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

      The idea is that the value from 3 will reach 5 if it is better than any value reached 5 before.

      In the case above, that would be that a[3]<a[1] and a[3]<a[2].

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

        Say a[2] < a[1] < a[3] < a[5] and the roads are as above

        And you start your dfs from a[1]
        You visit a[1]->a[3]->a[5], then you visit a[6]
        How would a[2] reach a[6] if a[3] is already visited?

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

          I allways visit all childs where the minimum of all previus values is bigger that the current value.

          This means, for the smallest price I traverse the whole subtree, for bigger prices I do not traverse a subtree a second time, if the first time the min price was smaller than the second time.

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

            Yeah, you're right...

            Failed to get this idea initially

            Though it should degrade performance of dfs and it will not be linear anymore if you can visit same nodes multiple times

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

              Yes, my last try would most likely TLE because of this. However, some of my previous attempts used a priority_queue, which basically makes that each vertex is traversed at most once.

              But in all implementations I considered 0 to be the smallest answer possible.

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

    If i am not wrong , your submission is failing on (input format same as question) :

    3 3 2 1 100 1 3 2 3 1 2

    Answer is 99 , yours give 98 .

    Because in your DFS solution , vertex 3rd is not taken into account when you are at vertex 2nd .

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

      spookywooky , in-fact your solution works on same graph if i reorder the edges in input i.e it's gives 99 on following input : 3 3 2 1 100 1 2 1 3 2 3

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

    Ah, ok, found the problem.

    "buy 1 kilogram of gold at some town, traverse one or more roads, and sell 1 kilogram of gold at another town."

    So, like the examples say, the result can be negative. I did not consider that.

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

      Not a very good wording in my opinion btw
      If you don't look at all the examples, it is natural to think that if you cannot get positive delta, you just don't buy the gold. They should've emphasized it

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

      Should've looked at the samples :D

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

        I did... after the contest ;)

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

          Sorry for counter-example above , probably i ran solution of comment above yours.

          Your solution is giving WA , even after initializing ans = INT_MIN , so what was the final issue ?

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

            I allways considered to sell at the same city as bought, so my min ans is allways 0, never negative.

            Maybe in the one or other submission there was other bugs, too, but the main reason for failing was this.

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

              ok,it was mentioned "traverse one or more roads" , thus we can't sell at same city . I also missed that at first reading.

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

Can anybody give a test case for which my solution is failing. It is failing only on one test case (random_25) Link Edit: Found the mistake (interval * hope[i].second was too big to fit in long long

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

Solution for D :

Like we do Range update query on array in O(1) Reference We will apply this thing using a map because we can't take array as constraints are big for array size.

My Solution

We increase the m[start[i]] with c[i] and decrease the m[end[i]+1] with c[i] so as if we traverse from the start we can take sum of values in m. We will store the previous day as you can see in my solution. So now our question comes to whether we will take subscription or not for days=it.F-prev.F.

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

Solution for E :

My solution

For each node we store a high[i] ( it represents the highest a[i] in the cities reachable from i). We can do this using simple DFS. Now for each city we can take current city as the city where we buy our gold and in high[i] we have the city that is reachable from current city, we will sell at the city that has maximum value. We will now take all cities and their child cities and update our answer as ans=max(ans, high[it]-a[curr]).

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

    We bought the gold from city say (i), now we don't sell at the same city, that's why we will be looking at the child of current city for selling.

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

My E is failing on two test cases. Can someone help me? Submission

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

    ckmax(maksi[s], a[s]);

    You assume that you can sell at the same city as you bought, but that is not the case, you can only sell in another city.

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

      I think I considered that case. I "split" the graph into two parts such that somewhere in the left part we bought gold and somewhere in the right we sold gold. I split the graph on the edges. (Left part is the left side of the graph when we delete the edge and the right part is the right side of the graph when we delete the edge.)

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

        You maintain two dps, max price per vertex you can get if bought at that vertex, and min price you can have paid if sell at that vertex.

        But for both dps you must not put a[i] at position i into mini[i] or maksi[i], because you cannot sell for a[i] if you have bought at i.

        Does the third example works with your code?

        And btw, you do not need that "split". The max/min diff you find in one of mini or maksi you will also find in the other one. It is enough to check the max selling price or min buying price foreach vertex, no need to check both.

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

          Yeah, the third example works with my code. You got my dp definition wrong. I defined dp (mini) as the minimum value we can get if we "split" the graph at the current node (including and that node). That dp is the left side. The same goes for maksi, but it shows the maximum value. This is the right side. In the end, I overcomplicated my solution, but I am trying to find the mistake. Thank you for trying to help me.

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

For F I understand that if y is even and the optimal answer is going to have a division operation then it is optimal to perform division right now. If y is odd then try both y-1 and y+1. It suggests that after at most 2 operation value will be halved. This way the height of the recursive tree will be log(y)=~60

I tried a few examples and it seems the number of states at each height is not growing very fast because of collision

Is there any tight upper bound for the number of states at each height and overall states in the tree?

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

My Submission

For problem E

I think of it as a DAG

And then dp on top

Why is my solution incorrect

Is there anyone who can help me

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

I found a counterexample to my accepted code (https://atcoder.jp/contests/abc188/submissions/19346819) for F.

On test case "1 1243", my accepted code prints 16, but the correct answer is 14, as witnessed by the following path: "(((1*2*2+1)*2*2*2-1)*2*2*2-1)*2*2-1"

The issue is that my code does not correctly compute the shortest way to make a number using positive and negative powers of 2; I thought the only issue is that you can replace blocks of ones with 2 operations (a positive and a negative power) but actually the situation is more subtle...you can make 11011011 with only 4 operations (not 6)

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

Implementation of the official editorial solution for problem E: SUBMISSION (commented as well)

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

Can someone please explain what is wrong with my code for problem E? I am getting WA on one pretest

Here's the link

https://atcoder.jp/contests/abc188/submissions/19426526

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

Why is this algorithm not working? Problem — D

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

    The first and/or last intervals are not calculated proper. Consider the first interval starts at day 10. Then you add 10*something to the solution, what is not correct.

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

I did the D problem base on the tutorial. and instead of using

	for (int i=0;i<n;i++)
	{
		cin >> a[i] >> b[i] >> c[i];
		mapp[a[i]] += c[i]; mapp[b[i]+1] -= c[i];
		s.insert(a[i]);s.insert(b[i]+1);
	}
	d = vector <long long > (s.begin(),s.end());
	long long temp=0;long long res=0;

I use


for (int i=0;i<n;i++) { cin >> a[i] >> b[i] >> c[i]; mapp[a[i]] += c[i]; mapp[b[i]+1] -= c[i]; d.push_back(a[i]);d.push_back(b[i]+1); } sort(d.begin(),d.end());

i thought it was right but somehow i got WA for 15 testcases pls help :<

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

can any one help me in finding my mistake in problem E peddler?? here is my solution https://atcoder.jp/contests/abc188/submissions/19482465

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

In Problem E, My 4 test cases are failing, my approach = dfs+memoisation. Please help me. **https://atcoder.jp/contests/abc188/submissions/19881794**