Monday, 16 June 2014

The June long challenge ended today been able to solve 4 questions the fourth one digjumps just being a modification of B.F.S. algorithm special thanks to my freind Ansh Khanna for motivating me to do the 4th problem and update this blog :) Ansh if you are reading this a big thanks man . Now talking about the readability of the problem it was not very good i thought i-1(Si-1) meant the the difference of the index and the value of the sequence at i-1 index. So now thinking of framing a similar question for codechef :P not in near future though :) anyways here is the problem link
 QUESTION 4 JUNELONG DIGITJUMPS
my solution
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <queue>
#include <climits>
 
using namespace std;
#define FOR(i,a) for(int i = 0;i < a;i++)
#define REP(i,a,b) for(int i = a;i < b;i++)
#define vi vector<int>
 
int main()
{
int arr[100001],len;/*the dp matrix storing the min moves taken to reach the element and the length of input string*/
char str[100001];/*the string*/
int allnum[10][100001];/*all the numbers position stored from 0-9*/
int allcnt[10];/*counts of all the numbers*/
bool truth[10];/*checks whethers the numbers encountered before or not*/
memset(arr,-1,100001*sizeof(int));/*intitialisation of the dp matrix*/
memset(str,'\0',100001*sizeof(char));/*sting init*/
memset(allcnt,0,10*sizeof(int));/*zero elements initially*/
memset(truth,false,10*sizeof(bool));
std::queue<int> q;/*the queue for storing positions*/
scanf("%s",str);
len=strlen(str);
for(int i=0;i<len;i++)
{
allnum[str[i]-'0'][allcnt[str[i]-'0']]=i;/*storing in the 2D array allnum the positions of numbers*/
allcnt[str[i]-'0']++;/*increase the size*/
}
arr[0]=0;/*no moves required to reach the index 0*/
q.push(0);/*beginning insert the zero*/
while(!q.empty())
{
if(!truth[str[q.front()]-'0'])/*if all the elements of the front type are not pushed*/
{
for(int i=0;i<allcnt[str[q.front()]-'0'];i++)/*i< allcount or total size of the particular element of the front type*/
{if(allnum[str[q.front()]-'0'][i]!=0)
q.push(allnum[str[q.front()]-'0'][i]);/*push the positions of elements in the queue*/

if(arr[q.front()]+1 < arr[allnum[str[q.front()]-'0'][i]] &&arr[allnum[str[q.front()]-'0'][i]]!=-1 )
{
arr[allnum[str[q.front()]-'0'][i]]=arr[q.front()]+1;/*transferring to the dp arr the lowest possible reach*/
}
if(arr[allnum[str[q.front()]-'0'][i]]==-1)
{
arr[allnum[str[q.front()]-'0'][i]]=arr[q.front()]+1;
}

}
truth[str[q.front()]-'0']=true;/*not repeating it next time*/
}
if(q.front()-1>=0)
{
if(arr[q.front()-1]>arr[q.front()]+1&&arr[q.front()-1]!=-1)
{
arr[q.front()-1]=arr[q.front()]+1;
q.push(q.front()-1);
}
if(arr[q.front()-1]==-1)
{
arr[q.front()-1]=arr[q.front()]+1;
q.push(q.front()-1);
}
}

if (q.front()+1<len)
{
if(arr[q.front()+1]>arr[q.front()]+1&&arr[q.front()+1]!=-1)
{
arr[q.front()+1]=arr[q.front()]+1;
q.push(q.front()+1);
}
if(arr[q.front()+1]==-1)
{
arr[q.front()+1]=arr[q.front()]+1;0
q.push(q.front()+1);
}
}
q.pop();
}
printf("%d\n",arr[len-1]);
return 0;
}
by the way it got AC in one go with a runtime of 0.00s memory of 7MB B-) but i have also seen far easier approaches from other people's code and editorials will try to learn them up as well and if possible write them here.

