Hi all! :)
I (Untitled) invite you to participate in Codeforces Round #178 (Div. 2) which will be held today. I want to thank Gerald Delinur MikeMirzayanov for their help in preparation of this event. I also want to thank havaliza who tested the round and made the graphics for the problems.
The hero of today's contest is Shaass. Hope you enjoy helping him! :D
Good luck and have fun ;)
UPD. Editorial is partially out and will be completed soon! :{
Good luck all. Author, thanks for contest!
Thanks all.
Codeforces comes again!How happy am I!
Wish everyone good luck and high ratings! :D
Who is Shaass?
He's one the most popular heroes in Iran National Olympiad. I guess he's Shaazzz's brother, who is one the most popular and powerful heroes of Iran too :D.
emmm... No , he's not. he's me and my friends hero
ps. "Shaazzz" is't a guy... is it??
If you meant "fool" of "Shaass", yes it is. "fool is one the funniest and useful heroes in Mashhad. If you didn't, sorry. It was just a guess :D I know Shaazzz is not a person but a group or country or planet or many things else, but this name commonly use in <Shaazzz.blogfa.com> problems. HF & GL!
shaass is short form of shasgol! :D i think.
hey at all shaass is not a good word & we all know what does it mean. I can't understand why he choosed this,there's many better words than it.
it's a big hero, trust me ;)
It's somehow like "fool" in Persian, but in a funny way.
I know that people who are under 1900 rating can not prepare contest.
the quality of the contest cannot depend on the rating of the designer however if you remind MR HolkinPV he producted many constests that in that time his rate was under 1900!
i love short post (as well as short problem statement)
Why do not deleting comments !
Thank you ! Our teacher , havaliza didn't came school today, because this contest and we came back home soon.So i have too much energy for this contest!!! :D And one question : what are the scores??? 5001000150020002500 ?
what is the meaning of challengeother when hack others
I think in the contest time, the message/talks option should be disabled. People like me who cannot solve more than (2 or 3) problems in a contest, get message "**How to solve B?**".
What is the answer on test: 2 2 1 1 UR ? I think answer is 1.
I've been strugling with problem B, i made DP solution
based on easy thing: DP[thickness] = left
It is, DP[x] = y stands for: We have thickness x and we have to put y on top of our construction.
You can see my solution coded here: 3488673
Then find smallest x for which x>=DP[x]. But this gave me WA on #4 pretest.
Please explain right solution :)
First fix, the numbers of books with thickness 1 and 2. Then you can find the minimum width of the books at the top greedily.
I also used a DP solution, but since the constraints were so small, I used dp[N][MAX_WIDTH][MAX_WIDTH] array and did a knapsack on it for each value from i = 1 to (MAX_WIDTH — 1). MAX_WIDTH is the sum of width of all the books. If any of the values i were sufficient to satisfy all the constraints I considered that the minimum thickness solution. If not, I needed MAX_WIDTH. Could have used binary search to determine i as well if the constraints were a bit higher but didn't need to in this particular case. Here is my code. 3486021
You can do a greedy bruteforce. Divide them into 2 arrays(one for thickness 1 and the other for thickness 2). Sort the arrays by width(biggest first) and than for every number of elements of array1 check every number of elements of array2(checking all combinations). And since they are sorted by width, it works.
See my solution: 3486814
Good contest, thank you. Problems are interesting, I like them.
But it is a bit hard for div2.
Shaass... Looks like a kind of a jewish name
It's not a real name in Farsi, it is sort of nickname for fool and stupid person :)
Why in third test on C answer is 6720?
Because there are 6720 ways.. Try to understand smaller tests.
1 2 3 4 5 6 7 8 9 10 11
0 0 0 1 0 0 0 1 0 0 0
answer=C(9,3) x C(6,3) x C(3,3) x (2^2)
maybe this helps you

