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

×

TRIPLET2 - Editorial

Queer Triplets

Problem:
practice

Tags: Number Theory

Author: Kaustav.
Tester: Shami.

This problem is a trick question. If you were to solve it with brute force taking the question too seriously you will time out. Here is the solution

Yes, the bounds of 10^18 (later reduced to 10^16) will not let you converge in time for the solution. You have to figure out the actual bound of I,j and k to compute them in time. Even if you were to pick lesser constraining bound say 100 you would have got the solution. The bounds you compute are 2 <= i,j,k <= 11. The way you go about is that if you are to notice ii-k, kj-I and j*i-k are symmetric where every permutation of the i,j, and k has to satisfy the constraint. Hence if you are to only consider the i<=j<=k go and plug i=0,1,2,… you will soon discover that the bound on i is 2<=i<=3. You then move the analysis to discover bounds of j to be actually bounded by only 2 and 5 and k to be only 2 and 11. Given this bound just run to see the satisfiability of the the constraints and you will have the all of the solution.

asked 12 Jan, 15:52

mmmreddy's gravatar image

0★mmmreddy
121
accept rate: 0%

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:

×565

question asked: 12 Jan, 15:52

question was seen: 113 times

last updated: 12 Jan, 15:52