**Getting Started with Competitive Programming **this course is designed in a way to provide students a real-world analysis of competitive programming, the techniques and implementations are in a way that can be understood by beginner students but students has knowledge of any programming language.

**NPTEL Getting Started with Competitive Programming** is a MOOC course offered by IIT Gandhinagar on the NPTEL platform. The course is developed by

**Prof. Neeldhara**is an Assistant Professor of Computer Science and Engineering at the Indian Institute of Technology, Gandhinagar. Her primary research interest involves the design and analysis of efficient algorithms for “hard” problems in general, and parameterized algorithms in particular.

Final Year Undergraduates**INTENDED AUDIENCE:****Requirements/Prerequisites:**Knowledge of basic data science algorithms**INDUSTRY SUPPORT:**All industry.

**CRITERIA TO GET A CERTIFICATE**

Average assignment score = 25% of the average of the best 8 assignments out of the total 12 assignments given in the course.

Exam score = 75% of the proctored certification exam score out of 100 Final score = Average assignment score + Exam score

Students will be eligible for CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If any of the 2 criteria are not met, the student will not get the certificate even if the Final score >= 40/100.

## Getting Started with Competitive Programming ASSIGNMENT WEEK 6 ANSWERS:-

**Q1.** Alice, Bob, and Charlie live in a country where there are N cities. The cities are numbered from 0 to N-1. For every ordered pair of cities (u, v), there is a flight from City u to City v, which costs C[u][v] rupees.

Alice is initially in City A, Bob is in City B, and Charlie is in City C. Alice has to visit Charlie, but is also wondering if she should also visit Bob before that. That is, Alice has two options:

**Code:-**

**Q2.** You are given a string S = S_{1}S_{2}…S_{N} of length N. Each character of this string is a digit (that is, 0, or 1, …, or 9). You have to start from S_{1}, and reach S_{N}. To do so, you can make multiple teleports. From a particular S_{i}, you can teleport to S_{i-1} or S_{i+1}. You can also teleport to some S_{j}, such that S_{i} = S_{j}.

**Code:-**

## Getting Started with Competitive Programming ASSIGNMENT WEEK 4 ANSWERS:-

**Q1.** You are given a graph with **N** vertices. It initially has no edges. The vertices are numbered from **0** to **N-1**.

You are asked to perform **Q** updates. Each update is one of two types:

- 0 u v – Type 0 – This means that an edge (
**u, v**) should be added to the graph. - 1 u v – Type 1 – Output 1 if there is a path from
**u**to**v**, and 0 otherwise.

**Code:-**

**will update soon and notify on telegram channel so you can join us there**

**Q2.** You are given a graph with **N** vertices and **M** edges. The vertices are numbered from **1** to **N**. The edges are numbered from **1** to **M**. Each vertex also has a weight associated with it – **A _{1}**,

**A**, …,

_{2}**A**.

_{N}**code:-**

## Getting Started with Competitive Programming ASSIGNMENT WEEK 3 ANSWERS:-

**Q1.** You are given a binary string **S = S _{1}S_{2}…A_{N}**. That is, the strong consists only of

**0**s and

**1**s. Your aim is to have more numer of

**1**s in the string than the number of

**0**s. To do so, you are allowed to make some Operations. In a single Operation, you can pick any

**1**in the string which hasn’t been picked so far, and if there is a

**0**adjacent to it (on either side), you can pick at most one of those

**0**s, and convert the

**0**to a

**2**. You can do these Operations as any times as you want.

**Code:-**

```
import java.util.*;
import java.io.*;
public class Main {
public static String traverseString(String s){
s=' '+s+' ';
for(int i=0;i<s.length();i++){
char d=s.charAt(i);
if(d == '1'){
if(s.charAt(i+1) == '0' && s.charAt(i-1) == '0'){
s=s.substring(0,i-1)+'2'+s.substring(i);
continue;
}
else if(s.charAt(i+1) == '0')
s=s.substring(0,i+1)+'2'+s.substring(i+2);
else if(s.charAt(i-1) == '0')
s=s.substring(0,i-1)+'2'+s.substring(i);
}
}
return s.trim();
}
public static int countString(String s){
int one=0,zero=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i) == '1')
one++;
else if(s.charAt(i) == '0')
zero++;
}
if(one>zero)
return 1;
else if(one == zero)
return -1;
else
return 0;
}
public static void main(String[] args) throws IOException {
Scanner sc=new Scanner(System.in);
String s; int n,m;
m=sc.nextInt();
for(int i=0;i<m;i++){
s=sc.next();
s=traverseString(s);
n=countString(s);
System.out.println(n);
}
sc.close();
}
}
```

**Q2.** There are **N** movies, numbered from **1** to **N**, that you’d like to watch. The ith movie has two integers attached with it – **D _{i}** and

**L**, which represent the movie’s director, and its length in minutes. You are going to watch these movies exactly once, but you can watch them in any order.

_{i}**Code:-**

## Getting Started with Competitive Programming ASSIGNMENT WEEK 2 ANSWERS:-

**Q1.** You are given an integer **N**, an integer **K**, and an array **A _{1}, A_{2}, …, A_{N}** of size

**N**. All the initial values in this array are guaranteed to be between

**1**and

**10**. You are allowed to make some Modifications to the array. In a single Modification, you should choose a contiguous segment of size

