### Wild_Hamster's blog

By Wild_Hamster, history, 4 years ago, translation, ,

Greetings to the Codeforces community!

Regular Codeforces round #308 for participants from the second division will take place on 18 June, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my second round on Codeforces(First round — Codeforces Round #280 (Div. 2)). Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: Scoring is standard: 500-1000-1500-2000-2500.

UPD: Congratulation to the winners:

UPD: Contest is over. Thanks for participating :)

UPD: Editorial

• +204

 » 4 years ago, # |   -57 i hope this round has harder problems than round #280.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +66 Your last round was interesting and solvable ! I believe it will be easier than round 307 :)
•  » » » 4 years ago, # ^ |   +52 Tell me allllekssssa, you are a fan of PrinceOfPersia aren't you? :P
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +28 He is grat guy ! I can imagine this sentence in announcment to my next round :We prepared one easy contest, because the past was very difficult :D
•  » » » » » 4 years ago, # ^ |   +4 Ya, I found his contest questions really interesting...:)
•  » » 4 years ago, # ^ |   0 just noticed round #280 is my first contest in code forces. Well, and after this round I am in Div-1, so when is the next round maybe i will be red :D
•  » » » 4 years ago, # ^ |   +4 You are really lucky to get your solution for D passed! :P :D
•  » » » » 4 years ago, # ^ |   0 I'm a lucky bastard :3
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +3 My history:First Codeforces round participation = round #235First Codeforces round to get in div1 = round #263difference in number of rounds = 28Your history:First round = 280 First round to get in div1 = 308difference = 28And my current rating is the same as that after round 263 . So clearly this is not a good metric to judge how soon you would become red :)
 » 4 years ago, # |   +42 Happy Ramadan holiday to all. I wish luck for today's contest to every participants.;)
•  » » 4 years ago, # ^ |   +2 Happy to you as well.
 » 4 years ago, # |   0 I wish to see some easy interesting problems :)
 » 4 years ago, # |   -20 I hope this round have some problems which i am not able to solve.
•  » » 4 years ago, # ^ |   +8 then u should attempt div 1 mate !!!
•  » » » 4 years ago, # ^ |   -8 The fact is that in many div 2 only contests there are some problems which are very hard and brilliant!Beyond that , i participate unoffically this contest so it is more important for me to learn something new than to get a good rank.
 » 4 years ago, # | ← Rev. 2 →   +11 Wild_Hamster has a recursive profile pichow did you make it
•  » » 4 years ago, # ^ |   +2 His profile pic is in Russian, but my interface is in English :)Also the rating and contribution are different.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 My guess would be 1. take a screenshot of your profile. 2. copy+paste 3/4th of the screenshot to the remaining 1/4th space by reducing its size. 3. Repeat 3-4 times till its possible to do this within the smaller window each time. But this is just my guess.
•  » » 4 years ago, # ^ |   0 that trend i did first :D
•  » » 4 years ago, # ^ |   0 I guess, print screen profile pic and set it as profile pic until the original pic is too small !
•  » » 4 years ago, # ^ |   0 блиииин, забыл зарегатся(((((
 » 4 years ago, # |   +20 Every contest is simply amazing !! Somebody will participate officially , others no , but the idea is improve in each contest. enjoy the problems and keep the calm !! Good luck and Have fun to everyone !!!
 » 4 years ago, # |   0 good luck to all participants
 » 4 years ago, # |   +3 I hope that there will be no delay, no lag near the end of contest, and no cheaters :)
 » 4 years ago, # | ← Rev. 2 →   +8 I think it's time to publish scoring
 » 4 years ago, # |   -9 When you know you are closest user to Div.1 but you know it will not be happen :(((
•  » » 4 years ago, # ^ |   +3 better change your user to BornToBeLoser, it will suit you better
•  » » 4 years ago, # ^ |   +13 it's your second round be patient! :3
•  » » 4 years ago, # ^ |   -8 Especially, when you BornToBeWinner :)
 » 4 years ago, # |   +2 Please announce scoring.
•  » » 4 years ago, # ^ |   0 Bro :(
 » 4 years ago, # |   +168 Did you notice live judgement updates on the status page? Do not hope to see verdict faster by pressing F5, this page now gets live judgement stream directly from the judging module!
•  » » 4 years ago, # ^ |   0 codeforces everyday growing! Keep on!
•  » » 4 years ago, # ^ |   +28 5-10 seconds of the highest quality drama on every submit! (Jaws music on the background) :)
 » 4 years ago, # |   0 For me it's really interesting why each Div2 round there are persons like this http://codeforces.com/profile/liyankui who solves all the problems without participating in any other contest before.
