harrypotter0's blog

By harrypotter0, history, 5 years ago, In English

I am not able to understand the approach used for this problem.

Can someone help me understand this submission provided by the author.

I know BIT(or Fenwick Tree) so any solution using BIT approach with some explanation would be helpful.

Thank you.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By harrypotter0, history, 5 years ago, In English

Hi there, I am trying to solve a problem with sparse table, I am getting TLE on this problem.

Here is what I tried.

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

By harrypotter0, history, 5 years ago, In English

How to approach this problem? This problem was asked in CodeNet Challenge organized by NetApp Company.

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Hello friends I cam across this problem

If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn] , solution should be in-place

I came with an idea :: First swap elements in the middle pair

Next swap elements in the middle two pairs

Next swap elements in the middle three pairs

iterate n-1 steps.

Ex: with n = 4.

a1 a2 a3 a4 b1 b2 b3 b4

a1 a2 a3 b1 a4 b2 b3 b4

a1 a2 b1 a3 b2 a4 b3 b4

a1 b1 a2 b2 a3 b3 a4 b4

Can someone implement this in C++ . I know the problem asked is quite silly but I am not able to implement this using C++ . Somebody please help !!

OR

If anyone has a solution which takes O(n) time complexity and O(1) space complexity he/she is most welcome to add his code below in comments :-)

Space complexity of O(1) is the priority here . Thanks in advance :)

Full text and comments »

  • Vote: I like it
  • -18
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Given an int array which might contain duplicates, find the largest subset of it which form a sequence. Ex: {1,6,10,4,7,9,5} then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time ??

Thanks in advance :)

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Hello to MikeMirzayanov and company , I have came across this bug in Codeforces website . I am unable to view the website as usual for 2 hours now . This problem is faced not only by me but by some other friends of mine . I am including the screenshots of my screen . Also to make sure that it is not a local problem on my system I have attached other sites screenshots too . Please resolve this matter as soon as possible . Thanks in advance :)

