You are not logged in. Please login at www.codechef.com to post your questions!

×

Not a triangle

I am getting WA for the question:http://www.codechef.com/problems/NOTATRI/ Anyone plz. explain where i am wrong.Thnx. My code: http://www.codechef.com/viewsolution/2213497

asked 09 Jun '13, 11:49

fiery's gravatar image

2★fiery
19091117
accept rate: 0%


sorting will help in terms of time. after sorting, start from the greatest value of length, if sum of smallest value and value lesser than(l[k-1]) taken value(l[k]), then add difference to count(cnt=cnt+l[k-1]-l[i]), because sum of all indices between those numbers, if considered particularly, will be lesser than taken value(l[k]). if sum of those two particular indices is greater than or equal to taken value(l[i]+l[j]>=l[k]), then increment the smallest index(i++). loop the aforementioned case for all index. voila.

link

answered 05 Jan '14, 08:35

garakchy's gravatar image

1★garakchy
1.1k163048
accept rate: 1%

1.What we will be doing is , we will take a set of 3 lengths say {first,second,third} such that first<=second<=third. This way we will count only unique sets.
2.After this we will fix first=0 and third = n-1 , i.e first and last elements of sorted array.Yes , array has to be sorted . Quick sort or Merge sort can be used.
3.Now loop is on third = n-1 to 0. for each chosen third , i have inner loop on first.
4.Now second begins from third-1 and move towards first. Now if we find some second such that first + second < third then our condition is satisfied and all such numbers between first and second are suitable candidates for "second". hence we count their number and add them.

For a better understanding of solution look here

link

answered 16 May '14, 21:11

empty_life's gravatar image

2★empty_life
355819
accept rate: 20%

edited 16 May '14, 21:18

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×558

question asked: 09 Jun '13, 11:49

question was seen: 2,180 times

last updated: 16 May '14, 21:18