Saturday, 14 June 2014

Zeptocode rush codeforces didn't go according to plan , the problems were quite good . Thinking that i have to renovate my approach to competitions , whenever I am faced with a problem i tend to think about the implementation rather than the problem in depth and land up with most brute force solutions which either get hacked or fail systests or exceed the time limit, got to understand the fact that it's not about coding it's about problem solving . Will have to try harder again, also i just might be losing my steam but got to build the passion again . Also I gave the SRM 624  easy problems could solve 2/3  but still grey although rating has improved hoping to become green in the next one . (just hoping and practicing what else can i do) :) 

Monday, 2 June 2014

Finally after so many months took up U.S.A.C.O problems opening with the greedy algorithm now. and Yes did I discuss the last problem of brute force name_that_number. Problem description:-
  Name That Number
Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."
Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):
          2: A,B,C     5: J,K,L    8: T,U,V
          3: D,E,F     6: M,N,O    9: W,X,Y
          4: G,H,I     7: P,R,S
Acceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).
For instance, the brand number 4734 produces all the following names:
GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI
As it happens, the only one of these 81 names that is in the list of valid names is "GREG".
Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.

PROGRAM NAME: namenum

INPUT FORMAT

A single line with a number from 1 through 12 digits in length.

SAMPLE INPUT (file namenum.in)

4734

OUTPUT FORMAT

A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.

SAMPLE OUTPUT (file namenum.out)

GREG
source:-http://cerberus.delos.com:791/usacogate

approach description :- make a structure having name and number
open the dictionary and input all the words which are valid and store them in the structure store the number corresponding to every name and and search the given 
input number if there is no matching case output "NONE" else output the name  

here is the code :-
/*
ID: gkeesh7
PROG: namenum
LANG: C++
*/
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

using namespace std;
#define FOR(i,a)    for(int i = 0;i < a;i++)
#define REP(i,a,b)  for(int i = a;i < b;i++)
#define vi vector<int>

struct namenums
{
 char name[20];
 long long int num;
} n[5000];

int main()
{
 long long int nquery,cp=0,len,t,mcount=0;
 char temp[20];
 freopen("namenum.in","r",stdin);
 freopen("namenum.out","w",stdout);
 scanf("%lld",&nquery);
 fclose(stdin);
 freopen("dict.txt","r",stdin);
 while(!feof(stdin))
 {
  scanf("%s",n[cp].name);
  cp++;
 }
 fclose(stdin);
 FOR(j,cp)
 {
  strcpy(temp,n[j].name);
  t=0;
  len=strlen(temp);
  FOR(i,len)
  {
   t=t*10;
   if(temp[i]=='A'||temp[i]=='B'||temp[i]=='C')
   {
    t+=2;
   }
   else if(temp[i]=='D'||temp[i]=='E'||temp[i]=='F')
   {
    t+=3;
   }
   else if(temp[i]=='G'||temp[i]=='H'||temp[i]=='I')
   {
    t+=4;
   }
   else if(temp[i]=='J'||temp[i]=='K'||temp[i]=='L')
   {
    t+=5;
   }
   else if(temp[i]=='M'||temp[i]=='N'||temp[i]=='O')
   {
    t+=6;
   }
   else if(temp[i]=='P'||temp[i]=='R'||temp[i]=='S')
   {
    t+=7;
   }
   else if(temp[i]=='T'||temp[i]=='U'||temp[i]=='V')
   {
    t+=8;
   }
   else if(temp[i]=='W'||temp[i]=='X'||temp[i]=='Y')
   {
    t+=9;
   }
  }
  n[j].num=t;
 }
 FOR(i,cp)
 {
  if(n[i].num==nquery)
  {
   printf("%s\n",n[i].name);
   mcount++;
  }
 }
 if(mcount==0)
 {
  printf("NONE\n");
 }
 return 0;
}
//not to mention it worked the first time :)