Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

chokudai's blog

By chokudai, history, 5 months ago, In English,

We will hold AtCoder Beginner Contest 153.

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

We are looking forward to your participation!

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

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

What's wrong?

»
5 months ago, # |
  Vote: I like it -84 Vote: I do not like it

Who know how to do E?

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

Question E and question F can be done if you think about them.Come on!!!

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

I like this kind of "to simple contest", allways makes me feel like a champion!

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

How to solve Question E?? Thanks in Advance

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

    Making a 2d dp would solve the problem. It's just like the standard minchange problem.

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

    just simple Knapsack my submission

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

    Let's say the monster current health is H. You can try any of the nth spell( can cast multiple times), the magic points increased would be B[i] and the remaining health would be H-A[i]. Overall complexity would be O(H*N) .

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

      If I cast nth spell 4 times then the magic points increased would be 4*B[i] and remaining health would be H-(4*A[i]).

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

    You can use dp[health] as minimum spells required to decrease health to 0.

    Now as health has max limit of 10^4 and N spells as 10^3. You can iterate over each health from 0 to H and update your answer for dp[health].

    i.e the recurrence is :

    dp[health] = Summation_of_i_from_(0 to n)min(dp[health — a[i]) + b[i], dp[health]).

    i.e you check by including all spells and get the best one.

    Then, the answer is just dp[H].

    Submission

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

    If you're using python, O(H*N) (10^7) might be too much. Especially if you use a top-down memoized solution.

    Turns out you can prune some of recursive calls if you sort the spells by highest attack per mana cost and break early when the min stops decreasing.

    I can't prove that this is correct but it AC'd during the contest. Is it actually correct and if so can someone provide a proof?

    Python code: https://pastebin.com/rTLWJXba

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

how to solve F? anyone please.

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

Editorial By MrGary

A
B
C
D
E
F

All of my submissions. ( https://atcoder.jp/contests/abc153/submissions?f.User=Gary)

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

Surprised to see an easy F. Also my E passed, but I am using $$$H*10^4$$$ operations, which means $$$10^8$$$ operations in worst case. Was this intended to pass?

https://atcoder.jp/contests/abc153/submissions/9758669

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

    H = 10^4 N = 10^3 not 10^4 so O(10^7).

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

      No I am ignoring N. I am doing 10^4 operations compulsorily for each H. Though yeah, I think O(H*N) was the intended complexity.

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

        i know that at most we can do 4 * 10^7 iteration and the problem time is 2s so 10^8 / 2 * (4 * 10 ^ 7) = 1.25s so it should pass.

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

          That's 1.25 times the amount of time within which the solution the should pass and not 1.25 seconds.

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

          No, that's not how it works. My $$$O(H*10^4)$$$ solution finished off in 118 ms.

          https://atcoder.jp/contests/abc153/submissions/9758669

          You can easily do 10^8 very SIMPLE operations (which is applicable in this case) in 1 second, in C++ on almost any platform. Multiplication, Division and Modulus are heavy operations, may not work. But mine is simple comparison. Sometimes even 10^9 operations can pass in 1 second.

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

Can anyone explained more details how to solve problem E ? thanks in advance !

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

    U can use a single dp state. let dp[i] be the minimum cost required to make i tend to zero. so ur answer is dp[h].

    Now let there be an intermediate state j and i be the presesnt start then

    dp[i] = min(dp[i],dp[j]) + cost_required_to_reach_i_from_h.
    

    https://atcoder.jp/contests/abc153/submissions/9765139

    u can refer to my solution it's easy to understand

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

I couldn't solve E for 87 minutes and it was because I was so impatient, trying out greedy solutions that I assumed would work and not waiting or thinking long enough before I implemented.

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

    I didn't solve E too,and first I think it is greedy,after I looked the other's code,it is dp? :)

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

    Yeah same thing happened with me as well.

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

      here is my submission for the problem E , you can see my code for understanding.)

      #include <bits/stdc++.h>
      using namespace std;
      const int N = 1e3 + 10;
      
      struct node{
          int a;
          int b;
      }A[N];
      
      int H, n;
      int dp[10010];
      
      int main() {
          scanf("%d%d", &H, &n);
          for (int i = 1; i <= n; i++) scanf("%d%d", &A[i].a, &A[i].b);
          for (int i = 1; i <= H; i++) dp[i] = INT_MAX;
          dp[0] = 0;
          for (int i = 0; i <= H; i++) {
              for (int j = 1; j <= n; j++) {
                  if (i >= A[j].a) {
                      dp[i] = min(dp[i], dp[i-A[j].a] + A[j].b);
                  } else {
                      dp[i] = min(dp[i], dp[0] + A[j].b);
                  }
              }
          }
          cout << dp[H] << endl;
          return 0;
      }
      
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem F: Can someone please find what's wrong in this code? I have used two pointer to solve it.

int n,d,a;
cin>>n>>d>>a;
vector<pair<int,int>> v(n);
for(int i=0;i<n;i++)
cin>>v[i].first>>v[i].second;
sort(v.begin(),v.end());
if(d==0)
{
	int total=0;
	for(pii i : v)
	total+=i.se;
	cout<<total;
	return;
}
int d1=(v[0].se+a-1)/a,r=v[0].f+2*d;
int cost=d1;int ptr=-1;int i=0;
while(i<=n-1)
{
	if(v[i].f<=r)
	{
		v[i].se-=d1*a;
		if(v[i].se>0)
		if(ptr==-1)
		ptr=i;
		vis[i]=1;
	}
	else
	{
		if(ptr==-1)
		ptr=i;
		d1=(v[ptr].se+a-1)/a;r=v[ptr].f+2*d;
		cost+=d1;
		i=ptr-1;
		ptr=-1;
	}
   	i++;
}
cout<<cost;
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong in this solution of F?
link

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

As a monster, I feel violated by this round.

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

Submission

Can someone please explain why this times out even after using memoization?

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

    You have $$$O(NH)$$$ states. For each state you do $$$O(H)$$$ calculations, so the overall complexity is $$$O(NH^2)$$$, which is not feasible for the given constraints.

    You can calculate the answer for each state in $$$O(1)$$$, so the overall complexity will be $$$O(NH)$$$. Replace the while loop with:

    dp[i][h] = min(solve(h, i + 1, n), solve(h - a[i], i, n) + b[i]);
    

    solve(h, i + 1, n) indicates that we decide not to use spell i.
    solve(h - a[i], i, n) + b[i] indicates that we use spell i. Note, that we don't advance to the next spell yet, because we may want to use spell i several times, and this allows us to avoid using the while loop.

    Sidenote: It is actually possible to "squeeze" your solution. Notice, that if all a[i] were different, the total complexity would improve from $$$O(NH^2)$$$ to $$$O(H^2\log H)$$$, by the Harmonic series argument (see this or this). And for this problem it is possible to make all a[i] different, because for each unique a[i] we are only interested in the smallest cost b[i]. See this submission, which barely fits in the 2s TL with a couple of optimizations.

    Edit: I just realized that the complexity of the second solution is probably $$$O(H^2\log H)$$$ rather than $$$O(NH\ log H)$$$.

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

Why does this solution to problem F fail?

I reckon that there is no problem with the main part...

Link

Maybe it's the sqrt decomposition part? I copied it from a template...

(The complexity is $$$O(n\sqrt{n}\log n )$$$, should be able to pass...)

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

    In your binary search you don't seem to be using mid variable. Maybe the check's supposed to be m[mid].x <= atkrange?

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

HOw to solve the question F ???

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

Am I only one here solve F using Segment Tree? Is it overkill?