•  » » 4 years ago, # ^ |   +12 I'm gonna be captain obvious here in case there's someone that doesn't know — Div1 users make new accounts to win Div2.
•  » » » 4 years ago, # ^ |   0 Ok, what is the goal of doing it?
•  » » » » 4 years ago, # ^ |   +11 Very frustrating I know. What is the point of red/orange coders beating div 2 guys? What are they trying to achieve this way? Its somehow fun and exciting for them, but very frustrating for div 2 participants.
•  » » » » 4 years ago, # ^ |   0 There is none, they just want to see themselves on the blog and feel good for being top5. We've all agreed it's a stupid practice, and it has been discussed tons of times before.Sadly there is no efficient way to stop them from doing it without limiting other competitors.
 » 4 years ago, # |   0 Its not programming contest, its math contest...
•  » » 4 years ago, # ^ |   +1 Brute Force, Digit DP, Number Theory ( ok, this one is math ), Geometry and I am not sure about the last one since I couldn't solve it. It was somewhat balanced I guess.
•  » » » 4 years ago, # ^ |   +19 C is brute force :Dwhen w=2 or w=3 the answer is always YES , when w>3 you will not use more than the first 16 weights so you can use O(3^16) brute force
•  » » » » 4 years ago, # ^ |   +1 not necessarily, my solution uses 100 iterations onlyhttp://codeforces.com/contest/552/submission/11642323
•  » » » » » 4 years ago, # ^ |   +3 ok I didn't say it can't be solved faster but constraints allow brute force to pass
•  » » » » » 4 years ago, # ^ |   0 I don't think your loop is over 50. log2(10^9) is only around 30 :)
•  » » » » 4 years ago, # ^ |   0 it could even be done in O(216) . You assign m to one pane and w0 to w15 to any pane and then try to balance both pans by removing weights greedily.
•  » » » » 4 years ago, # ^ |   0 how did you know that you will not use more than the first 16 weights ?
•  » » » » » 4 years ago, # ^ |   +11 If w >= 4 and there are 17 weights, then the minimum number we can get (positive) is 4^16 — (1+4+...+4^15), more than 10^9. And it is clear that with more weights, the minimum is even more.
•  » » » » » » 4 years ago, # ^ |   +1 then if we have in the first pan (1 + 4 + ... + 4^15) and in the second pan (4^16) the difference is larger than 10^9. however, why we can't put some weights to the first pan say (4^x & 4^y) then put (4^z) in the second pan to get the scale balanced again ?how did you prove that such numbers like x, y, z don't exist!
•  » » » » 4 years ago, # ^ |   +1 3^16 brute force can be optimized with meet-in-the middle approach to do it in 2*(3^8)
•  » » » » 4 years ago, # ^ |   +5 we can solve C in O(log n)
•  » » » » 4 years ago, # ^ |   0 Sorry, But how do you know that you will not use more than 16 weights? Is it depending on maths?
•  » » » » » 4 years ago, # ^ |   +8 Yeah, w^0+w^1+w^2+...+w^(n-1) < w^n holds for w>=2 :)
•  » » » » 4 years ago, # ^ |   0 Is it possible to find some weights more than w^16 to get the scale balanced ? If not , Can you explain that , please ?
 » 4 years ago, # |   +37 Great! contest was very interesting! thanks to author
 » 4 years ago, # |   0 I have mistake in problem C :(Problem D is classic, but I don't love geometry...
•  » » 4 years ago, # ^ |   +4 I think D has less geometry than it seems to have.
•  » » » 4 years ago, # ^ |   +1 but how do figure out how many collinear sets we have ? after that it would be normal permutations and combinations.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I didn't think about it a lot, but my solution have calculating coefficients , sortings and after that line sweep. Maybe I wrong ?
•  » » » 4 years ago, # ^ |   0 D was also a brute force.As time limit for D was 4sec.It's sad that very few noticed it. :(
•  » » » » 4 years ago, # ^ |   +4 10^8 iterations per second, isn't it?Then 4*10^8 iterations in 4 seconds. I don't get how come D passed for many submissions! It takes 2000*2000*2000 iterations!May be CF is too fast.
•  » » » » » 4 years ago, # ^ |   +10 I was going to hack a O(n3), then thought of running simple addition 2000^3 times in custom invocation and it took .7s. I was like "brace yourself, something terrible is coming :|" 10^8 iterations theory doesn't apply to CF
•  » » » » » 4 years ago, # ^ |   0 roughly 4 *10^8 iterations are there in 1 sec
•  » » » » 4 years ago, # ^ |   +3 D can be solved in n^2logn using some concepts of geometry. It would be a nice one if time limit would have been 2 sec. You can see my code here
•  » » » » » 4 years ago, # ^ |   0 I tried the same way but was not able to solve in the contest :( I was missing the condition when slope if line was infinity.
 » 4 years ago, # |   +7 two WA due to inbuilt gcc pow function:( in 308-B never using it again...
