How to solve Approximation Problems (Challenge Problems)

[@pradipnitw]

humm .. never thought of these ways.. my mind is running wild after seeing this video ... this is whole new dimension of solving the unsolvable..

[@gkcs]

Haha, truly 😁

[@paulhatcher951]

In the first cycle would you just swap the most significant digits to make sure you get a good spread. Then refine that by swapping more least significant digits ?

[@gauravanand6937]

2^Great tutorial, thanks. A general question, it takes me np time to solve questions (like long challenges codechef problems), so i lack? Practise , iq , analytical skill.?

[@gkcs]

I can't comment on that without knowing how you code, although I am sure your IQ is good enough :) You could try solving more practice problems from other contest sites to improve on the practice and analytical skill.

[@gauravanand6937]

Gaurav Sen , i agree on the iq part :), i think i need to work on my algorithmic design technique. Your videos are much helpful.

[@pritampathak798]

What are the tentative videos that you are going to make on December long challenge?

[@pgpt]

How does if checks if an answer is valid or not.For example,I can output 1 for every test case which would get me a good score without ever computing anything. How do they check if a given score belongs to a valid permutation?

[@gkcs]

Why would outputting 1 everywhere give you a good score?

[@vaibhavambasta8053]

Hi Gaurav, how would you go about utilising complete 100% of time when the problem gets completed in 70% of total time. 25:34?

[@gkcs]

The problem can't be 'solved', since it's a search algorithm with no clear optimal path. The longer you search, the better the results. If you can do the same number of computations in 70% of the time, you can now run 100/70 ~= 142% of the original number of computations in the same amount of time.

[@sriharsha8650]

Are you going to explain problems from Codechef Long Challenge that's going on right now after it's finished?

[@gkcs]

Yes :-)

[@MonikBhanushali]

Great tutorial Gaurav :) I have one suggestion for tutorial. Topic : Palindromic Trees

[@gkcs]

Will keep that in mind :-) Thanks!

[@suryaabhishek]

It is actually *nondeterministic polynomial time*

[@gkcs]

+Abhishek Surya Have a look at Bhisma Raj's comment. I didn't mention 'deterministic' anywhere, on purpose :-)

[@suryaabhishek]

In that case, this is Issued in public interest. "Jan hith mei jaari"

[@shivamsharma8874]

Hello Sir, i saw problem setter's solution. it was so easy . he just print value of A. why....?

[@gkcs]

His score will be terrible, close to 0. Because he just wants to show a sample solution.

[@jayeshmishra7095]

Sir did u had any kt in our engineering college life

[@jayeshmishra7095]

Plss ans

[@gkcs]

Yes :P

[@jayeshmishra7095]

Sir I want to be a good competitive coding what are the initial step as I'm I first year

[@ASHUTOSHKUMAR-zu6kr]

The contrast of video is not high that way blue colour is not visible

[@akhilsurapuram]

Hie gourav, your explanations are so cool. & it's pretty hard to catch up your phase. You should let your views to think and make viewers understand/get to know how you think. In simple easy words GO SLOWWWW

[@gkcs]

Hahaha

[@amur_]

Hey, I'm in class 11. How do I get really like really good at competitive programming?

[@ravishankarjoshi2952]

You should learn C++ or Java well, then C++ STL, then data structures and algorithms from this list: www.quora.com/What-algorithms-should-I-know-to-become-a-good-programmer/answer/Ashish-Kedia?srid=u3swV

[@gauravanand6937]

get into IIT :)

[@arunarkamukhopadhyay6443]

JEE first.

[@RudraSingh-pb5ls]

@@gauravanand6937 honestly worst answer

[@bhi5hmaraj]

I think you have mistaken the meaning of NP . Non Determinism is completely different from Not Polynomial (stackoverflow.com/questions/40207550/np-non-deterministic-polynomial-time)

[@gkcs]

I used the believe that NP problems are Non-Polynomial Time algorithms, thanks for pointing that out :) Luckily the video doesn't mention determinism anywhere, and I meant NP to be a short form of Non Polynomial. Now I know why HackerEarth used the word determinism in the blog! My mistake :-P

[@bhi5hmaraj]

I guess it's a common misconception , even I used to think that NP stands for Non Polynomial before I took the Theory of computation course .

[@dirghrajkushawaha3822]

sir... how to attack on these problems means where to start ..

[@gkcs]

One base solution is enough. Most of the time, you can try to find an answer which is a close approximation. For example: Job: To divide an array into two parts such that the difference in sums is minimum. A very good approximation is sorting the array and putting alternate in each part. The final sum is quite small, and hence this solution can be used as a base solution.

[@bhagwatibhalotia7636]

Great tutorial !

[@gkcs]

+Bhagwati Bhalotia Thanks!

[@DarshanSenTheComposer]

BOOM! Mind blown! :D

[@phantomhieve2353]

nondeterministic polynomial time* there is difference just watched mit ocw video on that.

[@mohitkalra9329]

non deterministic polynomial for NP!

[@akashkandpal1832]

Very Nice video ....

[@cevalfonso]

Wow, TSP has NOT been proven to be non-polynomial! That would imply that P =/= NP, which is one of the most famous open problems in computer science.

[@gkcs]

Yeah, non deterministic polynomial. Trying to find a polynomial solution to this is fun 😛

[@sudheertripathi3882]

Thanks.

[@ayushdeepdabas5383]

Good video

[@gkcs]

Thanks Ayush!

[@algolife2126]

Bro im in btech cse second semester..I also want to be a great programmer like u please help me p.s im also not from good college so im focusing on my skills bro pls tell me where can i ask u my doubts ??

[@lavkushtiwari2799]

@Shashank, you are 2nd sem student and He already completed his graduation so please don't use "Bro" for him.

[@algolife2126]

Lavkush Tiwari C'mon yr how does it even matter I want answer to my question

[@lavkushtiwari2799]

can you please tell me the name of your college?

[@algolife2126]

Lavkush Tiwari Chitkara University

[@sankalpkotewar]

@@algolife2126 Lol your reply, Anyways buddy just keep learning and practicing, that's all! There's no secret here.

[@sridharbajpai420]

i tjink tjats is MAchine Learning?😂