What's the solution to C?
I look forward to reading the editorial about D and E.
Once again an unrated coder winning.
What is logic for ProblemC ..??
the idea is the following
lets take an example (* denotes lighted bulb)
1 2 3 * 4 5 6 7 * 8 9 10
you can divide this into sub problems. The idea here is to find the number of ways to switch on bulbs on both side of a * and merge the result. One more thing, for any sub problem like * 1 2 .. n *, the answer will be 2^(n1) (i leave that to you).
Now, traversing the *s
1 2 3 * 4 5 6 7 * 8 9 10
for the first * , there are 3 bulbs And when treated independently, there is only one way to switch them all on. But for 4 5 6 7, the number of ways to switch them on when treated alone is 2^3 = 8. How do we merge this result? Notice that any solution for the sub problem {1 2 3 * 4 5 6 7 *} will be composed of a possible solution of {1 2 3} and a possible solution of {4 5 6 7}. To put it simply, if a solution is (3,2,1) and another (4,5,6,7), the final solution will be a tuple made from these two solutions with their ordering preserved (for two tuples of size n and m, there are C(n+m, n) final solutions). The ans = 1*2^3*C(4+3,3)
for the second '*'
we have the number of solution for the previous 7 bulbs, and there is only 1 way to switch on {8 9 10}. Thus
ans = ans*1*C(7+3, 3)
What is the function C doing?
combination(n, k)
That ordering preserved type of combinations is called the multinomial coefficient. More can be read from https://mathworld.wolfram.com/MultinomialCoefficient.html
This is similar to stars and bars problem which uses multinomial coefficient https://mathworld.wolfram.com/Multichoose.html
I think it would be better if someone from div.2 (or <=1750) tested it also.
Why ..?
So that author made problems simpler or chose other simpler problems.
Thanks for quick change of rating. :)
У когото было ВА8 по Е, я без понятия..
http://www.codeforces.com/contest/294/submission/3482847
I tried to hack this code for input
1 10 1 1 5
I think this code got RTE but hacking attempt was unsuccessful! why why why???
C++ is magic language. You should never try to hack C++ codes.
i also tried for a code to be RTE, and i was unsuccessful.
the things i learned is, from next time i won't try to hack any other code for RTE. :P
Data declared in the data segment (out of a function in C/C++) is pagealigned and initialized to 0. There is an offset before and after the array that is safe to work. The offset depends on the size of the array. It is a bad programming practice but most of the time works. See my B's solution: 3489441 I intentionally index 1 several times.
You should really read these two thread:
http://stackoverflow.com/questions/3473675/negativearrayindexesinc
http://stackoverflow.com/questions/671703/arrayindexoutofboundinc
I guess, GNU C++ compiler isn't so sensitive to RTE
A bug?
In my rating graph, the 2 points before today's contest seems to be swapped!
for problem D,what does the following sentence mean? "The robot stops painting the first moment the floor is checkered. "
"Checkered" means "painted like a checkerboard".
Problem D was harder than usual, at least for a div 2 contest.
Finally at the end of the contest I must say that you are not "Untitled" but titled to organise a div 1 contest also :)
Great contest.Good luck
Is the editorial out?
Первая идея с сортировкой на B не прошла, как тока собирался сдать новое решение, сеть с интернетом пропали. P.S. новое решение проходит.
The problem set seems to be A D D E E... But I enjoyed it!
Another time, an unrated user won the contest!
Nice contest Thanks ;)
Nice contest :) waiting for the editorial eagerly...
You don't want to publish tutorial?
Hello Everyone, Can anyone explain me the solution of the problem B of this contest. I am completely confused after reading some of the comments here as they suggest to check all the combination of the numbers to get the minimum value, where from the condition given in the problem appears to be very straightforward to sort with widths and collect first few as horizontal and the rest of others as vertical, but there code show that they try to check all the combination but actually they does not check all of the combination actually and got correct answer. As the description of the problem and the comment does not clear here to me, I beg your help to understand me the problem with the code.
Thank you!
This goes said that it check all the combination but actually it does not :(
http://www.codeforces.com/contest/294/submission/3486814
where this is my solution
http://www.codeforces.com/contest/294/submission/3487146
That solution does the following: initially tries to put vertically some books with thickness equal to 1 AND some books with total thickness equal to 2, then tries to put horizontally all the books with thickness equal to 2 and some books with thickness equal to 1, then, finally, tries to put horizontally all the books with thickness equal to 1 and some books with thickness equal to 2.
An alternative solution with dynamic programming: Dp[i][j][k] — 1 / 0 if you can obtain from the first i books a total thickness of the vertical books equal to j and a total widthness of the horizontal books equal to k. When you want to add a new book, you can put it vertically or horizontally. In the end, you have to find the smallest i with at least one value equal to 1 from Dp[N][i][j], j <= i.
I think this probblem can use Onezero backpack. http://codeforces.com/contest/294/submission/3485742
when we can meet shaass again?!?
Outdoors for example.