Posted in GCJ

GCJ Post #3

Continuing with my said goal ( solving 5 problems per day) This is what I did for the 2 days…

((งง •̀•̀__•́•́))งง


I have planned to put 5 problems of the GCJ types and discuss post and lot picked one for the next 2 weeks until July 10th.
On a more personal note, I have read somewhere that re-reading the  decision made extends the life of the decision!!

So the list of problems that were chosen the last 2 days were:

  1. Laddu
  2. Akhil and colored balls
  3. Kitchen Time Table
  4. Chef And Way
  5. Alternating sub-array prefix
  6. Simple Statistics
  7. Palindrome Substrings
  8. Chef and Coloring
  9. Movie Weekend
  10. Coins and Triangle
So the lot picked problem for today is 

Coins And Triangle

*Well, actually the first lot fell to NO. 8 but it was too easy… So I thought I’ll pick again?*

The problem statement :

Chef belongs to a very rich family which owns many gold mines. Today, he brought N gold coins and decided to form a triangle using these coins. Isn’t it strange?

Chef has an unusual way of forming a triangle using gold coins, which is described as follows:

He puts 1 coin in the 1st row.
then puts 2 coins in the 2nd row.
then puts 3 coins in the 3rd row.

The chef is interested in forming a triangle with maximum possible height using at most N coins. Can you tell him the maximum possible height of the triangle?

Input

The first line of input contains a single integer T denoting the number of test cases.

The first and the only line of each test case contains an integer N denoting the number of gold coins Chef has.

Output

For each test case, output a single line containing an integer corresponding to the maximum possible height of the triangle that Chef can get.

Constraints

1 = T = 100
1 = N = 109

Example

Input
3
3
5
7

Output
2
2
3

Explanation

Test 1: Chef can’t form a triangle with height > 2 as it requires at least 6 gold coins.
Test 2: Chef can’t form a triangle with height > 2 as it requires at least 6 gold coins.
Test 3: Chef can’t form a triangle with height > 3 as it requires at least 10 gold coins.

You are given a number N that represents the number of coins you have and you have to print the maximum possible height H of the triangle which can be made from these coins in such a way that ith row of the triangle contains i coins.

Pretty simple if you know the sum of first N natural numbers?

T = int(input());
for i in range(T):
   n = int(input());
   int h = 1;
   while((h * (h+1) / 2) <= n):
      h ++;
   print (h-1);


But I wasn’t satisfied…the answer was too direct for my liking so I was twisting the code to my liking?


So the code I came up with is this… pretty simple, right? 
t = int(input())
n = [int(input()) for i in range(t)]
for i in n:
height = triangle_height(i)
print(height)

def triangle_height(n_coin):
    height = 1
    coins = 1
    inc = 2
    while coins < n_coin:
        coins += inc
        if coins > n_coin:
            break
        inc += 1
        height += 1
    return height

// Or maybe not that different… oh well whatever…
ʕ ಡ ﹏ ಡ ʔ
Posted in GCJ

GCJ Post #2

So what have I planned for today? Since a problem, a day seems too slow for my 2-week goal I have taken things up a notch…

((งง •̀•̀__•́•́))งง

I have planned to put 5 problems of the GCJ types and discuss post and lot picked one for the next 2 weeks until July 10th.

So the list of problems that were chosen yesterday are:

  1. Rupsa and the Game
  2. Sticks
  3. Entrance Game
  4. One more weird game
  5. Collisions
So the lot picked problem for today is 

One More Wierd Game

*Wow… I sat on this for way too long during my placement training session yesterday *sigh…*

The problem statement :

Leha is playing a very interesting game. The game will be played on a rectangular grid consisting of N rows and M columns. Initially, all the cells of the grid are uncolored.

Leha’s initial score is zero. At each turn, he chooses some cell that is yet not colored, and colors that cell. The score obtained in this step will be a number of neighboring colored cells of the cell that Leha colored in this step. Two cells are neighbors of each other if they share a side between them. The game will end when all the cells are colored. Finally, the total score obtained at the end of the game will sum of score obtained in each turn.

Leha wants to know what maximum score he can get? Can you please help him in finding this out?

Input

