Приветствую сообщество Codeforces.
18 июня 2015 года в 19:30 MSK состоится очередной раунд Codeforces #308 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.
Это мой второй Codeforces раунд(первым был раунд Codeforces Round 280 (Div. 2)). Надеюсь, он вам понравится.
Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение.
UPD: Разбаловка стандартная: 500-1000-1500-2000-2500.
UPD: Поздравляю победителей:
UPD: Контест закончен. Всем спасибо за участие :)
UPD: Разбор задач
Автокомментарий: текст был обновлен пользователем Wild_Hamster (предыдущая версия, новая версия, сравнить).
i hope this round has harder problems than round #280.
Your last round was interesting and solvable ! I believe it will be easier than round 307 :)
Tell me allllekssssa, you are a fan of PrinceOfPersia aren't you? :P
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
Ya, I found his contest questions really interesting...:)
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
You are really lucky to get your solution for D passed! :P :D
I'm a lucky bastard :3
My history:
First Codeforces round participation = round #235
First Codeforces round to get in div1 = round #263
difference in number of rounds = 28
Your history:
First round = 280
First round to get in div1 = 308
difference = 28
And 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 :)
Happy Ramadan holiday to all. I wish luck for today's contest to every participants.;)
Happy to you as well.
Всем УДАЧИ!))) Хочу сегодня стать синим))))))
Синим ещё куда не шло, главное голубым сегодня не стань :-)
шутки про голубых не для таких сайтов, как Codeforces
а какие шутки для таких сайтов как Codeforces?
Например такие: Однажды ты спросишь меня, что для меня на первом месте: ты или программирование? Я отвечу тебе, что ты. Но ты никогда не узнаешь, что программирование для меня на нулевом месте:)
Шикаррррно)))
про молоко
Зачем же сразу минусовать? Человек с чувством юмора. Ничего плохого нету ;)
а я думал что я тут слабый, всего-то фиолетовый, а тут люди синими мечтают стать
Izi problem, izi life
How many times have you written this in the announcment?
[croaker mode on]
Three times.
[croaker mode off]
izi is love, izi is life
I hope this round have some problems which i am not able to solve.
then u should attempt div 1 mate !!!
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.
Wild_Hamster has a recursive profile pic
how did you make it
His profile pic is in Russian, but my interface is in English :)
Also the rating and contribution are different.
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.
блиииин, забыл зарегатся(((((
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 !!!
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 !!!
I hope that there will be no delay, no lag near the end of contest, and no cheaters :)
I think it's time to publish scoring
When you know you are closest user to Div.1 but you know it will not be happen :(((
better change your user to BornToBeLoser, it will suit you better
it's your second round be patient! :3
Especially, when you BornToBeWinner :)
Please announce scoring.
Help please register me for this contest please.There is still time left.Please
Пропустил регистрацию можно что то сделать?
Please Register me for this round please.Please
Bro :(
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!
codeforces everyday growing! Keep on!
5-10 seconds of the highest quality drama on every submit! (Jaws music on the background) :)
For me it's really interesting why each Div2 round there are persons like this http://mirror.codeforces.com/profile/liyankui who solves all the problems without participating in any other contest before.
I'm gonna be captain obvious here in case there's someone that doesn't know — Div1 users make new accounts to win Div2.
Ok, what is the goal of doing it?
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.
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.
Its not programming contest, its math contest...
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.
C is brute force :D
when 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
not necessarily, my solution uses 100 iterations only
http://mirror.codeforces.com/contest/552/submission/11642323
ok I didn't say it can't be solved faster but constraints allow brute force to pass
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.
how did you know that you will not use more than the first 16 weights ?
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.
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!
3^16 brute force can be optimized with meet-in-the middle approach to do it in 2*(3^8)
we can solve C in O(log n)
Sorry, But how do you know that you will not use more than 16 weights? Is it depending on maths?
Yeah, w^0+w^1+w^2+...+w^(n-1) < w^n holds for w>=2 :)
Is it possible to find some weights more than w^16 to get the scale balanced ? If not , Can you explain that , please ?
Great! contest was very interesting! thanks to author
По задаче D, я не смог взломать решение за O(n3 / 6). Такое вроде не должно было проходить.
А кто-нибудь решил её быстрее, чем за N^2logN?
Ну логарифм вроде можно убрать. Но зачем?
У вас логарифм от сортировки? Так она не нужна, можно просто пихать отрезки в какую-нибудь HashMap, чтобы находить кол-во отрезков, не совпадающих с данным.
Там 4 секунды... Я такое решение сам у себя пробовал на C# — чуть чуть не укладывалось (5-6 сек было), так что на плюсах должно было пройти.
подскажите 5 тест на B, пожалуйста.
переполнение инта, подозреваю
I have mistake in problem C :(
Problem D is classic, but I don't love geometry...
I think D has less geometry than it seems to have.
but how do figure out how many collinear sets we have ? after that it would be normal permutations and combinations.
I didn't think about it a lot, but my solution have calculating coefficients , sortings and after that line sweep. Maybe I wrong ?
D was also a brute force.
As time limit for D was 4sec.
It's sad that very few noticed it. :(
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.
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
roughly 4 *10^8 iterations are there in 1 sec
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
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.
two WA due to inbuilt gcc pow function:( in 308-B never using it again...
Yea, I realize now that my 308B is wrong ;_;
Same here, Don't understand why gcc pow function fails though ?
same problem ....faced twice on codeforces
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.
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.
I know that feel bro.
Try powl someday or use pow with nearbyint ...
Решение задачи Д был перебор всех треугольников? У меня на претесте 13 выдало превышение времени :(
Нет. Давайте почитаем число плохих троек точек(точек, лежащих на одной прямой). Переберем одну из точек тройки и покидает в set направляющие векторов от этой точки до всех остальных. Пусть у нас x раз встретился некий вектор. Тогда уменьшим ответ на x(x-1)
Условия задач короткие — реальные задачи! Браво автору! Краткость — сестра таланта
I like so much problem C
How do you solve C ? Someone please explain the solution. Thanks :)
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?
Eval gets Tl, doesn't it?
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.
Got it, thanks.
built-in eval && regex * regex, upsolved: 11658690
Yes, I was a bit surprised my solutions passed on those problems. The TL for D and E should have been tighter.
What was wrong with this approach for problem C? http://mirror.codeforces.com/contest/552/submission/11653548
I 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 cases
EDIT:GOT AC.Used same concept but properly handled corner cases this time :)
check for w=3 and m =17
Try to debug . It gives WA for 4 11 Your output NO Correct YES; 11 + 4 + 1 = 16
Got AC.Thanks
I tested my D solution for the worst case and it ran fast enough
I wonder can O(n^3) pass ? hope it will
no
I tried and got time limit error
are you sure ? my solution passed with O(n^3) complexity!
yes
not passed for me O(n^3)
did you use Cpp language for submit?
yes
If you use long long ints with n^3 I got a TLE, with ints and n^3 it got an AC
I submitted O(N^3/6) and it passed the pretests.
UPD: My solution also passed system tests.
Depends. I've tried on C# — it was like 5-6 seconds. So probably C++ could pass.
I think O(n^3) is too slow, but we will see.
IT PASSED :D
my first time to solve problem D during contest :D
Should it pass? If yes, then why?
I used n^2logn and it took me long time and cost 1 submission. :(
O(n3)??? This is the first thing I thought and then I spent all the contest trying to optimize to O(n2logn). Sad!!!
same thing happened to me. D should be rejudged be with proper test cases!!
http://mirror.codeforces.com/contest/552/submission/11663481
http://mirror.codeforces.com/contest/552/submission/11663430
C++ VS Java
You just use Java in a wrong way: 11665530.
what's the difference?
both use BufferedReader for input O(n^3) time complexity and PrintWritter for output
why your code runs faster?
Magic!
Actually constant factor is important. In deepest place in my code I do one subtraction (compare to 5 subtractions in your code).
OK thanks
Use Math tags for all of the problems :D
Nice contest thanks:)
Could someone explain the solution for C ? Thanks :)
wait for the editorial
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.
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.
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).
https://en.wikipedia.org/wiki/Balanced_ternary
I just found this looking for ternary base, so it looks like it's possible.
Because you should output YES immediately when w=3 , when w>3 use brute force
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" .
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 this
http://mirror.codeforces.com/contest/552/submission/11642323
Write
min basew. letb[i]be the i'th least significant number in the representationmin basew.Loop over
m(in basew) 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] isw - 1then we can addw^ito the balance side ofm. 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
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))
I’m so weak.QAQ
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 :( .
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.
Like, exploiting some properties of 'm'... but I couldn't think of any.
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
Yes got it!
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;
Wow! That's even better than DP!
what is ai ? And how its -1 <= ai <= 1 ?
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
Nevermind, got it.
You don't know python 11645160
Top 5 Filled with unrated users
some things never change
I guess now-a-days they are getting caught and discluded from final standings.
Good set of problems. Thank you author :)
For Problem D,
Is the approach of total triangles(nc3)-triangles formed by collinear points(found using overlapping straight lines,ie,slopes) wrong? I was getting wa on 4th test case. here is my code http://ideone.com/k8J9Zu
Контест мне понравился
НЕ ОЧЕНЬ.
I just saw the 4 seconds time limit for problem D, now I think it should be B instead.
OMG very very Good problems
I 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
C and D have the same number of accepted submissions.
Nice Contest , also with strong pretest cases.
If the N^3 complexity for the Problem D Passed, How It Can Be D??
why gnu inbuilt pow function fails?
same here
i got Wrong Answer on Pretest 6. But my GCC Compiler shows the correct output required!
Expected answer has 96 in the end, your code produces 89.
Dude, Read my comment properly.
I think because it returns a double value and not integer.
как то не серьезно что в D проходит тупой перебор
У меня (n^2)*log(n^2) не проходило, ну там конечно map.
ТУПОЙ ПЕРЕБОР, КАРЛ! 11650147
Вполне нормально по сути: 2000^3/6 * const = 1.3 * 10^9 * const оперцаии, const = 2 операции умножении и 4 операции разницы. Запросто уложится в 4 секунды.
Is a O(n3) solution worth 2000 points? Seriously?
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://mirror.codeforces.com/contest/552/submission/11654496
ignore it
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
ignore it
Not just equal slopes, because parallell lines have equal slopes, but you must treat parallell lines separately.
thanks!! Got it
Are you serious?
And it occured to nobody that some guys could write such solutions?
Really not justice for people who wrote n^2logn solution -_-
Yeah, and I have an N^2logN solution which gave TL :P
BTW, I got TL#7 with unordered map/unordered set and TL#13 with map/set :D
Same story
I got AC with an n²logn solution , maybe your algorithm constant is a little high , try to optimize your code.
Solution
I did it and it passed on the 10th attempt :D Thanks anyway! :)
Yeah :( The time limit should have been 2 sec. It would be worth solving it.
Are you serious ? :P
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://mirror.codeforces.com/contest/552/submission/11650994 Why this is happening?
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.
My C Solution: http://mirror.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..
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.
yes.
So,
why is the answer to this test YES, instead of NO?
W^0 on one side and m on other.
I now got it. I first thought that we have to put weight(s) on both sides. Thanks.
You can put weights on both sides but you don't always have to.
Got it. Thanks. I first assumed from the problem's statement that we have to put on both sides.
B solution 11647913... why not.
How about this 11637651
just wow!
Hi all.
552E - Vanya and Brackets
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'
9*(8+7*6+5)*4+3*2+1=1987
I assumed bracket pair as {a op b}. Got it. Thanks..
Actually i didn't solve it...but for your query it because 9+(8+7*6+5)*4+3*2+1=1987 :)
Lol teleport....u literally teleported before i could answer
9*(8+7*6+5)*4+3*2+1=1987
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).
I liked your contest not just because of the good problems but also because of fast rating change.(I got specialist though)
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.
pow()... :-|
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?
Check ur new rating. Really fast.
Check ur new rating. Really fast rating.
Лол. Тесты #1 и #11 в задаче B совпадают.
Nice!!!
I read E outputs and there where all integers i taught i should use bignum and didn't solve it you should have garenteed that the answer is int or long long
Yay, finally in Div 1.
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 Submission
Am sort of new to Codeforces, my apologies if this is not the correct place to put forth such queries.
Your code is awesome, but you forgot one thing. You have taken all necessary variables in
long long intbutn!Your code works fine up to
8-digit. Even works for some9-digitnumbers too. But fails for large9-digitnumbers. Why? because, you need to do multiplication inlong long.For
9-digitand10-digitnumber, re-think about the lines:res += (n-99999999) * 9;andres += (n-999999999) * 10;respectively.Say,
n = 999999999. Then what would be the calculation of(n-99999999) * 9portion?= (999999999-99999999) * 9= (900000000) * 9= 8100000000which is a10-digitnumber and could not fit inlong int.So, change the line
long int n = 0;intolong long int n = 0;and getAccepted!Another thing I have noticed in your code that you have used the same variable
nas 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!Thanks a lot for taking a look. My mistake :( .
Thanks you too. :)
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.
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
It is for your
(long long int)pow(10,(double)x). Be careful to usepowfunction. It is very dangerous! It calculates in double, so precision error occurs. Just handle it manually. Thanks in advance.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
Why liyankui was skipped?
妈的手速快就要被skipped? 管理员可不可以出来解释下？？
谁让你32秒切一题。。rank2都看不下去了
为什么liyankui会skipped? 有老司机出来解释下嘛？
5道题目代码风格完全一样 还TM封号？？？ 给我一个liyankui作弊的理由！ 题目太简单怪liyankui咯？
题目太简单都是liyankui的锅！
5道程序代码风格完全一样，程序没有雷同。凭什么skipped？ 哦你可能说有5个人同时在做，妈的做这种sb题liyankui需要开挂？
随随便便就封号？ 封你mb! why are you so diao?
我喷你了这么多，是不是也该把我封了啊？ 哦对你是毛子看不懂中文哦！ 我推荐用有道翻译！
Mind your language. If you really want to complain, go open a new thread and use English. Stop embarrassing yourself here.
sorry,I'm so angry just now。
go and learn English!
Awesome contest !!! C and D were good but O(n^3) wasn't fair !!
finally div1 !!!
P.S:- Very Happy
I'm so sorry for my behavior just now ..
No problem, I didn't understand anything either way.
Hello, Div.1!!! Looking forward to the next round!
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
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.
Still waiting for tutorial....
Don't just wait. Look around :)
Tnx. Why it's not in problems page!
Where is tutorial?!
http://mirror.codeforces.com/blog/entry/18696
question about problem D: can anybody explain why my O(n^3/6) solution was not accepted? here is the code 11645613
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
Editorial, please -
u got it http://mirror.codeforces.com/blog/entry/18696 dont always check the contest page for tutorial . check the blog too :)
thx :D
Мне кажется, или немного странно, что второе и треть место заняли люди с такими никами?
Can someone help me with my question B submission, its running fine on online compilers ? Here is the link: http://mirror.codeforces.com/contest/552/submission/11640318 Edit : Got it after reading the editorial !
http://mirror.codeforces.com/contest/552/problem/C
никак не могу понять алгоритм решения задачи С, помогите пожалуйста, смотрел правильные решения, но всё равно не понял
1) Любое число представимо единственным образом как сумма степеней w-шек.
2) Нам никогда не понадобится использовать гири, весом больше чем wlogw(109) + 1, для w ≥ 3. Ибо представим, что существует ответ и там есть гиря максимального веса (пусть на левой стороне), которая ≥ чем ограничение выше. Тогда утверждается, что на правой стороне мы никак не сможем набрать столько же. Ибо там все гири весом меньше, а это легко доказать что
. Причём разница между левой и правой частью будет больше чем 109, поэтому на какую сторону не добавь m, равенства всё равно не будет.
3) Ну и всё. Получили решение. Для двойки yes. Для остальных: посчитаем какой вес, какой маске соотвествует. Это в худшем случае займёт 220. Потом будем ставить на ту сторону где m, различные наборы гирь (маски), и пробуем положить на правую сторону столько же массы. Если получается это сделать двумя различными наборами гирь, то ок.
Мб излишне сложно, но как есть:)
http://mirror.codeforces.com/contest/552/submission/11643866
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.
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)
where are the editorials of the problems ?
http://mirror.codeforces.com/blog/entry/18696
click on author profile, then click blogs
wow, all top 5 winners had their first contest, kinda neat :)
uw_ttocs
uw_ttocs
Can you give me an editorial, Wild_Hamster?