•  » » 4 years ago, # ^ |   0 Yea, I realize now that my 308B is wrong ;_;
•  » » 4 years ago, # ^ |   0 Same here, Don't understand why gcc pow function fails though ?
•  » » 4 years ago, # ^ |   0 Whats the issue with pow? I too got WA for tests whereas the answer was all right in the local machine.
•  » » 4 years ago, # ^ |   +3 same problem ....faced twice on codeforces
•  » » » 4 years ago, # ^ |   +4 pow gives output in double i tried to cast it to long long but there can be precision issues like the pow function giving 2^3 as 7.999999999999 and not 8 which on casting will give lesser answer.
•  » » 4 years ago, # ^ |   0 For some reason codeforces, which uses mingw (i think) is giving a bad answer with pow. Ideone gave right answer for the same code of mine. I feel it should not have to approximate since pow(integer) would return an integer in double form, which would not need any truncation.
•  » » 4 years ago, # ^ |   0 I know that feel bro.
•  » » 4 years ago, # ^ |   0 i too got 1 wa because of same.
•  » » 4 years ago, # ^ |   0 Try powl someday or use pow with nearbyint ...
 » 4 years ago, # |   +5 I like so much problem C
 » 4 years ago, # | ← Rev. 2 →   +74 Is it OK nowadays to have "write a brute-force, it works in 3.7 while TL is 4" and "use Python to write it in 10 lines, it has built-in eval" as two hardest tasks of contest?
•  » » 4 years ago, # ^ |   +2 Eval gets Tl, doesn't it?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 With naivest implementation it gets; however, with relatively obvious additional observation that it makes no sense to place brackets near '+' sign (you may move it to extend part in prackets till the end of string or '*' sign and it will not decrease result), you have only a small number of possible ways to place brackets.
•  » » » » 4 years ago, # ^ |   0 Got it, thanks.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +13 built-in eval && regex * regex, upsolved: 11658690
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Yes, I was a bit surprised my solutions passed on those problems. The TL for D and E should have been tighter.
 » 4 years ago, # | ← Rev. 8 →   0 What was wrong with this approach for problem C? http://codeforces.com/contest/552/submission/11653548I tried decomposing m into powers of w and if some power of W is W-1 times i put a weight of W-1 on that side . :(Eg- if 20=3^2+3^2+3^0+3^0 Now 3^2 is 2 times and 3^0 is also two times,so adding 3^2 and 3^0 on side of 20 and 3^3 and 3^1 on other side would balance it,i also handled corner casesEDIT:GOT AC.Used same concept but properly handled corner cases this time :)
•  » » 4 years ago, # ^ |   +1 check for w=3 and m =17
•  » » 4 years ago, # ^ |   +1 Try to debug . It gives WA for 4 11 Your output NO Correct YES; 11 + 4 + 1 = 16
•  » » » 4 years ago, # ^ |   0 Got AC.Thanks
 » 4 years ago, # |   +5 I tested my D solution for the worst case and it ran fast enoughI wonder can O(n^3) pass ? hope it will
•  » » 4 years ago, # ^ |   0 noI tried and got time limit error
•  » » » 4 years ago, # ^ |   0 are you sure ? my solution passed with O(n^3) complexity!
•  » » » » 4 years ago, # ^ |   0 yesnot passed for me O(n^3)did you use Cpp language for submit?
•  » » » » » 4 years ago, # ^ |   0 yes
•  » » » » » 4 years ago, # ^ |   0 If you use long long ints with n^3 I got a TLE, with ints and n^3 it got an AC
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I submitted O(N^3/6) and it passed the pretests.UPD: My solution also passed system tests.
•  » » 4 years ago, # ^ |   0 Depends. I've tried on C# — it was like 5-6 seconds. So probably C++ could pass.
•  » » 4 years ago, # ^ |   0 I think O(n^3) is too slow, but we will see.
•  » » 4 years ago, # ^ |   +6 IT PASSED :Dmy first time to solve problem D during contest :D
•  » » 4 years ago, # ^ |   +8 Should it pass? If yes, then why? I used n^2logn and it took me long time and cost 1 submission. :(
•  » » 4 years ago, # ^ |   0 O(n3)??? This is the first thing I thought and then I spent all the contest trying to optimize to O(n2logn). Sad!!!
•  » » » 4 years ago, # ^ |   0 same thing happened to me. D should be rejudged be with proper test cases!!
•  » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   +12 You just use Java in a wrong way: 11665530.
•  » » » » 4 years ago, # ^ |   0 what's the difference?both use BufferedReader for input O(n^3) time complexity and PrintWritter for outputwhy your code runs faster?
•  » » » » » 4 years ago, # ^ |   +1 Magic!Actually constant factor is important. In deepest place in my code I do one subtraction (compare to 5 subtractions in your code).
•  » » » » » » 4 years ago, # ^ |   0 OK thanks
 » 4 years ago, # |   +7 Use Math tags for all of the problems :DNice contest thanks:)
 » 4 years ago, # |   +2 Could someone explain the solution for C ? Thanks :)