My problem is still not resolved I am unable to participate in contests in Codeforces due to shrinkage in the view UI of Codeforces for me and in my local area too . Please fix this issue ;) I am attaching a screenshot of my screen of Codeforces (I hope the screenshot is uploaded cause it's not shown in my local system ) . IF such problems keep continuing i guess I should move to some other OJ :( ![ ](http://codeforces.com/a711fd/Screenshot from 2017-08-31 12-49-28.png)

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Creating a group on Telegram . Please guys install Telegram on your android phones . We can have a good discussion over there about our doubts related to Competitive Programming . Link is here

Full text and comments »

  • Vote: I like it
  • -32
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Hi guys , I have been trying to pass this test case But i don't know why the time limit gets exceeded time and again . Can anyone find the error or at least provide a hint (how to proceed for this solution ) ?

Problem

Result ::

My submission ::::

/*
Hey , this one is mine ..
make a new one for yourself
             ---->>AKASH KANDPAL
             */
using namespace std;
#include "bits/stdc++.h"
#include <iostream>
#include <string>
#include <locale>
#include <ctype.h>
#include <string.h>
#include <typeinfo>
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#define st string
#define ld long double
#define mod 1000000007
typedef long long int ll;
typedef pair < int , int > pii;
typedef vector <int> vi;
typedef vector <char> vc;
#define eps 1e-8
#define PI 3.141592653589793
#define ld long double
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
ll INF = 1e18;
const int N = 600331;
#define MOD 1e9+7
 
/////////////////////////////////////////////////////
vector<int> comp;
int colored[N];
vi g[N];
void dfs(int v)
{
	comp.push_back(v);
	colored[v]=1;
	for (ll i=0;i<g[v].size();i++)
	{
		ll to=g[v][i];
		if (colored[to])
			continue;
		dfs(to);
	}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
ll lcm(ll a,ll b)
{
    ll m,n;
    m=a;
    n=b;
    while(m!=n)
    {
	if(m < n)
	m=m+a;
	else
    n=n+b;
    }
    return m;
}
////////////////////////////////////////////////////////////////////////
 
void cal()
{
  string week[]={"sun","mon","tue","wed","thu","fri","sat"};
  ll year,days;
  cin>>year;
  days = 365*year + (year-1)/4 - (year-1)/100 + (year-1)/400 ;
  cout<<week[days%7]<<endl;
}
  ////////////////////////////////////////////////////////////////////////////
ll palin(ll x)
  {
  ll t=x,y=0;
  while(t>0)
  {
  ll rem =t%10;
  y=y*10+rem;
  t/=10;
  }
  if(x==y)
  return 1;
  else
  return 0;
  }
////////////////////////////////////////////////////////////////////////////
/*for(i=0;i<n;i++)
v.pb(i+1);f trgf  bvb gbnnnnnn             m,\ n b  cbbbbb  hgbn jyu  gbvv m,;hhjyyuu
for(i=0;i<k;i++)
{
cin>>a;
a=a%v.size();
for(j=0;j<a;j++)
rotate(v.begin(),v.begin()+1,v.end());
cout<<v[0]<<" ";
v.erase(v.begin());
*/
///////////////////////////////////////////////////////////////////////////
bool f(char ch1,char ch2){
	if(tolower(ch1)!=tolower(ch2)){
		return tolower(ch1)<tolower(ch2);
	}
	return ch1<ch2;
}
////////////////////////////////////////////////////////////////////////////
   /* double b = 2.0459332;
    stringstream ss;
    ss << fixed << setprecision(3) << b;
    string v;
    ss >> v; // v will be "2.046"
*/
///////////////////////////////////////////////////////////////////////////
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cout << (fixed) << setprecision(10);
ll t,i,f=0,c=0,r=0,j,p,pa,a[901501]={0},n,n1,k;
cin>>t;
while(t--)
{
cin>>n1>>k;
f=0;
while(n1--)
{
cin>>p;

while(p--)
{
cin>>pa;
a[pa]++;
}

for(ll l=1;l<=k;l++)
{if(a[l]==0)
{f=0;
break;}
else
f=1;}

if(f==1 && n1==0)
{cout<<"all"<<endl;}

if(f==0 && n1==0)
{cout<<"sad"<<endl;}

if(f==1 && n1!=0)
{cout<<"some"<<endl;
while(n1--){cin>>p;
while(p--){cin>>pa;r++;}}break;}
}
for(ll i=1;i<=k;i++)
a[i]=0;
}
//cout<<r;
return 0;
}

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Hi guys .. CodeVita — the global coding contest by TCS is now in its 6th year. The CodeVita journey began in 2012 with the aim of promoting Programming-As-A-Sport, and has touched many milestones since then. In 2014 was the first time we opened the contest globally and last year we had registrations from 40 plus nations. Its popularity with the student community peaked last year when we saw 2,61,000 plus registrations and also secured a place in the Limca Book of Records.

Hope you too had great fun participating in previous seasons of CodeVita. With season 6 we are looking at it getting better, more challenging and super exciting. This season CodeVita is an individual contest. Unlike the other seasons it will not be a team contest. The contest will comprise of several rounds of coding. To participate in CodeVita, one needs to register on the Campus Commune portal.

There will be 3 main rounds to the contest.

Round 1: there will be various regional/zonal rounds. This will be conducted in 3 phases between Jul – Aug 2017, across India. We will map the student to the region/zone based on the location of their college. Details of zonal mapping and the exact time-lines will be communicated subsequently.

Round 2: Top performers from the zonal rounds will move to round 2. Top performers from round 2 have the opportunity to move to the Grand Finale, The list of Finalists is compiled only after all regional rounds across the globe are completed

Grand Finale: To be held in one of the TCSL offices in India. Top 3 contestant will be declared as winners of the contest. Winners (Top 3 contestants) will receive a total cash prize of USD 20,000. We will be extending internships and offers to top coders from the contest, we are looking at making upto 2000 offers this year

**** link to register

Full text and comments »

  • Vote: I like it
  • -20
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Hi guys , recently I tried to accept this question but was partially successful in my approach (30 points only). I have tried all my efforts but could not reduce the complexity of my code .Any help or suggestion will be highly appreciated .Thanks in advanvce .

Problem link ::

My submission ::

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Hello guys , my request to codeforces head please organise contests evenly say 1 contest/week so that new comers have ample of contests to practice on .

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Sample Input 0

6 31415926535897932384626433832795 1 3 10 3 5

Sample Output 0

1 3 3 5 10 31415926535897932384626433832795

my solution

include <bits/stdc++.h>

using namespace std; int main() { long long int n,i,a,s=0,m ; string str[201202]; cin>>n; for(i=0;i<n;i++) cin>>str[i]; sort(str,str+n); for(i=0;i<n;i++) { cout<<str[i]; } return 0; }

But i am getting this as output (attached ) Any help will be highly appreciated :)

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

