seland's blog

Codeforces Round #303 (Div.2)
By seland, 10 years ago, translation, In English

Hello everyone!

I am glad to announce that soon will Codeforces Round #303 for Div.2 paricipants, the author of which I am. Traditionally Div.1 participants can take part out of the competition.

This is my first round, and I hope that it will be interesting.

Round wouldn't take place without the help of the Codeforces team! Great thanks to Zlobober for helping me preparing the round and Delinur for translation. Special thanks to everyone who puts his effort into the creation and maintenance of Codeforces and Polygon systems.

Score distribution will be announce later.

Good luck and inspiration!

UPD Score distribution will be — 500-1000-1750-1750-2500.

UPD Congratulations for winners in Div.2:

  1. Bell-sama
  2. anko
  3. BobDylan
  4. Gusheng
  5. Diguised
  6. imyyimdog

And in Div.1:

  1. ngfam_kongu
  2. Laakeri
  3. Um_nik
  4. KrK

UPD Link for editorial.

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

Comments Comments (131)
| Write comment?
»
10 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Hope the English version won't be from Google translator!!

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

    Come on people,why downvote? I made some prediction here and as you can see the 1st problem really had some sign of google translation: "Little Susie, thanks to her older brother, likes to play with cars." Didn't my prediction work?

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

      People just like to downvote comparatively low rated programmers comments whatever they write.Racist everywhere.

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

World Final for div 2 :)

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

Maybe not so many genius unrated contestants, because most of them are in relaxation mode for tomorrow Div. 1 World Final ;)

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

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

    Many strong coders won't take part due to world finals . All of the strong coders are in div1 . That's why there are many div1 contests consecutively lined up after the WF ends.

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

When tourist said his team did not feel any pressure for the world finals i thought OK.. But then querty787788 went ahead and registered for this contest as if he has nothing to do tomorrow. Let's see if he actually participates.

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

I wonder why all the contest at the same time of the day ! It's not suitable and not reasonable at all .. can anyone explain this ?

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

Score distribution will be announce later :) When??? JUST 10 min. befor contest and no announce :/

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

    now 1 min :D

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

    Well, the author thought that good luck and inspiration are enough :)

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

Just 5100 participants?? too few! :D

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

who was translating statements??? i hate him with passion.

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

    Telling what exactly you think is wrong in a translation is a more constructive way rather than just saying you hate someone.

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

      I thought the translations were totally fine with a few minor mistakes that didn't really matter in understanding the problems.

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

      ye sorry for nonconstructive criticism, but some of the problem's statements weren't translated fully, compared to russian statement (example: E's english statement didn't contain that graph is connecte initially, while russian statement did)

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

The worst Contest EVER!

A,B,C,D,E were all obvious! -_-

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

    E was so obvious that I thought my logic has got to be wrong.

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

    Guy registered 3 hours ago judges the problemset. You even weren't brave enough to participate from your real account, lol =)

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

In problem E, using std::set(to implement Prims) gives TLE ?

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

In E, how to prove that shortest path tree we get using dijkstra is indeed the shortest path tree with least weight ?

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

    This solution may be hacked by following test case:

    3 3 1 2 8 1 3 6 2 3 2 1

    Simply doing djikstra — it will output 14; correct answer is 8.

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

      Even using dijkstra, we get 8. Ofcourse, the modification if ( dist[X] <= dist[current]+weight of edge )then parent[X]=current is to be made.

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

    Is that always true anyway? At least my implementation of Dijkstra does not have that property, and I spent forever trying to figure out how to modify it to get that property.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it 
    its wrong, so you cannot prove it :D
UPD: I wasn't fast enough
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      so, what's the correct solution for E?

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

        Use Dijkstra and modify (d[v] == d[u] + w);

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it 
        i used this method.
consider the spanning-tree (shortest path ST) with minimum weights.
delete a leaf from it then it can be prove that the remaining spanning tree is still with minimum weight.
so remove all nodes then add them one by one, in which you add you shout set it parent the node with minimum edge weight.
        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    it isnt because i used dijkstra and i got WA. i think you should modify dijkstra so when (d[v] == d[u] + w) happens, you change d[v] to d[u]+w if the trees wieght decreases.

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

    Let d[x] denote the minimum distance from u to x. Let's construct a tree in G using this approach: 1. Let u be the root. 2. For all other vertex p, we can choose as a parent any node q such that d[p]=d[q]+w[q][p]. The most natural idea is to select the q with minimum w[q][p].

    Since for each vertex we are selecting the edge with minimum weight, the total sum of weights will be minimum. It just remains to prove that for two different vertices, we can't choose the same edge as a link to the parent node (this is a consequence of positive weights)

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

Question similar to E was asked in ICPC regionals this year. Here is the link.

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

    Actually solution algo was directly google-able too :P one can get ready-made algo for E in 2 clicks :/

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