•  » » 4 years ago, # ^ |   -7 wait for the editorial
•  » » 4 years ago, # ^ |   +1 If m = 2, then solution always exist — it likes writing m in binary base.If m >= 3, find the first value of n that w^(n-2)*(w-1) > m. With m = 3, n = 18 and as m goes greater, n goes smaller. So, an O(3^n) brute-forces (considering each scales to be on the same pan with the object, different pan with the object or outside the pan) with properly branch-bound should be fast enough to get AC.
•  » » » 4 years ago, # ^ |   +16 With w = 3 there is always a solution too, right?I'm not really sure, but if we use base 3 (instead of binary), instead of using 0 1 2 we can use -1 0 1 and find any integer combining powers of three this way.
•  » » » » 4 years ago, # ^ |   0 I'm not sure about this.PS: My solution got TLE on test 85. So this is probably not the correct solution (or I didn't implement it well).
•  » » » » » 4 years ago, # ^ |   +5 https://en.wikipedia.org/wiki/Balanced_ternaryI just found this looking for ternary base, so it looks like it's possible.
•  » » » » » 4 years ago, # ^ |   +3 Because you should output YES immediately when w=3 , when w>3 use brute force
•  » » 4 years ago, # ^ |   0 The answer is "YES" if it is possible to add another number that only contains 0s and 1s (in base w) to m such that the resulting sum only contains 0s and 1s as well. Just use the algorithm for naive sum, if the sum at the current digit is w — 1 set carry = 1, if the sum at the current digit is 1 set carry = 0, if sum at the current digit is different than 0 return "NO" .
•  » » 4 years ago, # ^ |   0 our m needs to satisfy m = a_100*(w^100)+ .... a_0*(w^0),where a_100..a_0 are -1,0,1 we just test if m satisfies thishttp://codeforces.com/contest/552/submission/11642323
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 Write m in base w. let b[i] be the i'th least significant number in the representation m in base w.Loop over m (in base w) from right to left (from least significant to most significant).Then if b[i] is 1, we can match it using (w^i). if b[i] is w - 1 then we can add w^i to the balance side of m. Then the representation of m becomes such that b[i] = 0 and b[i + 1] = b[i + 1]+1. so we increase b[i + 1] by 1. Notice this could lead to have b[i + 1] equals to w in this case we should repeat the last case on b[i + 1] (i.e increase b[i + 2] by 1 and make b[i + 1] = 0).the last case if b[i] > 1 and b[i] != w — 1 and b[i] != w we cannot represent m.In contest I did not handle case where b[i] = w. But when i did (after contest) the solution passed all the cases) 11654584
•  » » 4 years ago, # ^ |   +8 My solution was not brute force. You can convert m to base w. Then iterate from least significant digit to most significant digit. If a digit d[i] =0 or d[i] = 1 then skip it (w^i is either skipped or added to the set). If d[i]==w-1 or d[i]==w, then subtract w from it, and add 1 to the next higher value bit (d[i+1]+=1). d[i] will become either 0 or -1 (w^i is skipped or added to the other set). This works because subtracting w from a digit is equivalent to adding 1 to the next higher digit. If d[i] is anything else, then it is not possible. complexity: O(logw(m))
 » 4 years ago, # |   +1 I’m so weak.QAQ
 » 4 years ago, # |   0 I thought C was about DP by assigning -1,0,1 weight to each power of 'w' to get 'm'. But then i realized, (10^9)^100 is impossible to calculate by the methods I know :( .