The first line contains a single integer T denoting the number of test cases. T test cases follow.

Each of the following T lines contains two space-separated integers N, M denoting the dimensions of the grid.

Output

For each test case, output a single line containing an integer corresponding to the maximal possible score Leha can obtain.

Constraints //For now, I don’t think the constraints bother me as much as the understanding of the question
1 = T = 100
1 = N, M = 1 000

Example

Input:
1
2 2

Output:
4

Explanation

Leha can obtain total score 4 in the following way.

  1. In the first step, he colors the bottom left cell, all the neighboring cells of this cell are uncolored. So, it adds 0 to the total score.
  2. In the second step, he can color upper right cell, it also adds total 0 to the score.
  3. In the third step, he can color top left cell. There are two neighboring cells of this cell, both of which are colored. So, this adds 2 to the score.
  4. In the last step, he can choose the remaining down the right cell. There are two neighboring cells of this cell, both of which are colored. So, this also adds2 to the score.

Leha can’t obtain a score more than 4. Hence 4 is the answer.

There is a n×m dimensional grid. Initially, the cells of the grid are uncoloured. You will colour all the cells of the grid one by one colouring a single cell each time. The score obtained for colouring a cell will be equal to the number of already coloured neighbouring cells of the cell that you are going to colour. Note that two cells are considered to be neighbours of each other, if they share a side with each other.

When I was trying to code this, I ended up playing the game like multiple games and I stumbled upon a pattern to win the game with the maximum possible score.

Fill up alternate boxes in the grid. Then start filling the interior ones. They would have boxes of score 4 in the middle ((m-1)*(n-1) alternate boxes) , boxes with score 3 along the edges and 2 boxes of score 2 if the values of m*n return an even number? (We were doing number systems yesterday so I ended up thinking with respect to the divisibility rules…)

But there were too many holes in this way, and I wasn’t willing to move on … and that was where I got stuck?!?

Apparently after a small discussion about a project proposed by one of my colleagues, I realized this is like the map colouring problem I had learnt in the previous semester under constraint satisfaction problem… Well after when I came home I searched a little about it online… and I came across this formulae (I am sorry I cheated But I really did try… I’ll put a pic of my note in the bottom if I have time)

So the code I came up with is this… pretty simple, right? 

T = int(input())
for i in range(T):
   n, m = [int(s) for s in input().split(” “)]; # read a list of integers, 2 in this case
   print(2*m*n-n-m);

Well, I got to learn a little about the constraint satisfaction problems? So I guess I should know more algorithms concerning graphs … I’ll get to it if I have time during the weekends?

UPDATE:

*I kinda am horrible with cameras so deal with it*
Posted in GCJ

GCJ Post #1

So GCJ for the year 2016 has started, I signed up on Saturday thinking that it was next month but apparently it was yesterday…. Kinda caught me off-guard there!

This is my first try in applying for this and I am making it a point to work on it to qualify to the 2nd round(There are 5 rounds A-E and I just wanna attend round B that is all…). So I will be posting a few questions and how I answered it and how they have answered it and compare them both and find where I can improve myself so that I can achieve this short term goal.

I call this a short term goal cause yesterday (26th, June) was the practice round with 4 two subdivision questions starting at 10am for 3 hours. And the next one is on July 10th. So in this 2 weeks time, I want to solve as many algorithmic problems as possible.

A little something about GCJ problems first so that I can move on to the format of my answer given a problem. The problem is a descriptive scenario where they give you the variables and trust me it was kinda hard to even understand the questions given in the practice round. And it is said that the practice questions are comparatively easier than the real deal… *sigh I have a long way to go I guess?

So the question format is this. A scene is given. A set of inputs are given and the corresponding set of outputs are given and we have to code in the language that we are comfortable in. I was having a hard time choosing the language. I think python will give me the desired results (I’ll most probably switch over to C halfway through?)

