spookywooky's blog

By spookywooky, 4 years ago, In English

I allways wanted to write an editorial, it seems like that very simple contest is my chance to do so.

1351A - A+B (Trial Problem) This is a most trivial problem, we just need to literaly output what is written in the statement, cout<<a+b<<endl; 79277814

1351B - Square? In this problem we need to observe that we can build a square from the two given rectangles if, and only if the sum of the two smaller sides equals the longer side of one of the rects, and both longer sides are equal.

How to implement this? Well, since there are four cases which sides could be the longer and the shorter ones, we can implement all four cases. Or simpler, change the side lengths of the rectangles if they are not in order. We end up with something like this

bool ans=min(a,b)+min(c,d)==max(a,b) && max(a,b)==max(c,d);

79287825

1351C - Skier First we need to understand that a "segment" in this problem is the way between two points. And the given path denotes the step from a current position to a next one, which uses one segment. We need to observe that it does not make a difference in which direction we use a segment.

For implementation it seems natural to somehow mark the used segments, and on every step check if we use a previously used segment, or a new one. We allways step from a previous position to a current position, and the current position is the previous position of the next step.

Marking a segment works fine by putting the allready seen segments into a map or set. Since a segment can be defined in two ways (the order of the two points) we can put both definitions into the set. Or while querying the set query for both. 79286682

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

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

THANK YOU!

»
4 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I hope this approach for A help others! 79440849

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

    Nice and efficient approach....
    I was afraid that this problem can only be solved by DP :)

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

    I think, this is solution can help someone too 79451368

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

I think it's better 79381459 :D

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

Challenge: solve problem A without using any of +-*/ in your code.