•  » » 4 years ago, # ^ |   0 I had the same idea! Also had no idea how to implement it. Although I believe that there's a O(1) solution. If that's true — can somebody give a hint? Thanks in advance.
•  » » » 4 years ago, # ^ |   0 Like, exploiting some properties of 'm'... but I couldn't think of any.
•  » » » 4 years ago, # ^ |   0 I took advantage that you won't ever need a power bigger than 10^9, so you can just compute the biggest power of m which is lower than that number, and do it your way.I did it recursive by brute force using that, taking into account that if w^k > m, you don't need w^(k + 1), because the sum of all the powers of w below w^k is less than w^k.Hope I made myself clear, sometimes I find it difficult to explain these things :P
•  » » » » 4 years ago, # ^ |   0 Yes got it!
•  » » 4 years ago, # ^ |   +24 We have to find a solution to this equation: m=a0+a1*(w)+a2*(w^2)+...+a100*(w^100), where -1<=ai<=1 and ai is integer If w=2, then it is always possible, because every number have a binary representation. Let's calculate a0 when w>=3: m-a0=a1*(w)+a2*(w^2)+...+a100*(w^100) Note that m-a0 must be a multiple of w, moreover (m-1)%w != m%w != (m+1)%w. So there are just one possibility for a0. After calculating a0, we can divide both terms by w and repeat the process;
•  » » » 4 years ago, # ^ |   0 Wow! That's even better than DP!
•  » » » 4 years ago, # ^ |   0 Great explanation. Thanks. I had figured out half of the solution but sadly couldn't figure out the better half :(. Nice problem :)
•  » » » 4 years ago, # ^ |   0 what is ai ? And how its -1 <= ai <= 1 ?
•  » » » » 4 years ago, # ^ |   0 ai is the choice for the ith weight. If you put it on the left side, it is -1, if you put in the right side 1, and if you don't use it 0
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Nevermind, got it.
•  » » 4 years ago, # ^ |   0 You don't know python 11645160
 » 4 years ago, # |   0 Top 5 Filled with unrated users
•  » » 4 years ago, # ^ |   +12 some things never change
•  » » 4 years ago, # ^ |   0 I guess now-a-days they are getting caught and discluded from final standings.
 » 4 years ago, # |   0 Good set of problems. Thank you author :)
 » 4 years ago, # |   +7 I just saw the 4 seconds time limit for problem D, now I think it should be B instead.
 » 4 years ago, # |   0 OMG very very Good problemsI love (short problem & good problem) that this problems are short and good so I love this problems so I love this contest so I'm crazy
 » 4 years ago, # |   +3 C and D have the same number of accepted submissions.
 » 4 years ago, # |   0 Nice Contest , also with strong pretest cases.
 » 4 years ago, # |   +44 If the N^3 complexity for the Problem D Passed, How It Can Be D??
 » 4 years ago, # |   0 why gnu inbuilt pow function fails?
•  » » 4 years ago, # ^ |   0 same here
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 i got Wrong Answer on Pretest 6. But my GCC Compiler shows the correct output required!
•  » » » » 4 years ago, # ^ |   0 Expected answer has 96 in the end, your code produces 89.
•  » » » » » 4 years ago, # ^ |   0 Dude, Read my comment properly.
•  » » » » » » 4 years ago, # ^ |   0 Sorry, my bad.
•  » » » » 4 years ago, # ^ |   0 same issue mate.
•  » » » 4 years ago, # ^ |   0 I think because it returns a double value and not integer.
 » 4 years ago, # |   +31 Is a O(n3) solution worth 2000 points? Seriously?
 » 4 years ago, # | ← Rev. 2 →   0 For Problem D,Is the approach of total triangles(nc3)-triangles formed by collinear points(found using overlapping straight lines,ie,equal slopes) wrong? I was getting wa on 4th test case. here is my code http://codeforces.com/contest/552/submission/11654496
•  » » 4 years ago, # ^ | ← Rev. 3 →   -9 ignore it
•  » » » 4 years ago, # ^ |   0 How come length is accounted into the picture? I am first finding the total no of triangles using nc3. Dont you think nc3 contains those triangles which are formed from collinear points..I think I need only to remove them..please explain
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -9 ignore it
•  » » 4 years ago, # ^ |   0 Not just equal slopes, because parallell lines have equal slopes, but you must treat parallell lines separately.
•  » » » 4 years ago, # ^ |   0 thanks!! Got it
 » 4 years ago, # | ← Rev. 2 →   +27 Are you serious?And it occured to nobody that some guys could write such solutions?
•  » » 4 years ago, # ^ |   +9 Really not justice for people who wrote n^2logn solution -_-
•  » » » 4 years ago, # ^ |   +6 Yeah, and I have an N^2logN solution which gave TL :PBTW, I got TL#7 with unordered map/unordered set and TL#13 with map/set :D
•  » » » » 4 years ago, # ^ |   +4 Same story
•  » » » » 4 years ago, # ^ |   0 I got AC with an n²logn solution , maybe your algorithm constant is a little high , try to optimize your code.Solution
•  » » » » » 4 years ago, # ^ |   0 try to optimize your code I did it and it passed on the 10th attempt :D Thanks anyway! :)
•  » » » 4 years ago, # ^ |   +6 Yeah :( The time limit should have been 2 sec. It would be worth solving it.
•  » » 4 years ago, # ^ |   +8
 » 4 years ago, # | ← Rev. 3 →   0 hey guys...in Problem B...Vanya and Books... it shown in test-6 my answer is wrong..for n=1000000 the result is 5888895 and the correct answer is 5888896 but when i run my code in terminal(g++) the output is 5888896.I used GNU C++ to submit. My Code: http://codeforces.com/contest/552/submission/11650994 Why this is happening?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I have the same issue.expected: '8888888899', found: '8888888895'Though in my terminal the code gives 8888888899 as the answer.
