havaliza's blog

By havaliza, 5 years ago, In English,

294A - Shaass and Oskols

Although Oskol is not really name of a specie of birds, In Iran it's known as a kind of bird which is very forgetful and can't even remember his way back to home when he flies away! It's commonly used instead of the word "stupid" among the kids! :D

In this problem you just have to now how many birds are there on each wire after each shot. A good trick for the first and the last wire would be to define wires 0 and n + 1. In this way the birds that fly away sit on these wires and you don't need to worry about accessing some element outside the range of your array.

Here is a neat implementation in C++ from contestant rpslive: 3484601

294B - Shaass and Bookshelf

As said in the statement, the thickness of each book is either 1 or 2. Think about when we want to arrange v1 books of thickness 1 and v2 books of thickness 2 vertically and arrange all other n - v1 - v2 books horizontally above them to achieve a configuration with total thickness of vertical books equal to v1 + 2v2. Is it possible to find such arrangement? Because the total thickness of vertical books is fixed it's good to calculate the minimum possible total width of horizontal books. As the width of a book doesn't matter in vertical arrangement it's good to use the books with shorter width horizontally and the ones with longer width vertically. So pick out v1 books with longest width among books of thickness 1 and do the same with books of thickness 2. The sum of width of n - v1 - v2 remaining books should be at most v1 + 2v2.

The solution would be to try the things we explained above for all possible values of v1 and v2. And print the best answer. :)

There exists other ways to solve this problem mostly using dynamic programming but this was the intended solution of the problem.

Here is a nice implementation in C++ from contestant Bayram: 3485189 (You should also know that 'bir' means 'one' in Turkish and 'iki' means two!)

294C - Shaass and Lights

I just want to solve the third sample of this problem for you and you can figure out the rest by yourself. :)

The third sample is ...#...#... where # is a switched on lamp and . is a switched off lamp. As you can see we have three different types of lights. The first three lights (Type A), the 5th to 8th lights (Type B) and the last three lights (Type C). We have to switch on the lights three times for each type of lights. Aside from the order of moves for each type there are possible permutations of the string AAABBBCCC which tells us how to combine the steps of different types. Switching on the lights is done uniquely for types 1 and 3. But for type 2 each time we have to possible options until we're left with one off light. So there are 23 - 1 ways to do this. So the answer would be 1680*1*4*1 = 6720.

The general solution would be to find all groups off consecutive switched off lamps and calculate the number of ways to combine all these groups. Then for each group you should calculate in how many ways it can be solved.

The implementation needs some standard combinatorial computations which you can see here: 3485187

294D - Shaass and Painter Robot

TODO

294E - Shaass the Great

TODO

I promise the editorial will be completed come soon soon soon! :)

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

E can be solved by selecting an edge and move it to the right place of the split trees. The right place can be found by calculating sums of all nodes in O(N) time, then select nodes in split trees that have the minimum sum to other nodes.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you know how to solve problem D ? Thank you very much .

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      There is a conclusion that as long as all the grids on edge have been visited, all the grids were visited. Although I don't know how to prove it.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you .But the task is to paint the floor until there is no two side-adjacent tiles have the same color .

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        But the starting point may not be on edge...Is that really right?

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

          In this question it is guaranteed that it's on one of the edges.

          About the proof maybe this helps : Suppose A is the set of all of tiles on the edges which must be colored in the final coloring(which is uniquely determined based on the tile robot is standing on in the beginning) and suppose all of tiles in A is colored right now and no other tile which is on an edge is colored.

          now for each tile (x, y) inside A(but the tile which robot stops on), we know that the robot once entered it from one of the diagonals and exited from the other one. which means tiles in both of these diagonals are colored.

          Now take any diagonal which the tiles on it must be colored in the final coloring. We call such diagonals good diagonal. Since each good diagonal has two tiles on it which are on the edge, there exist at least one tile that isn't the one that robot stops on. So for each good diagonal we know that the tiles on it are colored. which means that all of the good diagonals are colored.

          And of course if any other tile in any other diagonals be colored then one of that diagonal's ends are colored as well which contradicts the fact that only tiles insides A got colored.

          This means that if we reach such state the robot must stop and since the final state is counted such state, it's enough to check when we'll reach such state and if we don't print -1.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That’s right . I got it . Thank you very much .

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can you please complete the rest of the tutorial before next codeforces round that is 179.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am really looking forward to seeing the solution of Problem 294D and 294E. I hope havaliza or somebody can complete the rest of the editorial. Thank you so much!

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

please , can you make editorial for problem 'D'

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is an explanation of the solution with somehow good details.

»
4 years ago, # |
  Vote: I like it +48 Vote: I do not like it

This editorial is at least 3rd, that I've seen in last couple days, with TODOs. Is it so hard to complete it within 1 year?

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

He started writing editorial 21 months ago. A very good editorial is waiting for us!

"I promise the editorial will be completed come soon soon soon! :)"

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem Shaass :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the details how we get 9!/(3!3!3!) possible permutation on problem C editorial?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you figured it out now? I want to ask the same

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

are you gonna finish the editorial or not.....havaliza

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Promise Broken! :'(