Sign up now
to enroll in courses, follow best educators, interact with the community and track your progress.
Enroll
92
Download
Problem statements
1,010 plays

More
Learn about various types of problems and the structure of a statement

Balajiganapathi Senthilnathan
I am a competitive programming enthusiast.

U
Unacademy user
sir for amcat exam is this helpful?????
Saket Sourav
2 years ago
No!! In Amcat you'll be given only the simple pseudo codes and you have to predict the output. This video is helpful for the Written exams conducted by various companies, there you have to follow the same approach.
  1. bfs (competitive programming) Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 1/28


  2. Introduction to Competitive Programming Get started with competitive programming part 2 Balajiganapathi S code-drills.com April 23, 2017 Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 2 28


  3. Outline Structure of a problem statement Problem types Common mistakes Conclusion 2 3 Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 3/28


  4. Structure of a problem statement Outline Structure of a problem statement Problem types Common mistakes Conclusion 2 Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 4/28


  5. Structure of a problem statement Statement http://codeforces.com/problemset/problem/796/A 1. CODEFORCES Sponoored by Telegram You have HOME CONTESTS GYM PROBLENSET GOUPS RATING APM RCVK (UPHFTBATTLE A. Buying A House time lii per est 2 seconds memory lmit pce teet: 258 megabybes input: seanda d irput Finishad Practice rn the wrard had rever bved anyone betere urti he fell in love with a gia, whose name mains trinoen to us. the gid ives in house m cf a vilage. There are n houses in thar village, Ining in a sraight ire trom left to rght house 1. ouse 2.... house n Tre v ages also wet-structured; house i ond house i l( 1 1 < N)A' exactly 10 meters away. tsdis vilege, sont houses are occuped, and pome a e not indeed, unoccupied housss can be purchabed -submit? You will be given n integers a,a that desete the availablity and the prices of the houses It house i is oceupind, and therefora cannot be bought, then a,equas D Ohenwise, house i canbe bought, and d, represents the money nequised o buy it, in dolars AsZane has orty dolars spare, tbecomes achallenplor him to choose the hust to purchase, so that he could bre as near ns possible to his crush. Help zane determine the minimum dsance from hs crusiths house to some house he can atord, to help him succeed in his love Input The first line contains three imegers n, m, and k2sns 100, 1msn1sks100) he number of houses in the vilage, the houGand Ewips where the or lves and the amount ot money Zane has in doilars), respectively The second line contin s n megers@gaa- , a, a <a,s100-denotng the avalabilty and te proes of thehases t is qustaneed that a 0and that is pocable to ourchase some houee wih no mone than k dollars Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 5/28 5 28


  6. Structure of a problem statement Statement - Story A. Buying A House time limit per test: 2 seconds memory limit per test: 256 megabytes input: standard input output: standard output Zane the wizard had never loved anyone before, until he fell in love with a girl, whose name remains unknown to us. The girl lives in house m of a village. There are n houses in that village, lining in a straight line from left to right: house 1, house 2, . house n. The village is also well structured: house 1 and house i + 1 1s r) are exactly 10 meters away. In this vilage, some houses are occupied, and some are not. Indeed, unoccupied houses can be purchased. You will be given n integers a1, a2, ..., an that denote the availability and the prices of the houses. If house i is occupied, and therefore cannot be bought, then a equals 0. Otherwise, house i can be bought, and a represents the money required to buy it, in dollars. As Zane has only k dollars to spare, it becomes a challenge for him to choose the house to purchase, so that he could live as near as possible to his crush. Help Zane determine the minimum distance from his crush's house to some house he can afford, to help him succeed n his love Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 6 28 April 23, 2017 6/28


  7. Structure of a problem statement Statement - Task The girl lives in house m of a village. There are n houses in that village, lining in a straight line from left to right: house 1, house 2,. house n. The village is also well-structured: house i and house i +1 (1 si<n) are exactly 10 meters away. In this village, some houses are occupied, and some are not. Indeed, unoccupied houses can be purchased. You will be given n integers a, a2,.. an that denote the availability and the prices of the houses. If house i is occupied, and therefore cannot be bought, then ai equals 0. Otherwise, house i can be bought, and a represents the money required to buy it, in dollars. As Zane has only k dollars to spare, it becomes a challenge for him to choose the house to purchase, so that he could live as near as possible to his crush. Help Zane determine the minimum distance from his crush's house to some house he can afford, to help him succeed in his love. Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 7/28


  8. Structure of a problem statement Statement Input format Input The first line contains three integers n, m, and k (2sns 100, 1smsn, 1sks 100)-thenumber of houses in the village, the house where the girl lives, and the amount of money Zane has (in dollars), respectively. The second line contains n integers a, a2,., an (0 s ai s 100)-denoting the availability and the prices of the houses. It is guaranteed that am 0 and that it is possible to purchase some house with no more than k dollars. Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 8 28 April 23, 2017 8/28


  9. Structure of a problem statement Statement - Output format Output Print one integer- the minimum distance, in meters, from the house where the girl Zane likes lives to the house Zane can buy. Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 9 28 April 23, 2017 9/28


  10. Structure of a problem statement Statement Examples Examples input 5 1 20 27 32 21 19 output 40 input 7 3 50 62 99 33 22 output 30 input 10 5 100 output 20 Note In the first sample, with k = 20 dollars, Zane can buy only house 5. The distance from house m = 1 to house 5 is 10 + 10 + 10 10 40 meters. In the second sample, Zane can buy houses 6 and 7. It is better to buy house 6 than house 7, sance house m = 3 and house 6 are only 30 meters away, while house m 3 and house 7 are 40 meters away Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 10 28


  11. Structure of a problem statement Statement - Time limit A. Buying A House time limit per test: 2 seconds memory limit per test: 256 megabytes input: standard input output: standard output Zane the wizard had never loved anyone before, until he fell in love with a girl, whose name remains unknown to us. Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 11 28


  12. Structure of a problem statement Statement solution 1 #include <bits/stdc++.h> 2using namespace std; 4 int main) f int n, m, k, a, ans = 100000; cin >> n>> m >> k; for(int 1-1; i n; i++) { 5 7 8 9 10 cin > a; if (a != 0 && a <= k) ans = min(ans , 10 * abs (m-i)); 11 cout << ans<endl; 12 13 14 return 0; Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 12 28


  13. Problem types Problem types scoring Binary/classical o Either correct or wrong no partial o Most common form Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 14 28


  14. Problem types Problem types scoring Approximate o There can be many valid solution o Each valid output may be assigned a score Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 17 28


  15. Problem types Problem types output Multiple outputs o Multiple valid outputs possible Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 19 28


  16. Problem types Problem types output Multiple outputs o Multiple valid outputs possible http://codeforces.com/problemset/problem/534/A Output In the first line print integer k-the maximum number of students who can be seated so that no two students with adjacent numbers sit next to each other. In the second line print k distinct integers a, a2, ..., ak (1 s aiS n), where a, is the number of the student on the i-th position. The students on adjacent positions mustn't have adjacent numbers. Formally, the following should be true: la,-a |-1 for all 1 from 1 to k-1 If there are several possible answers, output any of them Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 19 28


  17. Problem types Problem types output Problem types interactive o Output and input are mixed Output and input are mixed Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 20 28


  18. Problem types Problem types output http://codeforces.com/gym/101021/problem/A Input Use standard input to read the responses to the queries. The input will contain responses to your queries- strings" and". The i-th string is a response to the i-th your query. When your program will guess the number print " ! x", where x is the answer and terminate your program. The testing system will allow you to read the response on the query only after your program print the query for the system and perform flush operation. Output To make the queries your program must use standard output. 10%), one query per line. After printing each line your program must Your program must print the queries - integer numbers xi (1sxs perform operation flush Each of the values X, mean the query to the testing system. The response to the query will be given in the input file after you flush output. In case your program guessed the number X, print string"! X" where X- is the answer, and terminate your program Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 21 28


  19. Common mistakes Common mistakes - not returning 1int main) 3 4 return 0; // DO THIS 5 Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 24 28


  20. Common mistakes Common mistakes - wrong I/O format # of test cases o Outputting doubles, newlines etc. Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 25 28


  21. Common mistakes Common mistakes edge cases o Only testing on sample case Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 26/ 28


  22. Common mistakes Common mistakes edge cases o Only testing on sample case o Pay attention to constraints and input sections Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 26/ 28


  23. Conclusion Outline Structure of a problem statement Problem types Common mistakes 2 Conclusion Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 27 28


  24. Conclusion Thank you Balajiganapathi S (code-drills.com) Intro to CP April 23, 2017 28 28