•  » » » 4 years ago, # ^ |   0 In fact i ran my test in ideone...it showing correct answer too!! http://ideone.com/tC7xB0
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 same!! http://ideone.com/yycBrQ thanks to this bug my rating has gone down further.
•  » » 4 years ago, # ^ |   0 My guess is that it is due to different casting behaviors.If you cast pow(10,count-1) to long long int immediately, you will get AC.
•  » » » 4 years ago, # ^ |   0 Did that too... Still didnt work http://codeforces.com/contest/552/submission/11652803
•  » » » 4 years ago, # ^ |   0 I have done the same with all the type castings correct but didnt work for me
 » 4 years ago, # |   0 My C Solution: http://codeforces.com/contest/552/submission/11647965 So basically, if we look at everything mod w, the only weight that matters is one, because everything else is zero. So if there is a way to get this to work, we can change the current weight and divide by w. Recursively, this gives the correct answer. Surprised at high number of TLE's, I guess..
 » 4 years ago, # | ← Rev. 2 →   0 Just want to clarify for problem C,we have to put weight(s) on both sides, right? If so, I'm curious that for a case that M = 1, W = 3, it's impossible to do so; however, we're still able to balance the pans by putting the weight on only one side, that is, put w^0 on the other pan.
•  » » 4 years ago, # ^ |   0 yes.
•  » » » 4 years ago, # ^ |   0 So, why is the answer to this test YES, instead of NO?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 W^0 on one side and m on other.
•  » » » » » 4 years ago, # ^ |   0 I now got it. I first thought that we have to put weight(s) on both sides. Thanks.
•  » » 4 years ago, # ^ |   0 You can put weights on both sides but you don't always have to.
•  » » » 4 years ago, # ^ |   0 Got it. Thanks. I first assumed from the problem's statement that we have to put on both sides.
•  » » » 4 years ago, # ^ |   0 any one with recursive solution ?? for proble C mine gives TLE http://codeforces.com/contest/552/submission/11654141
 » 4 years ago, # |   +5 B solution 11647913... why not.
•  » » » 4 years ago, # ^ |   0 just wow!
 » 4 years ago, # |   0 Hi all.552E - Ваня и скобкиCould anyone explain the following judge?Input 9*8+7*6+5*4+3*2+1 Participant's output 837 Jury's answer 1987 Checker comment wrong answer 1st numbers differ — expected: '1987', found: '837'
•  » » 4 years ago, # ^ |   0 9*(8+7*6+5)*4+3*2+1=1987
•  » » » 4 years ago, # ^ |   0 I assumed bracket pair as {a op b}. Got it. Thanks..
•  » » 4 years ago, # ^ |   0 Actually i didn't solve it...but for your query it because 9+(8+7*6+5)*4+3*2+1=1987 :)
•  » » » 4 years ago, # ^ |   +8 Lol teleport....u literally teleported before i could answer
•  » » 4 years ago, # ^ |   0 9*(8+7*6+5)*4+3*2+1=1987
 » 4 years ago, # | ← Rev. 2 →   0 Is this logic correct for E: you will place bracket between * and * and if only 1 * then the bracket is either on left or right of it. So precalculating using DP= t= |s|^2.Total time=t + k^2, where k=number of * in expression(<=15).
 » 4 years ago, # |   0 my second submission for question 308B is correct according to ideone compiler but it gives wrong answer in codeforces compiler.
•  » » 4 years ago, # ^ |   0 same here...dont know why?
 » 4 years ago, # |   0 I liked your contest not just because of the good problems but also because of fast rating change.(I got specialist though)
 » 4 years ago, # |   0 accepted solutions of problem D should be rejudged with stricter time limit so that O(n^3) solution timeout. Then only standings will become fairer.
 » 4 years ago, # |   +3 pow()... :-|
 » 4 years ago, # |   0 My compiler gives ri8 ans bt codeforces compiler gives wrong ans I don't know why?
