### bharat.khanna.cse14's blog

By bharat.khanna.cse14, 2 years ago, ,

Hello Codeforces,

Manthan, Codefest 17 will take place on Sunday 24th September, 2017 20:05 IST with a duration of 2.5 hours (tentative). The round is rated for both Div1 and Div2 participants and consists of 7 problems.

The Department of Computer Science and Engineering is conducting Codefest from 22nd-24th September. Manthan (मंथन in Hindi, meaning Brainstorming), the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

The round is prepared by bharat.khanna.cse14, ayush24 and divyam.

We express our heartiest thanks to KAN and gritukan for their help in preparing the contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

## Prizes:

Overall 1st place: INR 25,000 Overall 2nd place: INR 18,000 Overall 3rd place: INR 12,000

1st place in India: INR 10,000

1st place in IIT(BHU) Varanasi: INR 4,000 1st place in freshman year, IIT(BHU) Varanasi: INR 1,000

About Codefest: Codefest is the annual coding festival of the Department of Computer Science and Engineering, IIT (BHU) Varanasi, which is held online and is open to participation by all! Register on the Codefest website now! Total prizes worth ₹400,000/- up for grabs with events covering domains from Math, Machine Learning, Natural Language Processing and Capture The Flag style competitions. Go to the Codefest website to find out more!

UPD1: The scoring distribution is 500-1000-1500-2000-2500-3000-3500

UPD2: System testing has been completed. Following are the winners of the contest:

1. anta

2. moejy0viiiiiv

3. tourist

4. Shik

5. LHiC

Best in India:

rajat1603

UPD: The editorial for the first 4 problems has been posted. We will update the editorial of the rest 3 problems soon!

Announcement of Manthan, Codefest 17

• +178

 » 2 years ago, # | ← Rev. 2 →   +49 7 problems in 2 hours?!UPD: Contest extended.