Problem C was really hard for third problem(C).

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

    It's obvious I think :) But D is easier than C.

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

      i think C is the obvious one cuz its a simple DP.

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

        i think you can solve it by using greedy approach also.

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

          i would love to hear how.

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

            Starting from left, If you can fell a tree left, make it go left else if you can fell it on right make it go right.

            Why this works ? If you are falling left then it is easy to see that you are not spoiling the chance of the next tree. The option for next tree is open.

            If you are falling the tree to right, may be there is a possibility that the right tree can't fall left. Only thing is worst case scenario you have to select only one of this tree.

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

        It was greedy. All problems were greedy :)

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

      D easier than A

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

    Hard ?? why ?? it was a simple implementation .

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

During coding phase,Earthquake at NEPAL-INDIA border ruined everything!! :( :(

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

    I am From Nepal (Original) . Please Don't Make a Joke about Earthquake

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

    I am from north India. There was no such earthquake.

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

unexpectedly easy problem set. appears as if we are participating in a DIV 3 contest

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

    if the difficulty level was "standard" ANY of problems A,B,C,D could be Div2. A or at most Div2. B.Because no specific algos were needed,and problem C had some tricky coroners and wasn't actually difficult

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

Thanks for nice contest for Div.2. There were interesting problems. Maybe pretests could be a bit weaker.

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

Why am I still unrated after this contest? (It is my first btw)

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

What was the 7th pretest for C :(..Kept getting WA

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

    It was DP. You should initialize 0th tree at -infinity(-10^14) and n+1th tree at infinity.

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

      Well, that's obvious. But what about other trees, could you please explain to me? I couldn't code a working solution.

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

        Either a tree doesn't fall at all, or falls on left or right. So, 3 arrays to hold these results.

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

          Actually when the tree falls on the left or doesn't fall generates the same sub-problem!

          So you can use only 2 arrays :)

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

      I did C in a greedy manner: keep 3 arrays(one for trees position, one for trees height and one for where will the rightmost part of the i-th tree be). I initialised the rightmost part of the first element as the position of the first tree and the (n+1)-th with INFINITY. Then for each tree starting from the second to the last i check first if i can make it fell to left(using the rightmost array), if i cant i check if it can fell to right and it is still impossible i move to the next tree without increasing the amount of trees that can be cut.

      PS sorry for bad formating.

      Here is my source code: CODE

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

      Actually it could be solved in a greedy way without any extra space.

      The first tree is toppled to the left and the last to the right.

      Keep a variable "lastUsed" initially equal to the position of the first tree.

      For trees [2, n-1] try to topple it to the left. If not possible try toppling it to the right and update to x[i] + h[i]. If it couldn't be toppled or it was toppled to the left "lastUsed" gets updated to x[i].

      My code

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

Hmmmm.... either I drunk too little coffee or I have to participate in Div3 contests....

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

It was a GREEDY contest!! :D

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

A car is good if it turned over in no collision --> RIP English

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

This was easier than Codechef Lunch time contest, which is supposedly designed for school students.

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

    Have you actually participated in those, because I certainly feel that overall level of lunchtimes is at par with Div2 contests(old ones when I used to participate :)) and most of the times even difficult than that.

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

      Yes, I have and I believe that last two problems of Div2 contests are harder than last 2 problems of lunchtime. The level of first three problems are more or less the same. But today first 4 problems were very easy and 5th was direct implementation.

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

        I don't think you can judge the difficulty of problems which you can't solve in contest time. Just because the solution uses a familiar concept or uses less code doesn't necessarily mean it's simple. Have you solved Div2 E or the last problem from Lunch Time contest?

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

    IOI is also for school students. Do you think it's easy?

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

Codeforces favors C++ over Java too much. I cant make E accepted with Java, got TE all of the time. The algorithm I implemented is exactly same with accepted C++ version.

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

Only 3 "Failed System Test" solutions in my room. wow... XD

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

Can anybody explain this?

Task D. Sort and calculate got AC. But in query 1 1 1 1 1 1 1 5 two satisfied. But in query 1 1 5 1 1 1 1 1 1 three satisfied. Where am I wrong?

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

    Because we sort the array first, so both of them will produce 1 1 1 1 1 1 1 5. The answer should be three: serve the first two, and serve the last person.

    Hope it helps!

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

what an awful contest ?! Everything depends on problem E!

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

What did solve task C? I am build dinamic and found states with binary finder... Why it was not correct: http://pastebin.com/PHVYYqWC ?

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

The pretest was so strong i got two times WA in problem C&D and at last AC.I scanned the whole c++ coders of my room and there was no sign of mistakes in their codes :D

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

My room 1016, NO successful hacking, NO system test fail. :|

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

rasoolll and Behnam.B cheated look at their submissions : 11152882 and 11153982 they are also from same university (shame on ferdowsi university of mashhad)

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

    Code doesn't look 100% similar. Their outputs on the third test differ also.

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

    This is Common Problem With Short code. Two code can Have similar Idea ( Even These Code seems to be same but not Exactly Same). And another thing is, Generally Student from same University have closer Idea about many problems.

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

I am new to this site, and this was my first ever coding contest. I managed to solve 3 problems getting a rank of 1802. However, I cannot see any rating being alloted to me. Can anyone explain the reason for this, and how I can earn a rating.

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

    System testing wasn't finished. It is finished now. Your rating's 1448, gratz on your first contest!

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

      Thanks, I also wanted to know that few people were awarded more marks for certain questions, and I lost out on few points. For example Problem #1 was of 500 points, where as I was awarded only 408 points, even though I didn't fail any submission. I read somewhere about hacking other people's code and some room concept. Can someone explain me my roles about hacking and what am I supposed to do in a room.

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

        you get less points if you take more time to solve. If you are sure of your solution you can press the lock button on the dashboard. Then you can view others' solutions to that problem by clicking the score in the room. If you find a mistake in their code, give a test case which satisfies constraints and gives sub optimal answer wwith their code. You get +50 if their code gives wrong answer and -50 otherwise. Also, if you click the lock, you cant resubmit for that problem.

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

          It is actually +100 for correct hack.

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

Finally into DIV 1 (purple) after almost a year on CF :D

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

Answers to both of my wrong submissions (WA on pretest one in Problem A and Runtime Error in Problem D) is showing correctly on my computer. anything i am missing here?

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

    When a[i][j] == 3 || a[i][j] == 1 you should skip entry. i cant understand your code seems like you do the same for a[i][j] == 2 and it give WA.

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

In my opinion, problemset was like A-B-B-B-D, but it's just my opinion.

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

Can anyone tell me why this solution gave WA for test 11 question C? I used DP where prev=0 means previous tree wasn't cut, prev=1 means previous tree was cut to left, prev =2 means previous tree was cut to rightLINK

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

    its simple because you assume tree number 2 will always be cut in code: int ans=1+func(2,1); ans=max(ans,1+func(2,2));

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

      No, I am assuming that tree 1 will always be cut to the left (this is optimal, I know). ans=max(ans,1+func(2,2)) means tree 1 is cut to right. func(i,prev) means I am checking for tree i and I have solved for i-1 trees and (i-1)th tree was cut to prev.

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

I tried to solve the problem E using Dijkstra modified. It is my aproach:

  • Save the parents of each node using dijkstra
  • create a toposort for the directed graph of parents
  • for each node select the parent with the minimum weight.

I get WA in the 8th case. The test case is very large and I cant debug it...

Here is my code.

I read several comments and found some similar ideas. can anyone help me? (sorry for my poor english) thanks in advance

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

    Try to change distance (vector dist and priority_queue) to long long :)

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

      Thanks a lot!!! long long vs int

      I try to don't forget it...

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