•  » » 4 years ago, # ^ |   0 My Code My compiler gives ans 17
 » 4 years ago, # |   0 I have a question guys. My code for problem B: 11655174 seems to return 99 when calling pow(10ll,2). I notice this does the same on my mingw, but returns 100 correctly on g++ and ideone. Is there any reason for this?
 » 4 years ago, # |   0 Check ur new rating. Really fast rating.
 » 4 years ago, # |   +80 Nice!!!
 » 4 years ago, # |   +22 Yay, finally in Div 1.
 » 4 years ago, # |   0 in submission my code fails on the third test case 100 output 193 but copying the code and running it on ideone and then running it on same test case gives the correct answer http://ideone.com/UdTLjMhttp://codeforces.com/contest/552/submission/11644910
 » 4 years ago, # |   0 For ProblemB 'Vanya and Books' my answer is not 'Accepted' with the message saying "wrong answer on test 18'. But when I re-run the same code it gives me correct output. Don't know how the program gave an invalid output out of the blue. My SubmissionAm sort of new to Codeforces, my apologies if this is not the correct place to put forth such queries.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Your code is awesome, but you forgot one thing. You have taken all necessary variables in long long int but n!Your code works fine up to 8-digit. Even works for some 9-digit numbers too. But fails for large 9-digit numbers. Why? because, you need to do multiplication in long long.For 9-digit and 10-digit number, re-think about the lines: res += (n-99999999) * 9; and res += (n-999999999) * 10; respectively.Say, n = 999999999. Then what would be the calculation of (n-99999999) * 9 portion?= (999999999-99999999) * 9= (900000000) * 9 = 8100000000 which is a 10-digit number and could not fit in long int.So, change the line long int n = 0; into long long int n = 0; and get Accepted!Another thing I have noticed in your code that you have used the same variable n as local and global at the same time. It is a bad practice for programming contest. Sometimes, it could massacre your contest!Thanks and sorry for my bad English as well as bad explanation. Happy Coding!
•  » » » 4 years ago, # ^ |   0 Thanks a lot for taking a look. My mistake :( .
•  » » » » 4 years ago, # ^ |   0 Thanks you too. :)
 » 4 years ago, # |   0 In case anyone is interested there is a way to solve problem C trivially without a computer if you are given the base w expression of n. My solution uses this approach, it runs really fast, you don't need to calculate anything, you just need to read the base w expression.
 » 4 years ago, # |   0 In problem B,my solution is working fine for a particular output on my system but its giving a different output when i submit the same solution.This was my submission 11656471 Is it because i am using long long int and lld specifier? In which cases does the online compiler might behave differently than my local system?Thanks
•  » » 4 years ago, # ^ |   +3 It is for your (long long int)pow(10,(double)x). Be careful to use pow function. It is very dangerous! It calculates in double, so precision error occurs. Just handle it manually. Thanks in advance.
 » 4 years ago, # |   +1 my solution of second at 5th test case is giving ryt answer in all other compilere like ideone etc....herein code force compiler it is giving wrong answer.....how is it even possible
•  » » 4 years ago, # ^ |   0 same here
 » 4 years ago, # |   0 Why liyankui was skipped?
•  » » 4 years ago, # ^ |   +31 妈的手速快就要被skipped? 管理员可不可以出来解释下？？
•  » » » 4 years ago, # ^ |   -8 谁让你32秒切一题。。rank2都看不下去了
 » 4 years ago, # |   +10 为什么liyankui会skipped? 有老司机出来解释下嘛？
 » 4 years ago, # |   -11 题目太简单都是liyankui的锅！
 » 4 years ago, # |   -13 5道程序代码风格完全一样，程序没有雷同。凭什么skipped？ 哦你可能说有5个人同时在做，妈的做这种sb题liyankui需要开挂？
 » 4 years ago, # |   -41 随随便便就封号？ 封你mb! why are you so diao?
 » 4 years ago, # |   -57 我喷你了这么多，是不是也该把我封了啊？ 哦对你是毛子看不懂中文哦！ 我推荐用有道翻译！
•  » » 4 years ago, # ^ |   +11 Mind your language. If you really want to complain, go open a new thread and use English. Stop embarrassing yourself here.
•  » » » 4 years ago, # ^ |   -24 sorry,I'm so angry just now。
•  » » 4 years ago, # ^ |   -8 go and learn English!
 » 4 years ago, # |   +1 Awesome contest !!! C and D were good but O(n^3) wasn't fair !! finally div1 !!! P.S:- Very Happy
 » 4 years ago, # |   -18 I'm so sorry for my behavior just now ..
•  » » 4 years ago, # ^ |   +41 No problem, I didn't understand anything either way.
 » 4 years ago, # |   +3 Hello, Div.1!!! Looking forward to the next round!
 » 4 years ago, # |   0 Whats the mathematical principle for problem C? I have seen some solutions they are operating on m (decrementing and incrementing according to divisibility by w which so conveniently uses powers of w only once) but cant seem to figure out how they came up with the solution e.g.11657140
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I don't know how that solution specifically works. But I notices that the base w representation of n can only have the following digits:0 (this can appear without any restriction)1 (this can appear only if the digit to the right is 0 or 1)w-1 (this can appear without restriction)w-2 (this can appear only if the digit to the right is (w-1 or w-2)Just read the base w representation and check if all the digits are as mentioned above.
 » 4 years ago, # |   0 Still waiting for tutorial....