┬┴┬┴┤(・_├┬┴┬┴

Anyway, the problem randomly chose for today for me to work on is :

The Lazy Spelling Bee

I was only able to understand the problem statement like after the time expired (meaning I never attempted any of the 4 problems) this was the question.

In the Lazy Spelling Bee, a contestant is given a target word W to spell. The contestant’s answer word A is acceptable if it is the same length as the target word, and the ith letter of A is either the ith, (i-1)th, or (i+1)th letter of W, for all i in the range of the length of A. (The first letter of A must match either the first or second letter of W, since the 0th letter of W doesn’t exist. Similarly, the last letter of A must match either the last or next-to-last letter of W.) Note that the target word itself is always an acceptable answer word.

You are preparing a Lazy Spelling Bee, and you have been asked to determine, for each target word, how many distinct acceptable answer words there are. Since this number may be very large, please output it modulo 1000000007 (109 + 7).

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with a string consisting only of lowercase English letters (a through z).

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the number of distinct acceptable answer words, modulo 109 + 7.

Limits
1 = T = 100.

Small dataset
1 = length of each string = 5.

Large dataset
1 = length of each string = 1000.

Sample
Input 
4
ag
aa
abcde
x

Output 
Case #1: 4
Case #2: 1
Case #3: 108
Case #4: 1

In sample case #1, the acceptable answer words are aa, ag, ga, and gg.
In sample case #2, the only acceptable answer word is aa.

I really feel stupid now that I wasn’t able to understand the question…*sigh Guess I have a long way to go to qualify for the B round?
# input() reads a string with a line of input, 
#stripping the ‘\n’ (newline) at the end.
# This is all you need for most Google Code Jam problems.
t = int(input()) # read a line with a single integer
for i in range(1, t + 1):
     #Insert code logic
This is the format you need to submit in at least that was what I understood from reading the tutorials page at the site (after 10:30 cause I was totally new over here…*sigh)

So what’s the logic? More importantly, what’s the question? I don’t know if I can make it more complicated by explaining it but you never know cause it is me under consideration!!!

Ψ( ̄∀ ̄)Ψ

So from the question: 

There are 3 cases. W of length 1 which has 1 and W of length 2 has 4 iff W’s 2 characters are different from each other else it is again 1. And the others can be split into [ 1,W-2,1 ] and the problem logic can be applied. So a possible solution can be…

T = int(raw_input())
for i in range(T):
   print (“Case #%d:” %(i + 1));
   W = raw_input();

   ans = 1;
   if (len(W)==1):
      print ans;
   elif (len(W)==2):
      if(W[0]==W[1]): print 1;
      else:print 4;
   else:
      W = W[0] + W + W[-1];
      for i in xrange(1, len(W) – 1):
         ans *= len(set(W[i – 1: i + 2]));
         ans %= 1000000007;
      print ans;

At least that is what I have understood from the problem statement. Since I don’t have a way to find if the logic is right or not for all possible inputs… I am gonna think of some other way to prepare for the GCJ, Maybe try out some site like Code Chef or CodeKata or the Euler Project that dropped in the middle cause of my sem exams….

(≖ლ≖๑ )フ

Posted in Random Language Exploited

Random Language Exploited #2

Since I was drowning myself in making the student portal I’ll postpone the lot picking for now and jot down a few things that I learned for fun and move on

(⊃‿⊂)

Okay, So the random language for today is Perl. The language having a camel as its icon?!

Perl is a general-purpose programming language originally developed for text manipulation and now used for a wide range of tasks including system administration, web development, network programming, GUI development, and more.

Perl is a programming language which can be used for a large variety of tasks. A typical simple use of Perl would be for extracting information from a text file and printing out a report or for converting a text file into another form. But Perl provides a large number of tools for quite complicated problems, including systems programming.

Programs written in Perl are called Perl scripts, whereas the term the Perl program refers to the system program named Perl for executing Perl scripts. (What, confused already?)

If you have used shell scripts or awk or sed or similar (Unix) utilities for various purposes, you will find that you can normally use Perl for those and many other purposes, and the code tends to be more compact. And if you haven’t used such utilities but have started thinking you might have a need for them, then perhaps what you really need to learn is Perl instead of all kinds of utilities.

Perl is implemented as an interpreted (not compiled) language. Thus, the execution of a Perl script tends to use more CPU time than a corresponding C program, for instance. On the other hand, computers tend to get faster and faster, and writing something in Perl instead of C tends to save your time.

Windows – Visit StrawberryPerl Site and install the needed version.
Linux MAC – Make sure you don’t install a package of perl that happens to conflict with your basic kernel!?

Assuming that Perl is correctly installed and working on your system, the simplest way to run a Perl program is to type the following: 


perl filename.pl

The filename should be replaced by the name of the program that you are trying to run or execute. If you created a test.pl file while reading the previous section, you can run it like this: perl test.pl

It is very important to place comments into your Perl programs. Comments will enable you to figure out the intent behind the mechanics of your program. For example, it is very easy to understand that your program adds 69 to another value. But, in two years, you may forget how you derived the number 69 in the first place.

Comments are placed inside a program file using the # character. Everything after the # is ignored. For example comment.pl:

# This whole line is ignored.

print(“Perl is easy.\n”); # Here’s a half-line comment.

I don’t know why I went into the basics…

( •́ ⍨ •̀)

Okay moving on… since I kinda don’t have time to go into details… What did I do to consider learning Perl as a programming language?  If I remember correctly Perl was my first scripting language which I learned a year back… WHY? Cause I wanted to know why the camel was it’s icon. 

Guess where I landed… Here It was a site that had a few links to the various species of camels and well the places from where they come from. And since I landed on their site, one thing lead to another and voila I have a backup post for today… Thank you, Mr. Camel !!!
ᕙ (✿⊙へ ⊙〃)

On a more serious note, Perl is like any other scripting language with variables with automatic types, arrays, loops, conditionals, operators bleh-ble-bleh!!

What’s special about Perl?

Not sure if that was true… But I feel that it answers the question asked.

.
.
.

Link to my note – link : you will find a rather incomprehensible note on Perl syntax that I made when I was learning some time back for absolutely no reason whatsoever?
The book I read – Site –  That famous site where I learned almost everything?
Interested in motion pictures – Playlist – YouTube … I have gotten addicted to these things!
perl-tutorial.org – collects up-to-date Perl tutorials and warns about outdated ones
For a beginner these sites are good:
For better clarity and more examples follow this site:
Below tutorial link will give almost everything to begin:
For better learning and understanding write Perl code as much as possible.

Happy Learning! 🙂
Posted in Uncategorized

JS Post 9 – Some randomly selected frameworks of JS !!! (ノ꒪ロ꒪)ノ

The number of web applications being created and used has grown rapidly since the new millennium. And importantly, so has the sheer complexity of them — especially on the front end. No more static pages, no sir!

You have a ton of sections each interacting with each other and the server and yes, it’s as complicated as it sounds and just as hard to pull off. Today, I’d like to talk about a few choice JavaScript frameworks that aim to simplify front-end application development.

Why We Need Frameworks Like These…

If you think jQuery is the answer, you lose a cookie and get an F grade!

Creating responsive, fluid, and maintainable interfaces for web apps isn’t as easy as one would imagine — there is data to be sent back to the server and the results parsed, data stores to be updated, views to be re-rendered and so much else that needs to be done in the background. Desktop developers have it much easier with robust tools and well-defined workflows. Us, poor web devs? We’ve been twiddling DOM elements, creating models by hand and pulling our hair out trying to keep everything synched.

The monstrous rise in the number of web apps being built recently has really made it apparent that we need better tools and frameworks and the devs have responded with a staggering amount of solutions. Today, I’ll go over just a few of these. A couple of these are quite old but I’m certain you can learn a lot from perusing their code base.

Sure, a few of these may be a little old but their code bases have lots of lessons to teach.

Sproutcore

Sproutcore powers a lot of high profile apps including MobileMe amongst others. Sproutcore has a steeper learning curve compared to the other options but makes up for it with developer productivity once he/she has learned the ropes.

This framework boasts a UI framework, the market standard MVC architecture and well-written documentation.

Cappuccino

Cappuccino was created by the 280North team, now owned by Motorola. This framework gained significant coverage with the release of the 280Slides — built completely with Cappuccino.

This framework varies dramatically from the others in that the developers don’t need to understand or work with any of the front end trifecta — HTML, CSS or the DOM. All you need to master is the framework!

Backbone.js

Backbone.js is a JavaScript library with a RESTful JSON interface and is based on the model–view–presenter (MVP) application design paradigm. Backbone is known for being lightweight, as its only hard dependency is on one JavaScript library, Underscore.js, plus jQuery for the use of the full library.

It is designed for developing single-page web applications, and for keeping various parts of web applications (e.g. multiple clients and the server) synchronized. Backbone was created by Jeremy Ashkenas, who is also known for CoffeeScript and Underscore.js.

qooxdoo

qooxdoo is a universal JavaScript framework that enables you to create applications for a wide range of platforms.

With its object-oriented programming model you build rich, interactive applications (RIAs), native-like apps for mobile devices, light-weight traditional web applications or even applications to run outside the browser.

Eyeballs

eyeballs.js is a slim javascript library designed to sit on top of a javascript framework, such as jQuery or Prototype. eyeballs.js can sit on top of an already implemented web app with a well thought out object model.

It can also be used to build standalone javascript apps, backed by HTML5 local storage or something like CouchDB.

Choco

Choco brings the MVC to the client side! A Choco app consists of only one HTML page, all the interactions are managed by Javascript. Your UI only uses HTML and CSS!

Knockout

Knockout is a JavaScript library that helps you to create rich, responsive display and editor user interfaces with a clean underlying data model. Anytime you have sections of UI that update dynamically (e.g., changing depending on the user’s actions or when an external data source changes), KO can help you implement it more simply and maintainable.

Batman.js

batman.js is a full-stack microframework extracted from real use and designed to maximize developer and designer happiness. It favors convention over configuration, template-less views, and high performance by simply not doing very much.

It all adds up to blazingly fast web apps with a great development process; it’s batman.js.

That’s a Wrap!

And we’re done here. The number of options here might border on overdoing things at first glance but each of these are a little different in how they tackle this problem and given a problem, different solutions and choices are always a welcome addition.

Well, anyway that’s all I know on JS I guess… So I’ll wrap it up for today and move on to post on something else…

I’ll get back to you once I am done with the lot picking..

(๑ᵕ⌓ᵕ̤)


Update:

Wiki list of JS frameworks

Posted in Filler Post

Filler Post #5 A website I am working on from scratch ( ̄へ ̄)

I just realized that I haven’t scheduled a post for today and since I am kinda running outta things to post it’s a filler post for today 

(҂⌣̀_⌣́)

So, just putting it out there, My exams are done and I have finally become a final year student (I can’t wait to graduate and go to work that pays my bills!!!). So what had me busy yesterday? Well, I was doing this student portal for my college. This is the first increment.

ヾ(⌐■_■)ノ♪

I had a few examples projects each very different from the other and poorly documented! I wasn’t even able to differentiate between the redundant lines from the useful ones??  So I dropped all of them and started from scratch. I felt so much more better when I had a blank template to start from (Maybe I am not a full on plagiarist like I thought).

What have I used to create the website:

Hostinger: Provides a free sub-domain and other hosting things with good data upload rate and bandwidth.

Bootstrap: The page is responsive as far as I have tested out using F12!

PHP: If you noticed JS is client side and the logic can be seen in the client browser. Now if I ended up using JS to access my DB which is supposedly having sensitive information then well that’s just bad! So I used PHP and it’s usual accompaniment MySQL.

WAMP: Personal server on my desktop for faster results on minor changes.

JavaScript: Well, Bootstraps CSS kinda is more fluid when you use JS with it. Just the basic transitions that I got from places.

SASS: That’s just a super powered CSS code. I used it to beautify my 2-page site using variables and functions instead of  the kinda unchangeable CSS code.

That being said I present to you the first increment of my 2-page site:
What will you find there?

A login page: That asks for your register number and password

RegNo: 311113104001 , 311114205703 , 311115106043 , 311113105303 , 311114114705

(Why these numbers well our reg no has a few inherent details that can be derived from it!! Like the firstRegNo. is a person who entered on 2013 and will leave in 2017 belongs to CSE dept and is a normal student who started college after finishing their schooling or other studies. This kinda cuts down the size of my table on the server. How do I get these info? Well, that’s where PHP comes in! I’ll do that on another day)

Password : licet@123

Well, the logged-in page is a bit informal since well I am a bit informal. I will update it with more formal stuff after giving it to my professors?

Screenshots (just for me so that I can see the difference in the increments)

ԅ(≖‿≖ ;ԅ)

Posted in Uncategorized

JS Post 8 – Some plugins I am planing to exploit Ψ(☆w☆)Ψ

As is my nature, I always tend to pick out random libraries and test it out for almost all the languages I happen to stumble upon. And JS is not an exception!!!

A plug-in is a piece of code written in a standard JavaScript file. These files provide useful jQuery methods which can be used along with jQuery library methods.

I found a few things… actually loads cause there just some amazing JS developers out there!!!
So without further ado, and not in any particular order…

And since the list was getting a bit too long I’ll just add 2 links that kinda sums up everything that I want to convey for today.

And I don’t know about you but I really like how the eyes turned out!!!

(≚ᄌ≚)ƶƵ

// <![CDATA[ var width=50; // width of the eyes in pixels var colour="#90f"; // colour of the eye – bluey green in this case var iris="#000"; // colour of the iris (normally black); var swide=800; var shigh=600; var sleft=sdown=0; var glasses, lefteye, righteye; function addLoadEvent(funky) { var oldonload=window.onload; if (typeof(oldonload)!='function') window.onload=funky; else window.onload=function() { if (oldonload) oldonload(); funky(); } } addLoadEvent(draw_eyes); function draw_eyes() { var i, j, l, m; glasses=document.createElement("div"); i=glasses.style; i.position="fixed"; i.top="50%"; i.left="50%"; i.width="1px"; i.height="1px"; i.overflow="visible"; i.zIndex="100"; document.body.appendChild(glasses); lefteye=document.createElement("div"); righteye=document.createElement("div"); i=lefteye.style; j=righteye.style; i.position=j.position="absolute"; i.width=j.width="1px"; i.height=j.height="1px"; i.overflow=j.overflow="visible"; i.zIndex=j.zIndex="101"; glasses.appendChild(lefteye); glasses.appendChild(righteye); for (m=-1.1; m<2; m+=2.2) for (i=-width; i<width; i++) { l=Math.pow(width*width-i*i, 0.5); j=line(m*width-l, i, 2*l, colour, 0.5); glasses.appendChild(j); } for (i=-width/2; i<width/2; i++) { l=Math.pow(width*width/4-i*i, 0.5); j=line(-1.1*width-l, i, 2*l, iris, 0.8); lefteye.appendChild(j); } for (i=-width/2; iwidth/2.5) { xdiff=xdiff*width/distn/2.5; ydiff=ydiff*width/distn/2.5; } lefteye.style.top=ydiff+”px”; lefteye.style.left=xdiff+”px”; xdiff=x-(1.1*width)-(swide*0.5); ydiff=y-shigh/2; distn=Math.pow(xdiff*xdiff+ydiff*ydiff,0.5); if (distn>width/2.5) { xdiff=xdiff*width/distn/2.5; ydiff=ydiff*width/distn/2.5; } righteye.style.top=ydiff+”px”; righteye.style.left=xdiff+”px”; } document.onscroll=set_scroll; function set_scroll() { if (typeof(self.pageYOffset)==”number”) { sdown=self.pageYOffset; sleft=self.pageXOffset; } else if (document.body.scrollTop || document.body.scrollLeft) { sdown=document.body.scrollTop; sleft=document.body.scrollLeft; } else if (document.documentElement && (document.documentElement.scrollTop || document.documentElement.scrollLeft)) { sleft=document.documentElement.scrollLeft; sdown=document.documentElement.scrollTop; } else { sdown=0; sleft=0; } } window.onresize=set_width; function set_width() { var sw_min=999999; var sh_min=999999; if (document.documentElement && document.documentElement.clientWidth) { if (document.documentElement.clientWidth>0) sw_min=document.documentElement.clientWidth; if (document.documentElement.clientHeight>0) sh_min=document.documentElement.clientHeight; } if (typeof(self.innerWidth)!=”undefined” && self.innerWidth) { if (self.innerWidth>0 && self.innerWidth0 && self.innerHeight0 && document.body.clientWidth0 && document.body.clientHeight