PROBLEM : http://www.spoj.com/problems/PRIME1/

MY SOURCE CODE:::::: IN GNU G++11 5.1.0

include <bits/stdc++.h>

using namespace std;

void prime(int low,int high) {

int flag=0,i,temp;
if (low > high) {
    temp = low;
    low = high;
    high = temp;
}
while (low <=high)
{
    flag = 0;
    for(i = 2; i <= low/2; ++i)
    {
        if(low % i == 0)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 0 && low!=1)
       cout<<low<<endl;
    ++low;
}

} int main() { long long int n,a,b; cin>>n; while(n--) { cin>>a>>b;prime(a,b);cout<<endl; } return 0; }

Please can anyone correct my solution or tell me the problem in my code......thanks in advance :)

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

First do a self analysis (truthful) — don’t assume you are the best or the worst.

List the areas to improve,

Language skills — C++/Java Math skills Data structures — including the tough ones Trees, Graphs etc. Algorithms (not just simple sorting, but advanced ones that’s required for competitive programming). Once you have a fair idea, then start work — be humble enough to admit you do not have the skills of Anudeep Nekkanti or Ashish Kedia at the beginning.

Keep a small goal to solve enough Div-II 250 problems without peaking into solutions, then 500 pointers, and then 1000 pointer in Div-II. During this process, you can learn and improve your skills in implementation, solving and speed.

The process will be slow and may take up to 2–3 years, be patient and measure growth in each step. As you slowly climb the steps, your confidence will improve and one day can be among the top programmers. The most important point is to not loose patience, and when you do take a break and come back stronger.

Some things you could do are read/ view/study the following,

Mathematics for Computer science (MIT OCW) Stanford — Algorithms I & II — Coursera — Free Online Courses From Top Universities | Coursera Introduction to Algorithms — CLRS Concrete Mathematics by Graham, Knuth & Patashnik. This should be more than sufficient to start with and reach a level above average programmers. Be patient while reading these books, as they are little difficult to understand and learn. Try reading multiple times — if you did not understand the content.

In short : practice make perfectness.

You should try to practice the competitive problems which are beyond your ability or knowledge but no more than a lot beyond your ability. For OJ, I recommend HackerRank or Topcoder since on these site, you can review other programmer's code or solution. Find some descent algorithm books to learn(CLRS for example), but do not only read the book, keep practice during the process. You can find problems of the topic you're reading to practice. On hackerrank, this is easy, since they already classify the problem by topics. Learn math, especially discrete mathematics. I recommend the book "Concrete mathematics" Solve, review, solve review, repeat this process Prepare your coding library from the start, try to review your library once in a while Find some persons with the same passion as you to form a team, go along the way together since ACM-ICPC is a team contests. And encourage each other. Finally, and most important one: Have fun, avoid over training. If you find it is tired to train, drop it, play with friends, find a girlfriend, do some other things. And then returned with passion and energy again.

You can read the story of the most successful topcoder Petr(The Story of Petr Mitrichev — Target in Six Steps) to find some keys to success in competitive programming.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By harrypotter0, history, 7 years ago, In English

Well I would suggest you to check out Programming Competition,Programming Contest,Online Computer Programming. Here is the details about as the codechef team promote the students for ACM-ICPC or you can also check out the actual university site which conduct ICPC The ACM-ICPC International Collegiate Programming Contest

And to practice problems you can you can refer following sites 1. http://codechef.com 2. http://spoj.com 3. http://hackerrank.com 4. http://codecademy.com 5. http://topcoder.com 6. http://codeforces.com

Good Luck...

for the details about ACM-ICPC 2015 you can read the details ACM ICPC 2015 | CodeChef. I hope you'll find most of the things... Here are some steps to get started and be good at it.

Get comfortable writing code in either of one of these languages C, C++ or Java. Why only C, C++ or Java? Because these are the standard languages allowed in any programming competition.

If you are already good at C, it is suggested to learn C++. It is the most popular language among competitive programmers because of its speed and an excellent library in the form of STL (Standard Template Library).

Pick an online judge. Recommended ones are Topcoder and Codeforces. These sites have high quality of problems and also allow you to see other’s code post contest completion. These also categorize problems based on the topic. Some other popular judges include SPOJ, CodeChef (powered by SPOJ) andHackerEarth.