•  » » 2 years ago, # ^ |   -35 Maybe it's like Div 2A, Div 2B, Div 2C/1A, Div 2D/1B, Div 2E/1C, Div 1D and Div 1 E?
•  » » » 2 years ago, # ^ |   0 I think they should extend the contest a bit. 2 hours and 30 minutes would be better I think.
•  » » » » 2 years ago, # ^ |   +72 Why so many downvotes? I just said my opinion!
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   -42 Well the users are about to be crazy.Codeforces users' attitude to comments :Useful: Ok, upvote for him, it's nice to me.Useless: DOWNVOTE!_(It's not harmful to me and not useful,So why upvote?)_
•  » » » » » 2 years ago, # ^ |   -29 ignore these shit tards my friend.
•  » » 2 years ago, # ^ | ← Rev. 2 →   -43 1
•  » » » 2 years ago, # ^ |   0 this is the best comment in the whole thread. Why are people downvoting it gvaibhav21?
 » 2 years ago, # |   -26 This contest will consist of lots of mathematical problems. This is speciality of Indian contests. Brush up your maths skills to perform well. :)
•  » » 2 years ago, # ^ |   0 YEEEEEEEEEEEEEESSSSSSSSSS!!!
•  » » » 2 years ago, # ^ |   0 What a handle!!
•  » » » 2 years ago, # ^ |   -6 Biri keno? Gorib naki
•  » » » » 2 years ago, # ^ |   0 Ha bhai. :'(
•  » » » » » 2 years ago, # ^ |   -9 Hey nigga naga :|
•  » » 2 years ago, # ^ |   +6 Codefest'17 is excited to present a mathematical programming contest — Mathmania. It will bring a delectable collection of problems which will be an absolute delight for all the mathematics geeks. Cash prizes worth INR 50,000.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -26 Thats nice to hear, because Maths is good for health.
•  » » » » 2 years ago, # ^ |   +38 It's bad for the health of my rating though
•  » » » » » 2 years ago, # ^ |   -21 Yeah same here brother, I have been trying since a year to reach that dark blue area of expert.
•  » » » » 2 years ago, # ^ |   0 because Maths is good for health.You look healthy,I think.(just a joke
 » 2 years ago, # |   -23 Can people currently not enrolled in college participate and compete for prizes? :P Just asking for clarification as the post doesn't put any restrictions!
•  » » 2 years ago, # ^ |   +11 Anyone can participate and win the overall 1st,2nd and 3rd prizes. Same is true with the best in India prize.
 » 2 years ago, # |   +15 Where can I find the tasks of past years of machine learning and cyber security contests?
•  » » 2 years ago, # ^ |   +26 These are the links for the previous year's machine learning and CTF contests.Also, this year's CTF event has already started and can be found here.This year's machine learning and NLP events will also start soon.
•  » » » 2 years ago, # ^ |   +12 it seems last year's machine learning problems are not available, also registering for CTF is closed
•  » » » » 2 years ago, # ^ |   +27 Last year's Machine Learning problems are only visible to registrants of the contest. I think it is some error on Hackerearth's side. Registrations for CTF are open again. You will be able to register now.
•  » » » » » 2 years ago, # ^ |   +14 it seems registration for CTF is not working, sign up button is not responding in particular.I did some investigation and it seems the POST request initiated by ajax technique when I press sign up is getting error 500
•  » » » » » » 2 years ago, # ^ |   0 If name field gets red after sugn up button, just try to login. it worked for me Even tho I never got "successful registration" or email of any sort.
 » 2 years ago, # | ← Rev. 3 →   -115 Is it rated?
•  » » 2 years ago, # ^ |   +5 The round is rated for both Div1 and Div2 participants and consists of 7 problems.
 » 2 years ago, # |   -31 It is hard to belive that 7 problems for 2 hours... Ok. We will do this. :D
•  » » 2 years ago, # ^ |   -11 Manthan, Codefest 17 will take place on Sunday 24th September, 2017 08:05 IST with a duration of 2.5 hours (tentative).
 » 2 years ago, # |   -12 Hope it'll be a nice round, and no math and geometry.Wish everyone high rating.
•  » » 2 years ago, # ^ |   +16 And it must be XD.
•  » » » 2 years ago, # ^ |   0 regular trainings will improove your skill, just try your best
•  » » 2 years ago, # ^ |   +3 well every one cant have high rating ...
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Well..... Didn't the announcements always wish every one high rating?Maybe I said something wrong o(╥﹏╥)o.
•  » » » » 2 years ago, # ^ |   -9 thats just an impossible thing :) only happens if every one gets the exact same score which is impossible
•  » » 2 years ago, # ^ |   -32 I won't post any comment taking about the future contest.Every time I post such comments I got TONS OF DOWNVOTE!!!!!!!
 » 2 years ago, # | ← Rev. 2 →   +32 When I saw IIT BHU's event, I was expecting praran26 as one of the problem-setters.
•  » » 2 years ago, # ^ |   -22 praran26 Fandom!!
 » 2 years ago, # | ← Rev. 2 →   -49 contest prepared by IITians.
 » 2 years ago, # |   -52 Is this contest rated?
•  » » 2 years ago, # ^ |   +5 Sometimes we should enjoy the process of the game rather than care about the rating...
•  » » » 2 years ago, # ^ |   +105 Some people enjoy contests because of the learning opportunity, some want to be the best in the long-term ranking, some compete just for fun. I don't see why anyone //should// anything :PThat said, Ctrl+F "rated".
 » 2 years ago, # |   -28 My First Rated Contest. All the best to Indian Guys. Your Prime Minister is very aggressive. Namo Namo !
 » 2 years ago, # |   0 The time in the link text is incorrect it should be 20:05 IST, not 08:05 IST.
•  » » 2 years ago, # ^ |   0 Thanks! I have updated it.
 » 2 years ago, # |   -46 The university is next to my home and currently facing students protest for a girl's molestation , i hope they don't do in the contest :D
•  » » 2 years ago, # ^ | ← Rev. 144 →   -23 .
 » 2 years ago, # | ← Rev. 3 →   -77 Sorry!!!
 » 2 years ago, # |   -21 gl hf
 » 2 years ago, # |   -23 The contest duration is 2.5hrs but the banner says 8:05 pm — 10:05 pm. It should be 8:05 pm — 10:35 pm.
 » 2 years ago, # |   -27 Where will this contest be held?
•  » » 2 years ago, # ^ |   -15 On the best platform ever — codeforces. :')
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -8 Ah ok — what page will I navigate to to compete? EDIT: Found it
 » 2 years ago, # |   -37 No doubts all IIT guys knows problems...
•  » » 2 years ago, # ^ |   0 Even if they did, it won't matter. Cause they won't be able to win. :D
 » 2 years ago, # |   -9 It is 13 minutes before the contest starts and I cannot register. I says "Registration Completed". Shouldn't registration complete 5 minutes before contest?
•  » » 2 years ago, # ^ |   +16 That means you already registered
•  » » » 2 years ago, # ^ |   0 LOL I realized that five minutes in when it let me enter submit code tab./╲/( ͡⎚ ͜U ͡⎚)/\
 » 2 years ago, # |   +14 Scoring?
 » 2 years ago, # |   -46 Is it rated ?
•  » » 2 years ago, # ^ |   +31 Your comment is rated.
 » 2 years ago, # |   -36 I know that all of the problems are about religion
 » 2 years ago, # |   +54 Is it really Div1 + Div2? Seems like just Div1 xD
•  » » 2 years ago, # ^ |   +3 In B, Did you applied DP ? It smells like DP.
•  » » » 2 years ago, # ^ |   +7 No need for dp.You need to try all a[i] as a coefficient for q value. Once you have chosen a[i] * q you need to take the best a[left] for p value and take the best a[right] for r value.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 This is all I did. Find maxes for each p multiplied by each array item  q multiplied by each array item  r multiplied by each array item and return the final sum. One test kept failing. Did we have to return sum%(10^9+7) or something?
•  » » » » » 2 years ago, # ^ |   0 No. p<=q<=r. So You Should keep in mind that if q != p then you can't use r if r <= p.
•  » » » » » 2 years ago, # ^ |   0 Doing that won't ensure that you chose i <= j <= k when building sum a[i] * p + a[j] * q + a[k] * r. One of the right solutions (I don't know if there are more) is Pixar's above.
•  » » » » » » 2 years ago, # ^ |   0 missed this. so naive.
•  » » » » » » » 2 years ago, # ^ |   0 me too lolthat's why test case three didn't work i think
•  » » » » 2 years ago, # ^ |   +19 Precomputing the best a[left] and a[right] is DP!
•  » » » » » 2 years ago, # ^ |   0 Is it dp? int sum = 0; for (int k = 1; k <= n; k++) sum += k; 
•  » » » » » » 2 years ago, # ^ |   0 Yes you can call it dp, since to calculate the sum upto index 'n' you have used the sum upto index 'n-1' which in turn uses sum upto 'n-2' and so on. This is only what defines dp..
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 In some sense yes. But even if you say no. I'm sure that you don't compute the best a[left] with a for loop for each a[i]. This will get you TLE. I cannot see your solution yet, but I'm sure you precomputed all best a[left] and a[right] values. And that is DP.
•  » » » » » » » 2 years ago, # ^ |   0 What about this one? int sum[n + 1]; sum[1] = 1; for (int k = 2; k <= n; k++) sum[k] = k + sum[k - 1]; 
•  » » » » » » » » 2 years ago, # ^ |   0 I think prefix sums are a form of dp.
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 3 →   +1 Of course, this is DP. DP is a recursion + memoization. The recursion here is sum(k) = k + sum(k-1) and the memorization happens when you compute all values and store them in an array.
•  » » » » » » » » » 2 years ago, # ^ |   0 Ok.I always thought that it is necessary that we have exponential number of states in the original problem.
•  » » » » » » » » » 2 years ago, # ^ |   0 i think you meant memoizationbut i shouldnt really be talking cuz i suck at dp
•  » » » » » » » » » 2 years ago, # ^ |   0 Yes, you are correct. Although memoization and memorization bascially mean the same thing. memoization is just the computer science term for memorization.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Hello pixar, I have looked at your solution but I can see that you are considering all possibilities based on whether p,q and r are either positive or negative? Am I correct?
•  » » » » » 2 years ago, # ^ |   0 Yes, you are correct. That is the first solution that came to my mind. After I have submitted solution I realized how it could be simplified.
 » 2 years ago, # | ← Rev. 2 →   +6 Am I the only one seeing codeforces like only the left half of it and right side is blank? Edit: sorry I had clicked on mobile version by mistake
 » 2 years ago, # |   0 shit > Problem D
 » 2 years ago, # |   +17 Waiting for problem B massacre during system testing :)
 » 2 years ago, # |   -33 How To Pass That Case In B With C++ :- 1 -1000000000 -1000000000 -1000000000 1000000000
•  » » 2 years ago, # ^ |   +1 Please ask these things after the contest
•  » » » 2 years ago, # ^ |   +2 Sorry
•  » » » » 2 years ago, # ^ |   0 why don't you use long long ?
•  » » » » » 2 years ago, # ^ |   0 No. long long is out of range as the result will be -3000000000000000000
•  » » » » » » 2 years ago, # ^ |   +7 long long can handle numbers from -9223372036854775807 to 9223372036854775807.
•  » » » » » » » 2 years ago, # ^ |   +1 the 1st rule of the fight club — nobody should know about fight club
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +5 it is -922337203685477580 8, not 7.
 » 2 years ago, # |   +17 After the contest ends, can someone tell me how to solve that C? (btw, rip rating)
•  » » 2 years ago, # ^ |   +7 My solution:We can distinguish three types of parents for each node:1. A parent which is high security, which means this node has to have a type that is smaller than k2. A parent which is not high security, but has a type 1...k-1, so this node could be high security, or have a type from 1...k-1 or from k+1...m3. A parent which is not high security, but has a type k+1...m, so this node can not be high security, but it can have a type from 1...k-1 and k+1...mSo you can specify a dynamic programming state as node id, parent type, number of high security nodes in subtree, which leaves a complexity of O(N*3*x)=O(Nx) which is small enough.I didn't manage to implement it during contest successfully, but I'm pretty sure it's correct :/
•  » » » 2 years ago, # ^ |   +1 I came up the above you mentioned in about 15 minutes, but still can't solve it during contest:(If you know the subtree for this vertex has exactly i high security nodes, how can you know how many high security nodes come from each child?
•  » » » » 2 years ago, # ^ |   0 You can start of with the first child and try to give it j (ranging from 0 to i) high security nodes, and then there will be i-j nodes left for the other children. So here you can keep another dynamic programming state with properties node id (of the child), number of high security nodes left for the remaining children (so i-j) and type of parent. This will take an additional O(4*i*N)=O(Nx), so it should still be OK.Basically just try out every number for each child and use dynamic programming to avoid TLE.
 » 2 years ago, # |   0 Can someone tell me after contest what may be wrong with solutions for D in case 9 ? Is there any special condition that you can figure out from the problem statement that is not so obvious? Thanks
 » 2 years ago, # |   +22 At first I thought B was too easy and submitted it 2 times..But then i realized they said i<=j<=k and I stopped...out of 7 problems they cant afford to have two easy problem for newbies like me... Why so cruel!!!!
•  » » 2 years ago, # ^ | ← Rev. 2 →   -30 .
•  » » » 2 years ago, # ^ |   0 The contest is still running.
•  » » » » 2 years ago, # ^ |   -29 In last 2 minutes hardly anyone will benefit from this comment.
•  » » » » » 2 years ago, # ^ |   +4 Doesn't mean you should be discussing problems and solutions before the contest has finished.
•  » » » » » » 2 years ago, # ^ |   0 shhhh.... (time is running)
•  » » » 2 years ago, # ^ |   0 But i try to solve it greedy why is this wrong ? https://pastebin.com/AbG3BwLX
•  » » » » 2 years ago, # ^ |   0 You're missing i <= j <= k
•  » » » » » 2 years ago, # ^ |   0 Xd": ok that's dp , i'll hang a rope and suicide
•  » » » » » » 2 years ago, # ^ |   +5 No No. Don't do that !! There is lot more contests to come. This is not the last contest of CodeForces. And also DP problems will come too.
•  » » » » » » » 2 years ago, # ^ |   0 thanks
•  » » 2 years ago, # ^ |   0 Did we have to print answer modulo 1^9+7 or something for Problem B? My submission kept failing.
•  » » » 2 years ago, # ^ |   0 no,use long long int
 » 2 years ago, # |   +56 Wow, in D, type 1 of relationship in statement corresponds to type 0 in input. Nice.
•  » » 2 years ago, # ^ |   0 also the structure is not a tree but a forest and "...An object is considered to be neither a part of itself nor a special case of itself". That caused me 2 WAs :(
 » 2 years ago, # |   0 How to solve E?
 » 2 years ago, # |   +21 How to solve C?
 » 2 years ago, # |   0 Hack for B?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Overflow: 3 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 
•  » » 2 years ago, # ^ |   0 I hacked with this 1 1000000000 1000000000 1000000000 -1000000000
•  » » 2 years ago, # ^ |   +4 min or max value of result -3e18 or 3e18 wtf
•  » » 2 years ago, # ^ |   0 3 -2 3 -2 1 2 1Answer: 2
 » 2 years ago, # | ← Rev. 2 →   0 Will dp[len][mask][base] for smaller length, and fixing the first digit that differs work in E?
•  » » 2 years ago, # ^ |   0 I approached just like yours(with some hardcoded precomputations) but it was too slow.
•  » » » 2 years ago, # ^ |   0 the same.
 » 2 years ago, # |   0 TC4 for C? Does standard tree dp not work?
 » 2 years ago, # |   +18 I think I spent around 45 minutes for understand D task, and maybe I didn't understand it correct :D
•  » » 2 years ago, # ^ | ← Rev. 3 →   +13 Yes, "object", "special case", "part" all these terms are very unintuitive and it was very difficult to reason anything about this. I tried for 5 minutes and for the sake of my sanity I decided to let go this problem even if it later turns out to be very easy :P
 » 2 years ago, # |   +170 Wow, problem D was so beatiful, understanding complicated statement and dealing with stupid corner cases (forest + in query of type 2 if v is ancestor of u then NO), such fun
•  » » 2 years ago, # ^ |   +20 ah, it can be forest. Beautiful. Wonderful. So I guess that's why I got WA 9.
•  » » » 2 years ago, # ^ |   0 same
•  » » 2 years ago, # ^ |   +3 How is it possible to get "in query of type 2 if v is ancestor of u then NO" from the statement? I don't think it follows from "An object is considered to be neither a part of itself nor a special case of itself." sentence. Why a special case of object is object? It looks more like isinstance vs type in python :)
•  » » » 2 years ago, # ^ |   +15 This is clear (but not easy to observe), you simply have no rule to infer that B is a part of A if A is a special case of B.
 » 2 years ago, # |   -27 the best part of the contest were the problem statements. any potterhead there?
 » 2 years ago, # |   +32 Am I right in thinking B, C and E are all DP or DP variants? I got sick of coding C and was still coding E when time ran out, but I'm pretty sure B is a linear DP, C is a DP on trees and E is a recursion which pre-processes cases such as the number of all magic numbers smaller than bk so sort-of DP-like?
•  » » 2 years ago, # ^ | ← Rev. 2 →   -10 .
•  » » » 2 years ago, # ^ |   0 It's not that I don't know that. I solved B in about 20 minutes. You were discussing the solution to problem B with another user 4 minutes before the contest was over.
•  » » 2 years ago, # ^ |   0 I honestly felt the difficult was A
•  » » » 2 years ago, # ^ |   0 Actually, your formulation of the Problem C is almost perfect — it can be solved with dp[current node][number-of-special-nodes-left][is-neighborhood-of-special][is-neighborhood-of-node-with-whose-number-higher-than-special].After defining the table, you can fill it with knapsack inside recursion.
 » 2 years ago, # |   0 How did you guys solve the Problem E?I approached it with DP but it turned out in random testing that dp solution runs slow(about 8 seconds for 10^5 test cases).
•  » » 2 years ago, # ^ |   0 If you're at state "I can use every number from now because I guaranteed current number is smaller than R", then you have nothing to do with R so you can just use precalculated values for every base.
•  » » 2 years ago, # ^ |   +11 Precompute the following values: dp[base][length][mask] = number of combinations of the digits 0 to base-1. The binary representation of mask determines, which digit should appear odd and which even times. Then you can define a function f(base, x), which returns the number of numbers <= x, with each digit appearing an even time. Then the answer is f(r) - f(l-1). To implement f: Convert x to base base. iterate over all possible lengths of the numbers if the length is stricktly smaller then the length of x, the answer is sum(dp[base][length-1][1<
•  » » » 2 years ago, # ^ |   0 I tried just like that(even for the precomputation parts!) but it ran 8sec on my computer given this dataset(generator): from random import randint n = int(1e5) print n for _ in range(n): b = randint(2, 10) x, y = sorted([randint(1, int(1e18)), randint(1, int(1e18))]) print b, x, y 
•  » » » » 2 years ago, # ^ | ← Rev. 5 →   0 I think you made some mistake somewhere. The precomputation part takes no time at all on my laptop. And computing f(base, x) has runtime log(x). So this should be fast enough for n = 10^5. Pretests took 249ms. edit: accepted with 421ms.
•  » » » » » 2 years ago, # ^ |   0 Thanks, I found the BUG! it was frequent memset. I also made it work by fine-tuning memset calls(sadly, though the contest is over).
•  » » » » » » 2 years ago, # ^ |   0 How did you submit? System is not letting me submit
•  » » » » » » » 2 years ago, # ^ |   0 I didn't but I just tested with my generator(see above).
 » 2 years ago, # |   +1 How to Solve B?
•  » » 2 years ago, # ^ |   0 Yes, it is also interesting for me (
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 Fix the position of q. Then p matches with max(input[1..pos_q]) and r matches with max(input[pos_q...n]). Both maxes can be calculated in O(1) thanks to easy precomputations.
•  » » » 2 years ago, # ^ |   0 i spent almost one and half hours but couldn't and after seeing this i realize that i know nothing (:great solution!
•  » » 2 years ago, # ^ |   +3 I figure this is much much simpler than DP:  ll bestp = -INF; ll bestpq = -INF; ll bestpqr = -INF; for (int i = 0; i < n; i++) { bestp = max(bestp, p * values[i]); bestpq = max(bestpq, bestp + q * values[i]); bestpqr = max(bestpqr, bestpq + r * values[i]); } cout << bestpqr << endl; 
•  » » » 2 years ago, # ^ |   +73 This is, my boy, called DP solution.Btw, one should take care and set INF to at least 3e18, not to 1e18 as I did.
•  » » » » 2 years ago, # ^ |   0 Hello, I find it quite hard to understand this solution and how to come up with it. I see everyone mentioning DP, but I have no knowledge about it, could you give me some source for researching this type of algorithms?
•  » » » » » 2 years ago, # ^ |   0 Google "Dynamic programming"
•  » » » 2 years ago, # ^ |   0 can you please explain how it works correctly?
•  » » » » 2 years ago, # ^ |   0 So first we want to find the best if we just choose p, which is bestp. We can also choose to use the current one for q, which is bestpq, and it builds off of everything before us (stored in bestp) so we can maintain if it is the best over time. We do the same thing for bestpqr which is our answer.
 » 2 years ago, # | ← Rev. 2 →   +7 D is just LCA and recording the relations between the query nodes and LCA right? I kept getting WA on test 5, found bug, then got compile error in the last 5 second... (anyone know if that's the right idea though?)Also, how to solve C + E?
•  » » 2 years ago, # ^ |   +6 You can solve C with next DP states DP[ root of subtree] [ amount of highest elements] [ value of current element ( smaller than k, equal to k, bigger than k ].For E I think it is also some easy DP, I think it is called DP on Digts — but I didn't try to write code :)
•  » » » 2 years ago, # ^ |   0 Can you elaborate how we choose the amount of highest elements for the child? I got tripped up there.
•  » » » » 2 years ago, # ^ |   +1 you can just fix the number of special elements in subtree of children = x, and number of special elements we already had before in other subtrees of node = y, update states with x + y
•  » » » » 2 years ago, # ^ |   0 You can run another DP, something like amount of ways to choose i highest elements in subtrees of first j childs. And with third dimension in previous post (value of current element), you exactly know what values can be in children ( I think if value of current node equal to k than children must have that state smaller than k, it value of current node smaller than k, than children can have any value, and if it is bigger than k, children must be smaller than k or bigger not equal).
 » 2 years ago, # |   0 Reducing to graph reachability is wrong in D?Btw, is E really easier than D. For D at least I still have some idea, but for E my mind is completely draw a blank.
•  » » 2 years ago, # ^ |   +3 E is just well-known DP on digits.
•  » » » 2 years ago, # ^ |   +5 But with large b, the naive dp on digit will work in O(q * 2b * logba), which is not fast enough. So I think there must be some other observation here.
•  » » » » 2 years ago, # ^ |   +18 Just precalc dp[B][l][mask] = number of numbers in base B, with len l that have mask of digits mask. Now you can answer fast
•  » » » » 2 years ago, # ^ |   +5 Precompute first so you can remove 2b from the complexity
•  » » » » 2 years ago, # ^ |   +18 I don't have 2b factor even in preprocessing. I just keep number of digits with odd number of occurences (and I preprocess it).
•  » » » » 2 years ago, # ^ |   +3 You can do it for each base
•  » » 2 years ago, # ^ |   0 At least, E's statement is much easier to understand than D's.
 » 2 years ago, # |   0 In D : v is not a special case of v if u is a special case of v , v is not a special case of ujust thought about these two in the last 5 minutes where there was no time :(
 » 2 years ago, # |   0 Hack Case for B ?
•  » » 2 years ago, # ^ |   0 For example if somebody set the final answer as 0 then update it in O(n) process then when there have some cases like 4 12 14 16-1000000000 -1000000000 -1000000000 -1000000000then he will output 0 instead of correct answer
 » 2 years ago, # |   0 In problem d we have two rooted forests.forest 1 and forest 2.For queries of type 1 just check if vertex 1 is ancestor of vertex 2 in the forest (using the dfs in and out tree).For queries of type 2 I think the following works: For each vertex let let F(v) be the root of its component in forest 1. Add all edges that v has in forest 2 to F(v).now do the dfs in the modified graph and check:vertex 2 is son of F(v1)vertex 2 is equal to F(v1) and there is a loop at F(v1)If none of these happens print No.I forgot to check the loop thing, I think thats why I failed pretest.
•  » » 2 years ago, # ^ |   0 How did you solve C?
•  » » » 2 years ago, # ^ |   +2 let Rs[x][i] be the number of ways to color the subtree of vertex x such that there are i max security vaults and the node x has a security less than k.Let Ry[x][i] be the same but such that node x has max security and let Tb[x][i] be the same but such that node x has security larger than k.You can then obtain the values of R[x][i] from the values of R[y][i] such that y is a son of x.So it is like a dynamic programming on the tree.
 » 2 years ago, # |   +6 Best Problems i ever had...
 » 2 years ago, # |   +24 Am I the only one who skipped i<=j<=k condition in B ??? So stupid of me :(
•  » » 2 years ago, # ^ |   0 Me too.RIP rating
•  » » 2 years ago, # ^ |   +3 i realised it after reading ur commment
 » 2 years ago, # |   +18 I solved E as even number of times means equal number of times and realized it's wrong while testing the samples :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   +17 I think if it was each of the digits from 0 to b - 1 appears even number of times instead of all the digits from 0 to b - 1 appear even number of times, it would've been less confusing.
 » 2 years ago, # |   0 http://codeforces.com/contest/855/submission/30675269What's the hack for b ?
•  » » 2 years ago, # ^ |   0 Try this one 1 -430770061 -822021323 -993560291 674829238 ans is -1515903789120273650
 » 2 years ago, # |   +6 how to solve problem E?
 » 2 years ago, # | ← Rev. 2 →   +43 Shit! No large pretest for E. "calc(int b, int l)" still pass pretest!
 » 2 years ago, # |   +3 The time limit for problem C seems very strict to me. I had to somehow squeeze my solution by making stupid optimizations and still think it will get TLEd on main tests.
 » 2 years ago, # |   +2 Can anyone please explain the solution idea for problem C and D? Thanks in advance. During the contest time I thought that D can be solved using LCA and some query on it. But I am not sure.
•  » » 2 years ago, # ^ | ← Rev. 4 →   +3 The solution for D is indeed LCA. Let's say each edge is either type 'a' or type 'b' (because the problem changes the notation mid-problem anyway). One of the queries is asking if u is an ancestor of v & if the path between the two is composed only of type 'a'. The other query is to find the LCA of u and v which we denote 'p'. If p exists & the path from u to p is only of type 'a' & the path from v to p is only of type 'b'. (I might have mixed up the symbols) Along with the parent sparse table and height we use for LCA, we also use a boolean sparse table with the recursion reachA[x][d] = reachA[x][d-1]&&reachA[parent[x][d-1]][d-1] or similar to see if the path is with only type 'a' or type 'b'.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +3 UPD: Ok, my D failed. Maybe you don't want to listen to me about it :DProblem D: You were right. Let sc[i] be the uppermost (the one with lowest level) node which can be reached from i by following only special case edges and part[i] be the uppermost node which can be reached from i by following only part edges. Calculating these two values is a trivial DP/DFS. Now type 1 query simply asks if U is an ancestor of V and sc[V] is ancestor of U. Type 2 query asks if U and V are in the same tree (if so, let's say L is their LCA) and both sc[U] and part[V] are ancestors of L.Problem C: Okay, I am pretty sure I have overkilled this problem. Anyway, there are three types of labels — those less than K, those equal to K and those greater than K. Labels from the same type are indistinguishable. I use dp1[node][typeOfParent][numberOfHighlySecureVerticesInTheSubtreeOfNode]. Now, there might be an easier way to calculate the state which I don't know so what I do in such cases is use a second dp, dp2[node][currentChildOfNode][typeOfParent][numberOfHighlySecureVerticesInTheSubtreeOfNode] which works by looping over node's children and assigning some number of highly-secured vertices for each of their subtrees. So dp2[node][idx][type][cnt] is equal to the sum of dp1[v[node][idx]][type][i] * dp2[node][idx + 1][type][cnt - i] for i from 0 to cnt. v[node][idx] is the idx - th child of node. The value of dp1[node][type][cnt] is simply dp2[node][0][type][cnt]. To get the value of dp1[node][type][cnt], we will first need to choose the type of node. After that, we can easily obtain its value from dp2[node][0][type][cnt] or dp2[node][0][type][cnt - 1], depending on which type we have chosen.Note that in the second dp the number of pairs [node][currentChildOfNode] is O(N) — it's just the number of edges.
•  » » » 2 years ago, # ^ |   0 For fixed i and j, you can combine your dp1[i][j][k] into coefficients of a polynomial, of degree x. Then dp[i][j] is going to be a product of the corresponding polynomials of the children of i. (You have to fiddle around with exactly which polynomials to multiply — basically translate the rules about neighbors of highly-secure vertices).
 » 2 years ago, # |   +72 Type 1 relation means that the child object is like a special case of the parent object. Type 2 relation means that the second object is always a part of the first object and all its special cases.If typei = 0, this implies that the object i is a special case of object parenti. If typei = 1, this implies that the object i is a part of object parenti. Triggered.
•  » » 2 years ago, # ^ |   +13 This takes effort.
•  » » 2 years ago, # ^ |   +8 Very weird statement. Nice problem, but a better care with the statement would have made a great difference.
 » 2 years ago, # | ← Rev. 2 →   +9 Could anybody please explain me why my solution to B TLEd on test 66?Link to submissionUPD: Nevermind, I initialized my dp array with -1 while -1 is a possible answer. :(
•  » » 2 years ago, # ^ |   +7 same thing happened with me..
 » 2 years ago, # | ← Rev. 2 →   +6 System test is over, should we be able to submit or is there bug?edit: also cannot view other people submissions
 » 2 years ago, # |   0 GOOD for fast system testing :)
 » 2 years ago, # |   +7 CF Format hit me hard today. Made the silliest of bugs on B, didn't get hacked throughout on it, solved a much more harder C, and now I have to deal with ending below some people who got many hacks.So much related to luck is CF format, isin't it ?Only if I could change a single character on my B and resubmit.
 » 2 years ago, # |   -11 Not able to submit even after tests ? Is there some sort of bug ?
•  » » 2 years ago, # ^ |   0 Patience is the key to success
 » 2 years ago, # |   0 2nd problem was good :)
•  » » 2 years ago, # ^ |   +3 indeed it was :P
 » 2 years ago, # | ← Rev. 2 →   0 What is the solution for this test case for problem D? 5 -1 -1 1 0 1 0 2 1 2 0 4 2 1 4 2 2 4 2 3 4 2 5 4 
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 NOYESNOYES
 » 2 years ago, # |   +18 When can I submit??
 » 2 years ago, # |   +49 enable upsolving?
 » 2 years ago, # |   0 For B, what is problem with this solution If p,q,r is negative, multiply it by smallest ai. Else, multiply it with biggest ai.Sum those 3 and print.
•  » » 2 years ago, # ^ |   0 You have to maintain order of A[i], A[j], A[k] such that i <= j <= k. I think you are sorting your array . This was not allowed
•  » » 2 years ago, # ^ |   0 1 <= i <= j <= k <= N.If p is positive and q is negative.Then, that condition(i<=j<=k) won't be satisfied in your algorithm.
•  » » » 2 years ago, # ^ |   +3 Lol. Thanks, I totally forgot that order i,j,k matters ( i is for p and so on..)
•  » » 2 years ago, # ^ |   0 For test case 3 p = -1 q = -1 r = 10 A = {1 1 0} Answer = 8
 » 2 years ago, # |   0 someone please tell me how to solve problem B. If u can give correctness of ur solution will be very helpful
•  » » 2 years ago, # ^ |   +12 Let f[i] = a[i] * p and g[i] = a[i] * r. Now let pref[i] = min(f[1], ..., f[i]) and suf[i] = max(g[i], ..., g[n]). The answer is obviously pref[i] + a[i] * q + suf[i] for some i.
•  » » » 2 years ago, # ^ |   0 Thx :) clear now
•  » » 2 years ago, # ^ |   +1 Traverse the array, find the maximum value of p*A[i] for each prefix i ie., Prefix_A[i] = max(prefix_A[i-1],p*A[i]).This can be done in O(N).Now,find the maximum value of p*A[i]+q*B[j] for each prefix j ie., Prefix_B[j] = max(Prefix_B[j-1],B[j]+Prefix_A[j]) — O(N).At last find the maximum value for each prefix k of p*A[i]+q*A[j]+r*A[k] using this Prefix_B array and take the maximum of them ie., Ans = max( C[k] + Prefix_B[k] , Ans ).
 » 2 years ago, # |   +5 Ratings are updated without deleting cheaters now. They will be removed and the ratings will be recalculated, they may slightly change.
•  » » 2 years ago, # ^ |   +26 Sir, When will you enable upsolving?
•  » » 2 years ago, # ^ |   0 Why isn't other's solutions accessible?
•  » » 2 years ago, # ^ |   0 Have they been recalculated yet?
•  » » 2 years ago, # ^ |   +5 The code of these two accounts in many games is similar or even the same: 770780079 pb0207
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 It seems only 770780079 had his code skipped, shouldn't pb0207 get skipped as well? Is this a flaw of anti-cheat program?
•  » » » » 2 years ago, # ^ |   0 Perhaps this is a flaw in the anti-cheating software, but it seems that the code submitted early should be counted as AC. Because after locking the code, you can view the code of others.And for example, replace the variable name, add useless function, add useless comments, add a black line. Will make anti-cheating procedures can not be detected.Their code is too similar, and I also participated in those rounds, I do not think this coincidence caused by the coding habits .854C:77,pb861C:77,pb862D:77,pb862C:77,pb
•  » » » » » 2 years ago, # ^ |   0 It should be that both users are disqualified — they shared code, and the "alternate account to look at solutions after lock" is clearly not what is happening. It is definitely flaw of the system. By the way, you are great detective.
 » 2 years ago, # |   0 what is pretest 4 of problem C??
 » 2 years ago, # |   0 How to solve problem B. Good problem in my opinion.
 » 2 years ago, # |   0 What is the test 75 of problem B. Got Wrong answer on test 75 [main tests] → 30680748 -_-
 » 2 years ago, # |   +18 Literally my worst round ever. A: Map string to int, done B: Just iterate over the array from left to right, and from right to left. Unfortunately, I set the minimum answer to  - 1018 and end up getting hacked. C: Tree DP takes some time to implement, but not hard. D: Realizes that it's just LCA, incorrectly handles the statement "An object is considered to be neither a part of itself nor a special case of itself." E: Obviously digit DP, but I have never done digit DP very quickly. Spends 1,5 hours trying to debug and submits with a couple minutes left. After the contest ends, I realize that I did not properly handle the case where r = 1018. --> rating gain from MemSQL Round 1 completely erased :D
 » 2 years ago, # | ← Rev. 2 →   +127 http://codeforces.com/contest/855/submission/30682143 http://codeforces.com/contest/855/submission/30686094 — what a "tricky" solutions to F (of people from 1st and 4th places). Did setters spend at least 5 minutes on tests to this problem?
•  » » 2 years ago, # ^ |   +5 Look at solution, I see related problem.
•  » » 2 years ago, # ^ |   +40 The code of Shik without #pragma GCC optimize("Ofast,no-stack-protector")#pragma GCC target("avx,tune=native")receives TL30. ¯\_(ツ)_/¯
•  » » 2 years ago, # ^ | ← Rev. 3 →   +44 Oh, common. This is SSE optimized solution.How many setters even know about SSE/AVX? I doubt authors simple solution works >2x of TL.SSE speed up anta's solution >4x times: 30682143 30690004Guys, it's 2017, it's time to read something about vectorization. It's more useful on CF than learing suffix tree and other complex useless stuff.
•  » » » 2 years ago, # ^ |   +16 http://codeforces.com/contest/855/submission/30686153Without any vectorization and #pragmas.
•  » » » 2 years ago, # ^ |   +6 I put these in the headers of some of my previous codes and there's a significant speed up. So there are no extra things I have to worry about? I can just put it in my template and give my poorly-optimized codes a boost?
•  » » » 2 years ago, # ^ |   +30 Can you tell a bit more about what does SSE/AVX do?
•  » » » » 2 years ago, # ^ |   +32 Regular instructions (without AVX/SSE) are executed by the processor one at a time, while AVX/SSE instructions use special registers capable of holding more bits than a regular register, for instance, there are processors that support AVX-256, meaning that it provides instructions for executing operations (such as loading, storing, adding...) on 256 bits (8 integers/floats or 4 doubles/longs...) at once. It is basically a form of instruction-level parallelism (SIMD).You can ask the compiler for trying to compile your code into those special instructions, it will be done when possible, for exemple, if you're dealing with arrays, loops will take bigger steps and execute operations on more than one element at a time, that can cause speedups of 2, 4 or even 8 times. You could also, instead of asking the compiler, use those instructions yourself with high level functions, but the problem is that you would have to know which version of AVX/SSE the target processor supports.
•  » » » » » 2 years ago, # ^ |   +22 Is there any reason to not include above pragma's in your code by default?
•  » » » » » » 2 years ago, # ^ |   +3 I don't think so. Apparently what made a big difference was: #pragma GCC optimize ("O3") #pragma GCC target ("sse4") The compiler already uses SSE (< 4) instructions with the flag O3. And SSE4 has been around for quite some time, so it will probably work for most online judges. I'm not sure if the compiler still uses SSE4 if the processor doesn't support it, my guess is that it ignores the pragma (I could't find an older processor to test it).Analysing the differences in the assembly between 30682143 and 30690004, there seems to be very little change except for a few instrutions that get the same result in less steps, those new instructions are some of the ones introduced in SSE4. The speedup in that case is 4x (very high) because those faster instructions are in the middle of the two innermost loops! Which means that including the pragmas in every code will probably not make that big of a difference in the execution time.
•  » » » » » » » 2 years ago, # ^ |   +1 So what if I have both the sse and avx header? There's no problems to worry about?
•  » » » » » » » » 2 years ago, # ^ |   0 Well... There's usually some loss of efficiency when using both SSE and AVX, but apparently GCC takes precautions when that's the case. So I guess that using both pragmas isn't a problem, but I'm not sure about how much it improves the performance, it really depends on the program you're compiling.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 That's so sad I haven't read the statement of problem F during the contest. It is very obvious with such limits that it can be solved by O(NQ) =(
 » 2 years ago, # |   +22 Can someone recommend some DP on tree problems like C, where you compute the DP states inside the dfs and stuff like that? Thanks!
•  » » 2 years ago, # ^ |   0 Can you or anybody else suggest a tutorial for the same?
•  » » 2 years ago, # ^ |   +26 Here are some problems from Codeforces that can be solved using a similar approach: Bear and Tree Jumps, Appleman and Tree, Road Improvement, Ostap and Tree.
•  » » » 2 years ago, # ^ |   +3 Thanks!
 » 2 years ago, # |   +3 When will editorial be published?
 » 2 years ago, # |   +1 I was looking at someone's submission and I found this block of code. Can someone explain what the ONLINE_JUDGE flag is? #ifndef ONLINE_JUDGE FILE *stream; freopen_s(&stream, "input.txt", "r", stdin); // freopen_s(&stream, "output.txt", "w", stdout); #endif 
•  » » 2 years ago, # ^ |   +4 ONLINE_JUDGE is a flag used by most OJ's, basically that if the flag not set #ifndef`, enter that bloc of code which change the input/output stream to those files.
 » 2 years ago, # |   +9 Editorial right after the contest can be the best gift.
 » 2 years ago, # |   +3 What happened to ratings ? :(
 » 2 years ago, # |   +8 Any idea why the rating changes were removed?
•  » » 2 years ago, # ^ |   0 They are back already, i believe it is something like people cheating, so they invalidate person's contest and recalculate the ratings, if you observe, some people had ratings increased by 1 or 2
 » 2 years ago, # | ← Rev. 2 →   0 My little question about problem D:If object i is a special case of object j and object j is a part of object k. So is object i a part of object k?It's really bad to find out that you got FST on D because you remembered to examine one more case.
•  » » 2 years ago, # ^ |   +5 no, this is like if you have i is a monster truck wheel, j is a wheel, k is a car.So all car will have wheel but that doesn't mean it has monster wheel
•  » » » 2 years ago, # ^ |   0 Well, you are right. Many thanks.
 » 2 years ago, # |   0 Can anyone please help me find the reason for WA in test 5 in the B question...Here is the link to my solution...http://codeforces.com/contest/855/submission/30981196