Untitled's blog

Codeforces Round #178 (Div. 2)
By Untitled, 12 years ago, In English

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! :{

  • Vote: I like it
  • +234
  • Vote: I do not like it

Comments Comments (67)
| Write comment?
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Good luck all. Author, thanks for contest!

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks all.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Codeforces comes again!How happy am I!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish everyone good luck and high ratings! :D

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Who is Shaass?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      emmm... No , he's not. he's me and my friends hero

      ps. "Shaazzz" is't a guy... is it??

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like 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!

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          shaass is short form of shasgol! :D i think.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 3   Vote: I like it -27 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        it's a big hero, trust me ;)

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It's somehow like "fool" in Persian, but in a funny way.

    → Reply
»
12 years ago, # |
  Vote: I like it -94 Vote: I do not like it

I know that people who are under 1900 rating can not prepare contest.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +33 Vote: I do not like it

    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!

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i love short post (as well as short problem statement)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -56 Vote: I do not like it

Why do not deleting comments !

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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??? 500-1000-1500-2000-2500 ?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the meaning of challenge-other when hack others

→ Reply
»
12 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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?**".

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the answer on test: 2 2 1 1 UR ? I think answer is -1.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You can do a greedy brute-force. 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

    → Reply
»
12 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Good contest, thank you. Problems are interesting, I like them.

But it is a bit hard for div2.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Shaass... Looks like a kind of a jewish name

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It's not a real name in Farsi, it is sort of nickname for fool and stupid person :)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in third test on C answer is 6720?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because there are 6720 ways.. Try to understand smaller tests.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    -

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the solution to C?

I look forward to reading the editorial about D and E.

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Once again an unrated coder winning.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is logic for Problem-C ..??

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 7   Vote: I like it +20 Vote: I do not like it

    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^(n-1) (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)

    → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think it would be better if someone from div.2 (or <=1750) tested it also.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for quick change of rating. :-)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

У кого-то было ВА8 по Е, я без понятия..

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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???

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A bug?

In my rating graph, the 2 points before today's contest seems to be swapped!

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

for problem D,what does the following sentence mean? "The robot stops painting the first moment the floor is checkered. "

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem D was harder than usual, at least for a div 2 contest.

→ Reply
»
12 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Finally at the end of the contest I must say that you are not "Untitled" but titled to organise a div 1 contest also :)

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Great contest.Good luck

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is the editorial out?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Первая идея с сортировкой на B не прошла, как тока собирался сдать новое решение, сеть с интернетом пропали. P.S. новое решение проходит.

→ Reply
»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

The problem set seems to be A D D E E... But I enjoyed it!

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Another time, an unrated user won the contest!

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice contest Thanks ;)

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice contest :) waiting for the editorial eagerly...

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You don't want to publish tutorial?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think this probblem can use One-zero backpack. http://mirror.codeforces.com/contest/294/submission/3485742

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

when we can meet shaass again?!?

→ Reply