To begin with, start with simple problems that typically require transformingEnglish to code and does not require any knowledge on algorithms. Solving Div 2 250 (Division 2, 250 points) in Topcoder or Div 2 Problem A in Codeforces is a good start.

At the early stages of programming one tends to write long pieces of code, which is actually not required. Try to keep codes short and simple.

Practice these problems until you become comfortable that you can submit it for 240 odd points on any day.

Start implementing basic(or standard) algorithms. It is suggested to read them from Topcoder tutorials or Introduction to algorithms.

1) Graph algorithms: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.

2) Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.

3) Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.

3) Greedy: Standard problems such as Activity selection.

4) Search techniques: Binary search, Ternary search and Meet in the middle.

5) Data structures (Basic): Stacks, Queues, Trees and Heaps.

6) Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.

7) Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.

8) Computational geometry: Graham-Scan for convex hull, Line sweep.

9) Game theory: Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.

The list is not complete but these are the ones that you encounter very frequently in the contests. There are other algorithms but are required very rarely in the contests.

You can find description and implementation of standard algorithms here

Once you have sufficient knowledge of popular algorithms, you can start solving the medium level problems. That is Div 2 all problems in Topcoder and Codeforces. It is advisable not to go for Div 1 500 at this point.

Learning to code is all about practicing. Participate regularly in the programming contests. Solve the ones that you cannot solve in the contest, after the contest. Apart from Topcoder and Codeforces you can also look at HackerEarth Challengesor Codechef contests.

Read the codes of high rated programmers. Compare your solution with them. You can observe that it is simple and shorter than your solution. Analyse how they have approached and improve your implementation skills.

Read the editorials after the contest. You can learn how to solve the problems that you were not able to solve in the contest and learn alternative ways to solve the problems which you could solve.

Always practice the problems that you could solve in the contest. Suppose if you are able to solve Div 2 250 and 500 in the contest but not Div 2 1000 then practice as many Div 2 1000 problems as as you can.

Do not spend too much time if you are not getting the solution or are stuck somewhere.

After you feel that you have spent enough time, look at the editorials. Understand the algorithm and code it. Do not look at the actual solution before you have attempted to write the code on your own.

Programming is a very practical and hands on skill. You have to continuously do it to be good at it. It’s not enough to solve the problem theoretically, you have to code it and get the solution accepted. Knowing which algorithm/logic to use and implementing it are two different things. It takes both to be good at programming.

Programming learning phase is going to take a lot of time and the key is practicing regularly. It takes some time before you can attempt Div 1 500 and other tough problems. Do not give up on reading the editorials and implementing them, even if it takes many hours/days. Remember everything requires practice to master it.

It takes considerable amount of time before you get good at it. You have to keep yourself motivated throughout. Forming a team and practicing is a good choice. Not giving up is the key here. 76.7k Views · View Upvotes Upvote1.2kDownvoteComments7+ Share Viktória Nemkin Viktória Nemkin, studies software engineering at Budapest University of Technology and Economics. Updated Jan 20 · Upvoted by Jessica Su, CS PhD student at Stanford Originally Answered: Should I get involved in competitive programming? How do I begin? You won't regret if you do so. Doing competitive programming improves your problem solving skills (applies for any topic, not just algorithms), gives you persistence and makes you a lot more confident in yourself, also you can find quite a few nice people who will help you along the way.

You can do a few things to get started in competitive programming. I'm assuming you are a complete beginner, please correct me if this is not the case.

Mindset

This sounds off topic but please bear with me for a moment. What I struggle with a lot is essentially not doing what I know I should and want to be doing. My mind is not focused, I go watch a stupid video on youtube and the whole day is gone. It is really hard for me to get myself going. I don't know you, I don't know if you have the same struggles as I do but maybe some of this advice will help you stay focused if you need it.

Here are a few things I've learnt about doing competitive stuff:

You don't have to and you really shouldn't overwhelm yourself on the first time. Don't go to the bookstore and buy the heaviest, biggest book on Computer Science only to read the first few pages and realize you don't understand it and give up. I'm guilty of doing this a lot. Instead, try to find something that is not so into detail and easier to wrap your head around it. In the next steps I try to recommend you easy to understand tutorials online. Don't wait to get motivated. I find this advice really good because it is a great insight to how your mind actually works. I'm sure there are a few lucky people to whom this doesn't apply but for the rest of us, we are not going to feel like studying and practicing all the time. There will be days when we will get bored doing it. There will be days when we will want to go do other fun things. What makes successful people different from everybody else is that they can handle the boredom of doing the things they want to be doing for a long time. (I've read this here: How to Stay Focused When You Get Bored Working Toward Your Goals .) Don't try to completely change your schedule and study and practice in all of your free time. Completely changing everything is really hard and can easily overwhelm you and make you give up. Just like trying to get down to a healthy weight by eating 500 calories a day. You just can't stick to it in the long run. Instead, go for small changes, but do them regularly. Don't let other people's success demotivate you. You know how they say no matter how good you are, there is an Asian kid who is better than you? I'm no IOI medalist. I did compete in the country level qualifiers to get out but no success. I see famous people answering questions here on Quora and I'm really not one of them. But really, who cares? Feel proud of what you have accomplished so far and instead of comparing yourself to everybody else, try to outdo yourself. Generally, a lot of hard working famous people are also very humble and they will tell you they had their moments of giving up, failing and feeling bad about themselves. You only see their success but not how they got there. I hope this advice helps you stay on track. Now to the more technical stuff.

Knowledge in theory of algorithms and data structures

I started practicing for competitive programming with my teacher in school, the first few things we learnt were:

Data Structures: Topcoder tutorial Binary Search: Topcoder tutorial Sorting algorithms: Wikipedia list of sorting algorithms (They usually teach a few of them like these in this order: Bubble sort, Insertion sort, Merge sort, Heapsort, Quicksort and Bucket sort, a bit different. Look at visualizations too, like at sorting.at they are cool.) Greedy algorithms: Quora: What is an intuitive explanation of greedy algorithms? Backtracking: GeeksforGeeks: The Knight's tour problem, Sada Kurapati: N Queens problem Dynamic programming: Function Space: Fibonacci series and Dynamic programming (And I really like Jonathan Paulson's answer here.) Graph theory and some algorithms: Computer Science Source: Depth/Breadth First Search and Youtube video: Dijkstra's algorithm were the first for me. I think that's basically all I knew when I first competed. Probably other people will tell you a lot of other things, this is just how I started out.

Later, you can find a book that works for you and you can read it or watch an online course to get into the topic more deeply.

Here are some examples:

Quora: Computer Programming: What are the best books on Competitive programming out there?

Quora: What is the best set of algorithms books to read?

Topcoder Data Science Tutorials

Youtube playlist: MIT 6.006 Introduction to Algorithms, Fall 2011

Coursera: Princeton Algorithms course

Coursera: Stanford Algorithms course

Khan Academy course with Darthmouth college

A programming language

I like C++. It is fast, it has its Standard Template Library with plenty of cool stuff. For example if you need a good sorting algorithm you can just include the algorithm library and use one function. It is really useful because you don't want to waste your time on a competition to implement basic things like data structures and basic algorithms.

Some tutorials on STL:

Topcoder: Power up C++ with the Standard Template Library: Part 1

YoLinux: C++ STL Tutorial and Books at the end

And the reference site I use: cplusplus.com

Look up some Containers like vector, list, stack, queue and the sort algorithm I talked about.

Some argue that C/C++ are the only reasonable programming languages for competitive programming. I would say if you don't really like C, go for a high level language. It's better to be comfortable with the platform than to be miserable with C. A lot of good competitors use Java, and they say it is not a drawback for them. Look up similar libraries for your choice of language and try using them!

Practice, practice, practice. A lot.

It's one thing that you know how to solve stuff in theory. It's a completely different thing that you can code it, it compiles and runs, gives no errors, you made sure all variables are big enough so they will fit, it is fast enough and doesn't use too much memory.

You need to go sit down and solve exercises for yourself to be able to do it fast and with no errors on stage. When I'm out of practice I spend 10 minutes debugging a binary search because I just can't write it for the first time. It's not good to spend 10 minutes of your competition writing a binary search.

So doing exercises, not just in theory but finishing them with a tested, working code is really great for you.

Here are a few sites that host online competitions regularly:

Topcoder

Codeforces

Google Code Jam

Codechef

What's really great about these sites that you can post your code and they will test and score you for all the previous competitions. Even better, you can see what others have sent in. You can learn a lot from other people's codes. I've heard that some guys on Codeforces spend weeks optimizing their code, so they run faster than anybody else's.

If you check previous competitions on these sites, usually the first few problems in each of them are easy to solve and are aimed for beginners.

I hope this answer helps you get started. :)

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it