•  » » 4 years ago, # ^ |   +6 Don't just wait. Look around :)
•  » » » 4 years ago, # ^ |   0 thanks man, usually i see link to tutorial at problemset
•  » » » 4 years ago, # ^ |   +1 Tnx. Why it's not in problems page!
 » 4 years ago, # |   0 Where is tutorial?!
•  » » 4 years ago, # ^ |   0
»
4 years ago, # |
-6

question about problem D: can anybody explain why my O(n^3/6) solution was not accepted? here is the code #include

# include

using namespace std;

struct point{ int x,y; };

int n; point p[2005];

int main() { cin>>n; for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y; int s=0; for(int i=0;i<n;i++) for(int j=i;j<n;j++) for(int k=j;k<n;k++) { if(i!=j && i!=k && j!=k) { int x1=p[j].x-p[i].x; int y1=p[j].y-p[i].y; int x2=p[k].x-p[i].x; int y2=p[k].y-p[i].y; if(abs(x1*y2-x2*y1)!=0) s++; } } cout<<s; return 0;
}

 » 4 years ago, # |   0 question about problem D: can anybody explain why my O(n^3/6) solution was not accepted? here is the code 11645613
•  » » 4 years ago, # ^ |   0 You need to optimize your code for a brute force approach. You can get rid of the if statement in the inner loop by starting j = i+1 and k = j+1. Also move the x1, y1 computation one level higher so that it will not be recomputed for every k.It passes then 11670552
 » 4 years ago, # |   0 I have been getting WA for the problem B , my code runs fine in even in IDEONE and my c++ compiler for th same test case for which it is failing and giving a WA in codeforces compiler so what could be the problem ?????????? Am really confused
•  » » 4 years ago, # ^ |   0 My Submission ID is 11639371
•  » » » 4 years ago, # ^ |   0 i think pow() function is causing the trouble . pow() returns double so when you calculate pow(100,5) instead of returning 100000(10^5) it will return 99999 . So may be that's the one causing the trouble . Try printing the value of pow(10,i) and then run the test case your code fails upon. Good Luck
 » 4 years ago, # |   -8 Editorial, please -
•  » » 4 years ago, # ^ |   +1 u got it http://codeforces.com/blog/entry/18696 dont always check the contest page for tutorial . check the blog too :)
•  » » » 4 years ago, # ^ |   0 thx :D
 » 4 years ago, # | ← Rev. 4 →   0 Can someone help me with my question B submission, its running fine on online compilers ? Here is the link: http://codeforces.com/contest/552/submission/11640318 Edit : Got it after reading the editorial !
 » 4 years ago, # |   0 Can somebody please elaborate the Problem C editorial? Whats the concept behind the solution. Why the number m needs to be converted to base w.
•  » » 4 years ago, # ^ |   +1 OK I'll try . — we need to find if solution to equation M=w^0*a0 +w^1* a1 + w^2*a2.... Exist or not . This equation is equal to M-w^0*a0 =w^1 *a1 + w^2*a2.... Rhs has a common factor of w so lhs should be divisible by w . a0 can have 3 values -1 ,0,1 We try all cases of a0 and check if Lhs formed is divisible or not. Since w^0 is 1 we have m-1 , m+1, m. If any of the three is divisible my w. That would be new value of m. And equation now becomes m'= w^0 * a1 + w^1 *a2.... Which is solved similarly untill we reach a point such that m,m+1,m-1 is not divisible by w by m( answer doesn't exist) becomes 1 (possible)
•  » » » 4 years ago, # ^ |   0 Thanks speedster. Well explained.I got it now.
•  » » » 4 years ago, # ^ |   0 Have a look to my explanation for this problem. Happy coding. :)Explanation to Div2 CHere is my submission. 11776192
•  » » 4 years ago, # ^ |   0 where are the editorials of the problems ?
•  » » » 4 years ago, # ^ |   0 http://codeforces.com/blog/entry/18696click on author profile, then click blogs
 » 4 years ago, # |   0 wow, all top 5 winners had their first contest, kinda neat :)
 » 4 years ago, # |   0 uw_ttocs
 » 4 years ago, # |   -16 Congratulations to the real winners!Real Div.2 winners:
 » 4 years ago, # |   0 when will the editorial be available?
 » 4 years ago, # |   0 Can you give me an editorial, Wild_Hamster?
 » 4 years ago, # |   0 My Code is giving different output on codeforces system and ideone.Can Someone please explain me why is this happening ?for test 5 781 on cf , o/p is : NO on my system and Ideone o/p is : YES
 » 4 years ago, # |   0 hello to all. i want to understand why my 11724541 code get run time error. thanks to all.
 » 4 years ago, # |   0 Is there an editorial? if not can somebody help me with Div2 C?
•  » » 4 years ago, # ^ |   0 Have a look to my explanation for this problem. Happy coding. :)Explanation to Div2 CHere is my submission. 11776192