I am getting WA in http://mirror.codeforces.com/contest/545/problem/D

My solution http://mirror.codeforces.com/contest/545/submission/11166839

why?? please help thnx in advance :)

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

Too few successful hacks for A, B, C, D. Problems were so clear and obvious. Also, since I passed too many pretests, I was sure about getting accepted for first four problems!

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

:D

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

Can anyone plz explain why problem E is not minimum spanning tree? I thought it as MST but I know second test case is not following my observation. So plz elaborate why my assumption is wrong.

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

    The MST does not satisfy the condition: "shortest-path tree from vertex u" ... " the lengths of the shortest paths from u to any vertex to G and to G1 are the same".

    Make some test cases yourself and you'll realize it. (Sorry for my bad english)

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

    You have to find a tree such that each vertex has least-possible distance from an specified vertex of the graph, not just being connected to the tree with least-cost.

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

Since this round was the author's first contest as a writer, I think there should have been a reviewer working with him. The problems were okay, but the complexities didn't match the score. Even though most of the problems were easy, I spent relatively too much time trying to solve them because the translation was not clear enough.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

Impressive result from latisel! http://mirror.codeforces.com/contest/545/...

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

My E solution failed because of long long. I legit feel sad now.

11160086: initial submission
11171670: correct submission

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

this round very easy ! =D

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

has anyone did problem E with MST(kruskal's or prim's )?if yes then please explain the approach?

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

This was my first CF round so I can't compare it with others, but I'd like to give the author some feedback: I enjoyed the round :), although it was an one hour contest for me (A, B, C and D). I couldn't finish E as well, although it was a nice problem, also the only difficult one. I think that C deserved more points than D? or D deserved less points than C?

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

Hi every one in problem C can explain in test #7 why answer is 5? which trees can cut down? I think tree x=1 to right, tree x=41 to left, tree x=55 to left, tree x=59 to right, and last tree with x=105 to right why my answer is wrong?

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

    Your answer is almost right , but always cut the first tree to the left not to the right :)

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

      I forgot tree x=68 so: tree x=1 to left, tree x=41 to left, tree x=55 to left, tree x=59 to right, tree x=68 to left, and last tree with x=105 to right we can cut down 6 tree and correct answer is 5! what's wrong?

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

        If you cut down tree x=59 to right, it takes segment [59;66]. If you cut down tree x=68 to left, it takes sement [61;68]. These segments are intersect, so we can't do this.

        → Reply