Getting Started with Competitive Programming ASSIGNMENT 2021

Competitive Programming

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.

  1. INTENDED AUDIENCE: Final Year Undergraduates
  2. Requirements/Prerequisites: Knowledge of basic data science algorithms
  3. 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 = S1S2…SN of length N. Each character of this string is a digit (that is, 0, or 1, …, or 9). You have to start from S1, and reach SN. To do so, you can make multiple teleports. From a particular Si, you can teleport to Si-1 or Si+1. You can also teleport to some Sj, such that Si = Sj.

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
quizxp telegram

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 – A1, A2, …, AN.

code:-

Getting Started with Competitive Programming ASSIGNMENT WEEK 3 ANSWERS:-

Q1. You are given a binary string S = S1S2…AN. That is, the strong consists only of 0s and 1s. Your aim is to have more numer of 1s in the string than the number of 0s. 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 0s, 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();
    }
}
quizxp telegram

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 – Di and Li, 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.

Code:-

Getting Started with Competitive Programming ASSIGNMENT WEEK 2 ANSWERS:-

Q1. You are given an integer N, an integer K, and an array A1, A2, …, AN of size N. All the initial values in this array are guaranteed to be between 1 and 109. You are allowed to make some Modifications to the array. In a single Modification, you should choose a contiguous segment of size K, say Ai, Ai+1, …, Ai+K-1. Let the minimum value among these K values be Min. You then change all the elements in this segment whose value is Min, to 109+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 A1, A2, …, AN of size N. You need to find the smallest positive integer K, such that ceil(A1/K) + ceil(A2/K) + … + ceil(AN/K) is less than or equal to 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();
    }
}
quizxp telegram

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 A1, A2, …, AN, where Ai = ⌊(i*S)/K⌋. He has also told you the value of 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], Ai is equal to ⌊(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.