^{9}**K**, say

**A**. Let the minimum value among these

_{i}, A_{i+1}, …, A_{i+K-1}**K**values be

**Min**. You then change all the elements in this segment whose value is

**Min**, to

**10**.

^{9}+1**Code:-**

```
def find_sub_idx(test_list, repl_list, start = 0):
length = len(repl_list)
for idx in range(start, len(test_list)):
if test_list[idx : idx + length] == repl_list:
return idx, idx + length
def replace_sub(test_list, repl_list, new_list):
length = len(new_list)
idx = 0
for start, end in iter(lambda: find_sub_idx(test_list, repl_list, idx), None):
test_list[start : end] = new_list
idx = start + length
flag=0
count=0
N,K=input().split()
N=int(N)
K=int(K)
l1=[int(i) for i in input().split()]
l2=[]
#li=list(map(int,input().split()))
while flag != -1:
for i in range(0,N):
if(l1[i]==min(l1)):
if((i+(K-1))<=N-1):
l2=l1[i:i+K]
else:
l2=l1[(i+(K-1))-N:N+1]
l3=[10e9+1 if i==min(l2) else i for i in l2]
count+=1
replace_sub(l1, l2, l3)
#print(l1)
if(min(l1)==10e9+1):
break
if(min(l1)!=10e9+1):
flag=0
else:
flag=-1
print(count)
```

**For Quiz Assignment:- ** Getting Started with Competitive Programming

**Note:- WE NEVER PROMOTE COPYING AND We do not claim 100% surety of answers, these answers are based on our sole knowledge and by posting these answers we are just trying to help students to reference, so we urge do you assignment own your own.**

**Q2.** You are given an integer **N**, an integer **M**, and an array **A _{1}, A_{2}, …, A_{N}** of size

**N**. You need to find the smallest positive integer

**K**, such that ceil(

**A**) + ceil(

_{1}/K**A**) + … + ceil(

_{2}/K**A**) is less than or equal to

_{N}/K**M**.

**Code:-**

```
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T,N;
double M,A[],sum=0;
T=sc.nextInt();
for(int i=0;i<T;i++){
N=sc.nextInt();
M=sc.nextDouble();
A=new double[N];
for(int j=0;j<N;j++){
A[j]=sc.nextDouble();
}
double max = Arrays.stream(A).max().getAsDouble();
for(int K=1;K<=max;K++){
for(int l=0;l<N;l++){
sum=sum+Math.ceil(A[l]/K);
//System.out.print(sum+" ");
}
if(sum<=M){
System.out.println(K);
break;
}
sum=0;
}
}
sc.close();
}
}
```

## NPTEL Getting Started with Competitive Programming ASSIGNMENT WEEK 1 ANSWERS:-

**Q1.** Swayam wants to play a game with you. He has an integer with him, **S**, but he has hid it from you. Instead, he has shared some information about **S**.

In particular, for every **i** such that **1 ≤ i ≤ N**, he has told you the value **⌊(i*S)/K⌋**. This is given to you as the array **A _{1}, A_{2}, …, A_{N}**, where

**A**. He has also told you the value of

_{i}= ⌊(i*S)/K⌋**K**. But since he has not shared the value of

**S**, you want to find the largest possible range

**[L,R]**in which

**S**could lie. That is, find the largest possible range

**[L,R]**such that, for any integer

**P ∈ [L,R]**,

**A**is equal to

_{i}**⌊(i*P)/K⌋**for all

**i**.

**Code:-**

```
import java.util.*;
public class Swayam1{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T,N;
double K,a[],arr[];
double l=0,u=0;
T=sc.nextInt();
for(int i=0;i<T;i++){
N=sc.nextInt();
K=sc.nextDouble();
a=new double[N];
arr=new double[N];
ArrayList<Double> l1=new ArrayList<Double>();
for(int j=0;j<N;j++){
a[j]=sc.nextDouble();
}
l=a[0]*K;
u=(a[0]+1)*K;
while(l<=u){
for(int k=0;k<N;k++){
arr[k]=Math.floor(((k+1)*l)/K);
}
if(Arrays.equals(arr, a)){
l1.add(l);
l++;
}
else{
l++;
}
}
System.out.printf("%.0f %.0f\n",l1.get(0),l1.get(l1.size()-1));
}
sc.close();
}
}
```

**Q2.** Swayam likes prime numbers a lot. He calls a number `good` if the number of divisors (including 1 and the number itself) of this number is an odd prime.

Help him find the number of `good` numbers in the range from 1 to **N** (both end points inclusive).

**Code:-**

```
import java.util.*;
public class Swayam{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T,c=0,f=0,d=0;
double N;
T=sc.nextInt();
for(int i=0;i<T;i++){
N=sc.nextDouble();
for(double j=1;j<=N;j++){
for(double k=1;k<=j;k++){
if(j%k==0){
c++;
}
}
for(double l=1;l<=c;l++){
if(c%l==0 && c%2!=0){
f++;
}
}
if(f==2)
d++;
c=0;f=0;
}
System.out.println(d);
d=0;
}
sc.close();
}
}
```

**Also check :- Internship oppurtinites**

**Note:- We do not claim 100% surety of answers, these answers are based on our sole knowledge, and by posting these answers we are just trying to help students, so we urge do your assignment own your own.**