Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### chokudai's blog

By chokudai, history, 5 weeks ago, ,

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!

• +56

 » 5 weeks ago, # | ← Rev. 2 →   +2 What's wrong?
•  » » 5 weeks ago, # ^ |   0 No problem now
 » 5 weeks ago, # |   -84 Who know how to do E?
•  » » 5 weeks ago, # ^ |   +31 The contest hasn't finished, I suppose.
•  » » » 5 weeks ago, # ^ |   +12 When ppl take advantage of an easy contest.
 » 5 weeks ago, # | ← Rev. 2 →   -20 Question E and question F can be done if you think about them.Come on！！！
•  » » 5 weeks ago, # ^ |   -55 does E need backtracking ?
•  » » » 5 weeks ago, # ^ |   +40 No comment during the game.
•  » » » 5 weeks ago, # ^ |   -21 Correct soln is — Soln of Ehere
•  » » » » 5 weeks ago, # ^ |   0 XD
 » 5 weeks ago, # |   0 I like this kind of "to simple contest", allways makes me feel like a champion!
 » 5 weeks ago, # |   0 How to solve Question E?? Thanks in Advance
•  » » 5 weeks ago, # ^ |   0 Making a 2d dp would solve the problem. It's just like the standard minchange problem.
•  » » 5 weeks ago, # ^ |   0 just simple Knapsack my submission
•  » » 5 weeks ago, # ^ |   0 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 weeks ago, # ^ |   0 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 weeks ago, # ^ |   0 Yes
•  » » 5 weeks ago, # ^ |   0 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 weeks ago, # ^ | ← Rev. 2 →   +1 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 weeks ago, # |   +29
 » 5 weeks ago, # |   +4 how to solve F? anyone please.
 » 5 weeks ago, # | ← Rev. 9 →   +12 Editorial By MrGary Acin>>h>>a; cout<<(h+a-1)/a<=h the answer is "Yes"else "No" CJust greedy.use the Special Move only on the k monsters who have the biggest Hi.and the answer is the sum of the rest monsters' Hi Dconsider a tree like this:now you can see that the answer is the number of the vertex of the tree Edp[j] means that if the health of the monster is j , the minimum cost .(if the health is <0 , j=0)consider the i-th spell :use dp[j] to update others.dp[max(0,j-a[i])]=min(dp[max(0,j-a[i])],dp[j]+b[i])Answer is dp[0]Total O(H*N) FFirst sort all the monsters according to Xi.Clearly , to kill the left most monster(the first monster) we must use the bombs (h[i]+A-1)/A times .In order to attack more monsters ,we must let the left end point of the array be x1 .Then consider the second ,third ...But when considering the i-th monster,we must know how how many attacks he has faced before.And update its health.To do this we need make some marks(Where a bomb array end).When meeting a mark the previous attacks will minus this.We can use Binary_Search to make the marksTotal in O(nlogn)!All of my submissions. ( https://atcoder.jp/contests/abc153/submissions?f.User=Gary)
•  » » 5 weeks ago, # ^ |   +10 You give others a link of "my submissions" and will turn to our own submissions!
•  » » 5 weeks ago, # ^ |   0 When you are too excited to post editorials #me
•  » » » 5 weeks ago, # ^ |   +1 ？
•  » » 5 weeks ago, # ^ |   +5 This would be the link to all your submissions: https://atcoder.jp/contests/abc153/submissions?f.User=Gary
•  » » 5 weeks ago, # ^ |   0 Your submission link will direct everyone's personal submission. Can you provide the link differently?
•  » » » 5 weeks ago, # ^ |   0 Fixed now.
•  » » 5 weeks ago, # ^ |   0 can you tell me what is wrong in my solution. https://atcoder.jp/contests/abc153/submissions/9768886
•  » » » 5 weeks ago, # ^ |   +3 Might be that priority queue gives you the largest element by default
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Oh got it, i wrote the comparator wrong. Thnx
•  » » 5 weeks ago, # ^ |   0 can you elaborate on how to implement the binary search part
•  » » 5 weeks ago, # ^ |   +3 F can be solved in O(N) solution
•  » » » 5 weeks ago, # ^ |   +1 The standard library sorting algorithm is O(N log N), not O(N).
•  » » » » 5 weeks ago, # ^ |   0 yeah because of sorting, but no need for binary search
•  » » » » » 5 weeks ago, # ^ |   0 Ah, I see. I thought you were saying you found a solution that is O(N) overall
•  » » » 5 weeks ago, # ^ |   0 thanks I got it now
•  » » » 5 weeks ago, # ^ |   0 Can you explain how it works?
 » 5 weeks ago, # |   0 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 weeks ago, # ^ |   0 H = 10^4 N = 10^3 not 10^4 so O(10^7).
•  » » » 5 weeks ago, # ^ |   0 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 weeks ago, # ^ |   -6 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 weeks ago, # ^ |   +6 That's 1.25 times the amount of time within which the solution the should pass and not 1.25 seconds.
•  » » » » » » 5 weeks ago, # ^ |   0 I don't get that.
•  » » » » » 5 weeks ago, # ^ |   +3 No, that's not how it works. My $O(H*10^4)$ solution finished off in 118 ms.https://atcoder.jp/contests/abc153/submissions/9758669You 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 weeks ago, # ^ |   0 Aha i got that thanks for this information.
 » 5 weeks ago, # |   0 Can anyone explained more details how to solve problem E ? thanks in advance !
•  » » 5 weeks ago, # ^ |   0 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/9765139u can refer to my solution it's easy to understand
 » 5 weeks ago, # |   0 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 weeks ago, # ^ |   0 I didn't solve E too,and first I think it is greedy,after I looked the other's code,it is dp? :)
•  » » 5 weeks ago, # ^ |   0 Yeah same thing happened with me as well.
•  » » » 5 weeks ago, # ^ |   0 here is my submission for the problem E , you can see my code for understanding.) #include 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 weeks ago, # | ← Rev. 2 →   0 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> v(n); for(int i=0;i>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<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<
 » 5 weeks ago, # |   0 What's wrong in this solution of F? link
•  » » 5 weeks ago, # ^ |   +6 line 38 and 41 use 'd' instead of 'a'
•  » » » 5 weeks ago, # ^ |   0 Thanks :)
 » 5 weeks ago, # |   +3 As a monster, I feel violated by this round.
 » 5 weeks ago, # |   0 SubmissionCan someone please explain why this times out even after using memoization?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 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 weeks ago, # ^ |   0 Thanks
 » 5 weeks ago, # | ← Rev. 2 →   0 Why does this solution to problem F fail?I reckon that there is no problem with the main part...LinkMaybe 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 weeks ago, # ^ |   0 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 weeks ago, # ^ |   0 Fixed, it failed one more case.
 » 5 weeks ago, # |   0 HOw to solve the question F ???