Доброго времени суток!
19 января 2017 года в 18:05 MSK (время московское) состоится очередной раунд Codeforces #392 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Будет предложено 6 задач и 2 часа на их решение.
Хотелось бы сказать большое спасибо Николаю Калинину (KAN) и Алексею Вистяжу (netman) за помощь в подготовке задач, Татьяне Семёновой (Tatiana_S) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также за помощь в подготовке контеста и идеи нескольких задач.
Это мой второй раунд, надеюсь он понравится вам больше чем первый. Желаю всем честного рейтинга!
UPD: Разбалловка 500 — 1000 — 1500 — 1750 — 2500 — 3000.
UPD: Разбор!!! Огромное спасибо Пикляеву Мише (awoo) и Татьяне Семёновой (Tatiana_S) за перевод разбора на английский.
Поздравляем победителей!
Div. 2
I wolf29
II alexwice
III WhyamIhere
4 TaTaPiH
7 djqtxdy
8 whzzt
9 Lucas97
10 Clayton
Div. 1
I W4yneb0t
II sd0061
III irkstepanov
4 wolf29
8 kmjp
your last contest was really interesting Codeforces Round 378 (Div. 2) I hope we will see the same this time too :D
Yeah Epidemic in Monstropolis was probably one of the most interesting problems I've done in contest.
Driver's dissatisfaction also had a great idea within it.
Looking at the problem statements, I hope everyone knows that 'Y' is a vowel.
as long as he mentions it in the problem description, he can make 'Z' a vowel, or even a digit :3
:'v
This contest was interesting(especially for E)!!! Thank you Sergey Kniaz Kniazevskiy.
magic
His miracle minute.
short announcement... I hope problem statements will be the same
But what if... Kniaz had a limited number of symbols and wanted to use more of them in statements? Think about it!
by 'short' I actually meant 'clear'. We expect a clear and well-understandable problem set.
short means short
Yes, short means short, but Least_but_not_the_last was not claiming that “short” equals “clear”. He was correcting a mistake in word choice. i.e. “I said short by mistake but I realy wanted to say clear”.
The usual question. Yes or no?
the usual answer — yes
I really liked your last contest, especially the Problem F. Thanks for the contest again! :)
But I really disappointed about this contest :(
Anyway, please ignore me.. this is just a loser's comment.
WHY THE HELL X and Y means row and column?!?!
I hope there will be shorter statement and more interesting solutions :P
I am in Korea so I need to get waked up at 00:05
I am in Australia so i have to get up at 2am
I rarely sleep at 2am ;)
recent cf rounds' time are so bad to UTC+11, like either 2am or 4am, GG
What is the time of your peak performance?
Score Distribution?? Not declared yet, 2 & half hour left
will be declared within two & half hour.
Score Distribution??
This is the last CF round before the Central informatics test here...
I really hope that I can get to Div1 so I can impress everyone I know with a new color wish me luck!!!
:)
UPD:I'm gonna get my new color...sadly it will not be in DIV1 :(
Ahh well I'll try again in the next contest.
Good luck!)
thanks.
:)
you just need 250 points, good luck ;
I think 250 points is kinda a lot....
Less than the difference between Petr and tourist ;)
not saying it's impossible. but u need to be about top 15? gl guys! :)
Well it's not a challenge if it isn't hard...Am I right ?
Good luck.
:)
well said. gl
I want you to know that you're in my friends list, because you're one of the guys I'm competing with :)
Nice score distribution)
Score distribution? only 5 minutes left!
500-1000-1500-1750-2500-3000
problem a submission failing pretest 1 if sync_with_stdio(false) and cin.tie(NULL) is present on c++11. accepted without those lines in c++14
errors in pretest 1 are not counted anyways :)
I know, but I had to re-check my code, remove endlines etc, before i tried this. not that it matters in the long run, but pretest 1 failure on problem A is a shock when you try to solve the next one asap.
I am sorry to say this, but the reason for WA is not due to sync_with_stdio(false) and cin.tie(NULL). but because u did not set value of mx to 0. Try using the custom test next time to find out what's wrong.
Как решить C и D?
С: Посчитаем, сколько людей будут опрошены за цикл (т.е. до момента, когда учитель вернется к ряду 1), обозначим это число cntFull, тогда учитель совершит k / cntFull полных обходов, а после этого задаст еще k % cntFull вопросов. Заведем матрицу NxM, и заполним ее так, будто бы учитель сделал k / cntFull обходов (в первый и последний ряд расставим единички, в средние n-2 двойки, помноженные на k / cntFull), после этого проэмулируем оставшиеся ходы. Выведем максимум матрицы, минимум матрицы, и значение matr[x][y]. Главное — не набажить в реализации, при случаях n=1,n=2. 23953545
D: Напишем динамику dp[i] — ответ на префиксе длины i. Обозначим num(l, r) — число из инпута, являющееся подстрокой [l, r]. Тогда для каждого r > i, если num(l, r) меньше основания системы и не имеет лидирующих нулей мы можем сделать переход dp[r] = min(dp[r], dp[i] * base + num(i + 1, r))
Ответ в dp[s.length]
not say unrated for B :((
It affected about 3-10 users. Do not worry about unrated case.
tnx MAN :)
Great problems, I really enjoyed them. Thanks for contest Kniaz
Made 17 submissions but getting wrong answer of pretest 8 for problem D. Any reason?
Did you check for 64-bit integer overflows? Something like
if (f[i] <= INT64 / n)before anf[i + 1] = f[i] * nupdate.I checked whether num>=0 && num<=1e18; If it would have overflowed it might become negative or >1e18. AM i right?
Not really… If it by accident equals k × 263 + C where k is an integer and C falls into [0, 1018] then you'll probably do incorrect updates.
you can't have a string of consecutive 0s in your dp(example if k is 100000, you can't select '000' or '00'. But you can select '0').
have you taken care of this?
Yes mitsuki I have. Not only zeroes, you cant have "002" i.e. any number with leading zeroes.
Yes I meant all starting with a 0 (except '0' itself).
The result is guaranteed to fit into 64-bit int, so I don't get why you would need to check that?
In some implementations we calculate some value as is described above, and then compare it with another value to do updates. It's perfectly fine if this isn't involved in your implementation :)
Yes, sorry, I didn't realize there are non-greedy solutions :)
Nor did I realize there are greedy solutions… (●—●)
Could be overflow. I got pretest 9 due to overflow
Any idea of pretest 14 in problem C ?
not sure. but did u consider n=2?
In this test min = 0 (my first submission failed on it)
Any idea as to what was pretest 6 in problem D?
Hack cases for problem C?
you troll you...
How to solve B? I feel very emberrased asking this question.
The idea is that the color of light bulbs will be same in positions 0, 4, 8...similarly same in 1, 5, 9, ...and for sequences of 4 * K + 2 and 4 * k + 3. Since there is atleast 1 light bulb working for every color, you can know which sequence corresponds to which color.
Oh no. I am feeling gray right now or even below than that.
Is there any counterexample for greedy for problem D?
Should output 23 (= 1 * 12^1 + 11 * 12^0). (I assumed you meant greedily pick the largest portion < n)
That's exactly what my greedy algorithm outputs. I greedily pick the largest number (from the right obviously) in each step.
Well you assumed right, but my solution gives 23.
Yup there is, WA 100 :(
What is the case?
2 10000000000000000000000000 but I think it is more like a bug in our code than it is the problem w greedy UPD: I just debug my greedy and it AC. so greedy works
That's not a counterexample to greedy but rather to either not handling overflows or 0's correctly. Also, greedy does work.
Loved the problem set. Thanks for the contest. Really scared about clearing the system tests this time though.
Guys, what is a type of problem C today? Is it math or just implementation? I have difficulties with this kind of problems
DFS, BFS, Dijkstra, KMP, GCD, ... all this knowledge means shit when confronted with such kinds of problems :(
I don't even know how to study in order to be able to solve them.
Absolutely agree) I think this type of problems is named as "constructive"
I go for 'destructive", took me an hour to solve...
The correct term is "stupid time waster".
I don't think it's stupid and red guys solved this problem in 10 minutes. We should at least strive to perform like them.
The only problem for me is that I don't know how to train to be able to solve such problems.
It's called "stupid time waster" because: 1) the solution is obvious: you remove the cycles in O(1) then simulate the rest; and 2) there's a lot of corner cases to deal with (this is the part that wastes your time). And nothing better than "stupid" to call a problem that is both obvious and wastes your time.
There is exactly one corner case (n = 1) in my solution. I believe its what can be feasibly called an implementation problem due to the solution being pretty obvious. The time you spend is mostly spent on writing the code, not thinking about the problem.
That's just what "time waster" means to me.
A and B usually are time wasters, but this C is over 9000.
It is interesting for how long this point of view will serve you as a source of motivation :)
I don't need motivation. I need time.
By the way, if someone is interested, it is possible to write the code without any corner cases: 24112753
Exactly one
if()for the whole program.Nice, it took only a week! Now I'm so convinced that this is not a time waster problem!
Sorry, I didn't want to provoke you. I just wanted to share with my finding and it looked like this is a good place.
There's a "Write comment?" button up there ^
If this is not a provocation, you should've used that instead of replying one of my comments. It really seemed like you we're trying to provoke me. But you explained yourself, so okay, no problem. Just use the button in the next time.
I really hate that kind of problems
Cannot agree more. I found these types of problems very irritating.
I made 6 submissions and all failed on pretest 5, maybe I was missing an easy corner case.
It's a combination of math and implementation — you need to get the period idea to make the solution O(nm).
Is solution of O(1) possible ?
Yes it is. It is just some mathematical formula in the end.
C.cpp
Who all math lovers here?
Do we need Big integer in div2 D ? Passed pretest but it may fail due to multiplication overflow.
UPDATE:
FST, got accepted after checking overflow
if (mul2 && mul1 >= LINF / mul2)
{
return LINF;
}
Alexander guarantees that the answer exists and does not exceed 10^18.
So if we do it the right way, we shouldn't need Big Integer
But there can be cases that the minimum answer < 10^18 and the maximum answer > 10^18, and my solution may choose the maximum answer due to multiplication overflow
You don't consider cases where answer is more than 10^18.
In my solution I do multiplication such as curNum * exp, where exp can be big like 9e17, it's easy to overflow and I didn't find a way to avoid it.
I kept a double counterpart to detect overflow....
I wrote a function to check if multiplication/addition of two numbers leads to overflow or not.
So you didn't do greedy? How did you solve it?
didn't find a greedy solution and do O(len^2) dp
Not sure how your solution works. But looking through my code and with constraint such as (2 ≤ n ≤ 10^9), I dont see anywhere I could overflow. I could be wrong though.
In such situations, you can use a long double. It can store up to 1e18 perfectly, and so the answer will be reported correctly with full precision. If it goes above 1e18, you will lose precision but comparisons will still be correct enough. And in this case you don't require precision because it is not the answer anyway.
23960455
No you don't need big int, check my solution: http://codeforces.net/contest/758/submission/23960101
The idea is: you want the minimum amount of digits on the base N, if there's a tie, getting the smallest possible digit on the most significant digit is the smallest answer.
seconds away from submitting D :/
Me too, hope my solution turns out wrong or TLE.
no hacks this time!! :-)
Anyone passed D with a DP solution? I was doing dp(i,j) as the minimum decimal number when consider i-th position the beginning of j-th part. I am pretty sure about this approach but it received WA on pretest 7 however.
I passed with dp solution. You may have a problem with the 0's
I think i dealed with 0's, maybe it was because of overflow...
Well, I got caught in test 100 :v :v So ignore me :v
Any idea what the case is?
I did some calculation with double to check overflow... Maybe I got caught in there for some tricky case.
Did you handle overflows?
I was also doing DP soln and WA on pretest 8. I think my error was due to overflow.
I tried to solve it in the samw way. However, there are some tricky cases. For instance, when the choosen number starts with 0(2 — 0 — 16 is ok, but 2 — 016 isn't). There should be some other similar cases.
Yippiee, my solution is wrong! (Came about 15 seconds short.) But i think getting digits greedy from least to most significant should work?
This time greedy should lead to WA, try testcase
320
222408
My dp solution gives 2329608 but yours will give 22745608 (if i dont misunderstand your greedy solution).
I get the same answer as you. I start from the least significant side and try to find the biggest possible digit: 8 — 240 — 22
UPDATE: Greedy is accepted.
where do you have base power in your dp state? I had dp state as DP(i,j,pw).
PS — I got WA too
beginning of j-th part can be used to uniquely identify the base power... I think your states are redundant
can you explain with an example?
You could use a dp(pos) it tells you the minimun length of this number in the base,so after that you make a dp reconstruction as the statement tell you it fits in a long long you would make the reconstruction safely without overflow.
Pretest 7 might be the case that the result is 10^18
Yes.
23960455
Can smb explain the idea behind F?
I'm sure you can solve it with n = 1 or n = 2. So, let's assume n > = 3. Now, let r = x / y be the ratio of the progression( gcd(x, y) = 1) . WLOG, r > 1. Then, xn - 1 < = r because yn - 1 divides to a0. So, you can brute force x and y up to 3200( sqrt(10^ 7)). After that, you find bounds for a0 and you just need to add the difference of those bounds plus 1 to the answer.
Can someone explain how to do C?
The rows
(1,2,3,...,n,n-1,n-2,...2)form a sort of cycle that is repeated. The total amount of questions in the cycle ism*(2n-2).And after that you're left with
k%(m(2n-2))questions which is less thanm(2n-2) < 100*200 < 1e5which you can fill out manually.Since
2*1-2=0n = 1 is a special case (i dont exactly know if this is avoidable).Me also treated n = 1 as a special case. There is nothing like n+1 or n-1 here. Maybe modulus arithmetic can do some trick though.
There is lots of way to fail. Consider some variable.
MD = 2n-2
P = k/m
Z = P/MD
R = (P%MD)*m+k%m
Can you explain what variable holding which information? Do you see the pattern?
1) Calculate how many times the classroom (matrix) will be covered. Let it take 'cover' number of times. This can be calculated as: For 1st round: n*m For 2nd round: (n-1)*m (Won't ask the last row in second round) For 3rd round: (n-1)*m . For 'cover'th round : (n-1)*m
Summing them up: n*m*cover — m*cover +m (Eq-1) Equate this to k and solve for 'cover'. cover = (k-m)/(n*m-m) Check whether k<m. If it is then cover = 0.
2) Now the 'left' can be calculate easily by subtracting k with (Eq-1).
3) If cover=0, then left = k, and we can simulate by giving 'left' number of questions to students in the way described in the question.
4) Now, a)Initialize the top row by (cover/2)+1 [1st round = 1 time visited 2nd round = 2 3rd = 2 and so on.] b)Initialize the last row by (cover+1/2) [1st round = 1 time visited 2nd round = 1 3rd = 2 and so on.] c)Initialize others by(except first and last row) by cover
5) If cover%2==0, start from top and stimulate the process otherwise from last row, till left=0
6) Calculate max,min and a[x][y] from the matrix.
Consider n=1 separately, for which cover = k/m and left = k%m. Initialize it with cover and then increment the row until left=0
Was D solvable using greedy: http://ideone.com/lgOWrh And, the last 30 seconds the sumbmit button wasn't working. Is it only for me or somebody else got the same problem?
Does anyone have some good test cases for C? I got WA on 10. :(
same
2 3 6 1 1
mine was failing for this..
answer — 1 1 1
This is it, thanks!
2 5 21 1 1
I passed pretest 10 after checking this test case
What if my B solution is right !! It token me most contest time searching for the wrong after hacking . I hope that to be unrated contest or for who face the same problem only .
What if my B solution is right ! It token me most contest time searching for the wrong after hacking. I hope that to be unrated contest or for who faced the same problem only .
My O(n2) solution got TLE in Hack. !
I think the case was something like these —
Where they don't contain G,R,B,Y at least once
Also I solved D just 1 minute after the contest.. And my friend solutions are almost same to me.. But I didn't able to submit
The validator in this problem was incomplete. There were some hacks that uses invalid inputs but were processed. All of them will be rolled back. Sorry for it.
Hi guys, i really tried during the contest to cover all the cases on problem C, but i didn't do it. After the contest i have seen i didin't even have to. :) Anyway, i wish i could figure out what kind of situation have i missed. Can you, guys, please help me ?:D (code : https://csacademy.com/code/0ADQMygT) Thank you in advance! Btw great contest overall! Keep up the good work! :D
This contest should be unrated only for those who suffered in problem B. :(
Please don't make it unrated :(
RATED.
still 'Pending system testing'!!! :(
They need to decide how they will rejudge problem B.. That takes time.
Thanks Kniaz for writing problems. I like tasks A, B, E, F very much, D is OK, but problem C is terrible. I hate this type. A lot of commands 'if', 'else'. But it's only my liking. So excluding problem C contest was pretty good.
WTF is this!! This guy's all solutions got hacked!
http://codeforces.net/submissions/Fuck_Anas_Abbas
lol :D :D
Maybe someone is cheating and has two accounts: at one he sends wrong solutions, and from another he hacks...
But how can he make sure they will be in the same room?
OK, it's small probability. But if he has more than 50 accounts? Mabye there is a person who starts in contests to have a high rating...
as the one who hacked him:
i laughed when i opened his code for the first time
but now i think i've made an enemy for life
I am pretty sure that when you will see those hacking attempt you will find "Anas Abbas has been fucked"
lol :P :P
Open his source code, when suddenly...
cin>>fuck"Anas Abbas has been Fucked"
This made me laugh.
his code is funny
this guy must love me so much :/
This guy should write a book on "HOW TO PASS THE PRETESTS AND HACKS LIKE A SIR"
I like the last sample test for problem div2C.
Kniaz why are your Pretests this weak?!!!!!
Come on! The pretests for B and C were awsome and i think few people passed the pretests and failed the sys test !
I think that a lot of people failed system test on C...
Is this how to solve F?
First, insert in a fenwick tree values of antilog( log(x / n-1) )
Then, simply use these values to calculate the number of GP for a certain b(b has values from 2 to r)
The GP will be of the form xa^n-1,xa^n-2b,....,xb^n-1.
Finally, multiply by 2, and handle n=1 separately.
b can be less than 2 (rational actualy)
Can't we handle b>a similar to the above process?
oh, sorry, i thought b is step in GP
Is my approach right? I think it is.
Please fix problem B validator/solution as there are alot of participants who solved the problem and their solution should pass the time limit constraints my solution was : Submission for Problem B
the test case that gives time limit for alot of participants is test case 17 : R!!Y!!B!!G! which is invalid ! as stated in the input section .
Same problem here
Also many one didn't get time to submit another problem solution which they were capable of :'(
I don't think that case is invalid:
Consider the string RGBYRGBYRGB
Then the bulbs at 2nd, 3rd, 5th, 6th, 8th, 9th, 11th positions become dead The new string is
R!!Y!!B!!G!
"The string s can not contain other symbols except those five which were described.
It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'.
It is guaranteed that the string s is correct garland with some blown light bulbs"
None of these conditions fail.
153 Lines for problem B :/ Much time wasted there
How much time for upsolving?
How many tests for D are there? Failed test 100 :(
edit: there are 102 :D
Did you understand test 100? o.O It didn't made sense to me.
Yes, my problem was an overflow in the base variable I used to convert to int.
What is solution for "R!!Y!!B!!G!" test 17 for B?
RGBYRGBYRGB is the sequence, output is — 2 2 1 2 Edit: Forgot the actual numbers, only put the sequence.
The resulting sequence will be — RGBYRGBYRGB so answer will be 2 2 1 2
2 2 1 2
Waiting for rating change
ok, can someone explain test 100 to me for problem D? 2 10000000000000000000000000
Answer: 33554432
But how? As I see it, there is only one possible way to write this number in base 2 :O o.O
Plz someone explain
Exactly, the only way is to consider that is as 2^25 in base 2, which is 33554432 in decimal. I think you're confused about what you had to print as the answer.
You had to print the decimal representation (smallest) of the given number, not the number of possible decimal representations.
Why do we so many solution overflow on that case? I dont see why they would...
I assume they must have tried picking up consecutive zeroes, kept increasing the multiplier by 10 while going to the left causing it to overflow.
The many zeroes would mean that the actual number would remain zero, so a check to see if that has overflowed would be futile.
It is possible to have a solution without checking overflows.. Like I didn't check overflow but got AC — 23971526
Yes, thank you. I was not confused about what I had to print as my answer. It was just a stupid typecasting error.... And after seeing the test, I thought without counting the number of zeroes, that this number is greater than 10^18. I came back as soon as I realized my stupidity to delete the comment , but you had already replied :v Thanks anyway.
No problem at all.
I failed with the same case, while calculating number backward from last digit to get maximum number less than n, should break before getting overflow, here it overflows after 18 digits of 0.
Wrong answer on test case 84 — wrong answer 2nd numbers differ — expected: '14084507042253521', found: '14084507042253522' why???????
because 14084507042253521 != 14084507042253522 -_-
Is there a way to see submissions made using a particular language for a problem? I want to see Python submissions for Problem C.
You can use the Status Filter :)
Thanks!
What was so hard about E? Don't you just have to calculate the shortage at each edge, and then try to fulfill the shortage from the deepest node you can reach?
WhyamIinthewinnerlist lmao Nice contest thanks :D
Does anyone know why my code for D gets different veredicts if I switch between C++ and C++14?
GNU C++14: Wrong answer on test 28
GNU C++: Accepted
Edit: it might be because signed integer overflow causes undefined behaviour.
Same code. Same compilator. Differnet verdicts.
http://codeforces.net/contest/753/submission/23942304 http://codeforces.net/contest/753/submission/23942242
One question. HOW?:)
Could somebody explain the verdict seen here 23954999.
My code outputs the correct result locally, yet the judge gives some strange error which does not seem to be my fault.
edit: Perhaps MikeMirzayanov could shed some light on this problem?
LOOL, really
This maybe kind-of bug in judge :P lol
KAN and MikeMirzayanov I think you should look into this. Maybe the Disk failure or something :/
It was rejudged, I'll recalculate ratings soon.
When will be rating updated?
In question B the output of the following testcase !BGY! should be 2 0 0 0 ?
"It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'"
so this input is incorrect
Please can anybody help me with D .I am getting Wa on pretest 8 because of oveflow.. Here is my code
Try using unsigned long long. I got AC without handling any king of overflow and using unsigned long long — 23971526
Thanx man just changed that and got ac... i wish i had done this in the contest :)
I finished this solution just before 30second of the end of the contest but didn't managed to submit it >:(
My Solution B got Hacked :( :( And now rating change (-48) :'(
Stupid time waster problems like C should worth 5000 score, for the patience you must have to solve them.
Not really that much stupid. Everything I needed is to see the number of student will be at most 100*100. Though lost too much time before seeing the value of n and m.
wish some points!
When will the ratings will be updated ??? Wating and wating .......
Waiting for the rating update -.-'
Will it be unrated?????
No. It's going to be rated
*** *****?
rating will update soon?
Tired of refreshing !
0 Rating change thank you .:)
Why is wolf29 in Div1 in your post? He was blue before the contest.
Div1 means all contestants, i think
That's POWER of writer :-)
Why did the rating changes get rollbacked? :/
Why the heck did u take the ratings back?
Why are the ratings reverted back to the previous one??
Again changed
http://codeforces.net/blog/entry/49837?#comment-338510
I'm new here, so tell pardon me if i said something stupid. When the contest was over, I had 3 problems solved. I came back some time later and found out it shows 2 problems solved and one wrong solution. Is there a way to evaluate a persons code even after the contest is over. If so, can you tell me what do they really do?
pardon my English :(
It is about the main tests There are two kind of tests, pretests and main tests the main tests are used in system testing and sometimes it happens that you pass the pretests but fail the main tests
Both my submissions http://codeforces.net/contest/758/submission/23964519 http://codeforces.net/contest/758/submission/23963310 are correct when I test them in "Custom Invocation"
"Input" RYBGRYBGR
Output 0 0 0 0
But in pretest I got Verdict — "Wrong answer on pretest 1" and Output 0 1 1 0
Why I get different result in Custom Invocation and System test? I think it is not my fault
Finally BLUE again :D
I'll try to enjoy the feeling before losing it the next contest :3
Is the Venture Cup final on Sunday rated for Div2 ?