I am also sharing this code on github in case anyone needs any explaination, please feel free to send me a message at ping@qasimzeeshan.com
Sunday, December 28, 2014
CodeEval experience
I am also sharing this code on github in case anyone needs any explaination, please feel free to send me a message at ping@qasimzeeshan.com
Qasim Zeeshan's new website
Wednesday, April 18, 2012
My approach to TCO 2012 Marathon competition
My approach was pretty simple and concise. My solution extracts the strips from the extreme sides(top, bottom, left right) of the board and insert them to the strips with maximum whites(usually in the maximal component) those are not connected to their neighbouring strips. If they are connected to their neighbouring strips, no need to disturb them.
After completing each line with whites, I used to check if all whites are connected using floodfill. Following are my scores (seed 1 to seed 10)and output images:
1) 83.25
2) 87.85609934258582
3) 81.49243918474689
4) 81.43961927424152
5) 67.22552731206058
6) 82.146399523904
7) 81.375
8) 81.77083333333334
9) 87.23072562358276
Complete standings can be found on http://community.topcoder.com/longcontest/?module=ViewStandings&rd=15099
Tuesday, April 26, 2011
Creating Drupal CCK field module.
- Several separate fields: Create a multiple-valued field for the image, another for the caption, and another for the taxonomy term, and tell the people editing content on the site to try to keep them synchronized. This is not really workable in general -- users would need to scroll up and down the content entry screen to do their data entry, and inevitably someone will make a mistake and you'll have a caption or term associated with the wrong image. Also, for this specific case, Content Taxonomy as a multiple-valued field just gives you one multi-select list, so there is no way to choose a given taxonomy term more than once, or indicate the order (term 1 goes with image 1, etc.).
- Content sub-type: Create a second content type "Image Caption Term" to hold an image and its associated data. Then add a multiple "Node Reference" field to your original content type, which will associate your page with its images. This can be made to work, but in practice the editing is at best clumsy. (The Modal Nodereferencemodule may help in making the editing less clumsy.) Also, you'll end up with a lot of these little "Image Caption Term" items cluttering up your content management screens, which will confuse novice users.
- Content Multigroup module: Try out an experimental "Content Multigroup" module that is supposed to let you group multiple CCK fields together. As of this writing (April 2010), this module is not stable (not even released as an "alpha" version), and last time I tried it (October 2008), it didn't work at all with image fields. It may have improved since then.
- Flexifield Module: This may be working better now than the last time I tested it (October 2008).
- Custom CCK field: Create your own custom CCK field module that contains the desired grouping of information. Doing this is not very difficult, works very well, and is the subject of this article.
A compound image, caption, and taxonomy field: Allows a user to upload an image, provide "alt" and "title" text for the image, enter a caption (arbitrary HTML text), and choose one or more taxonomy terms. You can click the image to the left to see what it looks like in action.
- A simpler person field, with fields for displayed name, job title, phone number, and email address, which you could use if you didn't want to have full nodes for each "person". It also provides an illustration of how to make a compound field that contains just simple text fields.
- Introduction and Motivation (above)
- Getting Started
- Defining the Field
- Defining the Widget
- Defining the Formatter and Theming
- Final Details
- Downloads, Background, and References
Getting Started
- The first module we are creating implements a compound CCK field for an image, caption, and taxonomy term. So, I have chosen to call the CCK field "Image Caption Taxonomy", with machine-readable name "img_cap_tax". To distinguish the name of the CCK field from the name of the module, I have chosen to call the module "Image Caption Taxonomy Field", and to use the machine-readable name "img_cap_tax_fld" for the module; I'll refer to this machine-readable name as "(module)".
- The second module is for a person field, so the CCK field will be called "Person", with machine readable name "person". The module will be "Person Field", with machine readable name "person_fld".
- Because this module implements a CCK field, we can rely on the CCK module to take care of all the database tables for us. For that reason, we don't need a .install file for this module to define the database schema.
- We do need to define some module dependencies in the .info file, as we will see below. Check the completed .info file in the module download for a list.
- It is possible to define multiple CCK fields in a single module. However, having done it once, I really wouldn't recommend it -- it makes the module file confusing, and less "modular" (i.e. someone might only need one of your fields, but have to load the entire module with several fields in order to get that functionality on their site).
Defining the Field
CCK hook_field_info()
function img_cap_tax_fld_field_info() {
return array(
'img_cap_tax' => array(
'label' => t('Image Caption Taxonomy'),
'description' => t('Stores an image file, text for alt and title tags, a caption, and a taxonomy term'),
)
);
}
Core hook_install(), hook_uninstall(), hook_enable(), hook_disable()
function img_cap_tax_fld_install() {
content_notify('install', 'img_cap_tax');
}
- Make our module dependent on the CCK module (whose machine-readable name is "content") -- that dependency goes into the .info file.
- Verify which file the content_notify() function is defined in -- if it had been in an include file rather than the main .module file, we would have needed to put an include directive in the hook_init() implementation in our module.
CCK hook_field_settings()
function img_cap_tax_fld_field_settings( $op, $field ) {
switch( $op ) {
case 'form':
return img_cap_tax_fld_field_settings_form( $field );
case 'save':
return img_cap_tax_fld_field_settings_save( $field );
default:
return filefield_field_settings( $op, $field );
}
}
function person_fld_field_settings($op, $field) {
switch ($op) {
case 'database columns':
$columns['displayed_name'] = array('type' => 'varchar', 'length' => 255, 'not null' => FALSE, 'sortable' => TRUE, 'default' => '');
$columns['job_title'] = array('type' => 'varchar', 'length' => 255, 'not null' => FALSE, 'sortable' => TRUE, 'default' => '');
$columns['phone'] = array('type' => 'varchar', 'length' => 255, 'not null' => FALSE, 'sortable' => FALSE, 'default' => '');
$columns['email'] = array('type' => 'varchar', 'length' => 255, 'not null' => FALSE, 'sortable' => FALSE, 'default' => '');
return $columns;
}
}
filefield_field_settings() Operations Functions (image example only)
function img_cap_tax_fld_field_settings_form( $field ) {
$form1 = filefield_field_settings( 'form', $field );
$form2 = content_taxonomy_field_settings( 'form', $field );
$form2['save_term_node']['#type'] = 'hidden';
$form2['taxonomy_group'] = array(
'#type' => 'fieldset',
'#title' => 'Taxonomy',
'#collapsible' => 0,
);
$form2['taxonomy_group']['vid'] = $form2['vid'];
unset( $form2['vid'] );
$form2['taxonomy_group']['allow_multiple'] = array(
'#type' => 'checkbox',
'#title' => t('Allow multiple taxonomy terms'),
'#default_value' => is_numeric($field['allow_multiple']) ? $field['allow_multiple'] : 0,
'#description' => t('If this option is checked, the user can select multiple taxonomy terms for each image; otherwise, at most one.'),
);
$form2['taxonomy_group']['required_term'] = array(
'#type' => 'checkbox',
'#title' => t('Taxonomy required'),
'#default_value' => is_numeric($field['required_term']) ? $field['required_term'] : 0,
'#description' => t('If this option is checked, the user must select at least one taxonomy term for each image; otherwise, it is optional.'),
);
$form2['hierarchical_vocabulary']['#weight'] = 100;
$form3 = array( 'text_processing' => array(
'#type' => 'radios',
'#title' => t('Text processing for Caption'),
'#default_value' => is_numeric($field['text_processing']) ? $field['text_processing'] : 0,
'#options' => array( 0 => t('Plain text'), 1 => t('Filtered text (user selects input format)')),
));
return $form1 + $form3 + $form2;
}
function img_cap_tax_fld_field_settings_save( $field ) {
$flds1 = filefield_field_settings( 'save', $field );
$flds2 = content_taxonomy_field_settings( 'save', $field );
$flds2[] = 'allow_multiple';
$flds2[] = 'required_term';
$flds3 = array( 'text_processing' );
return array_merge( $flds1, $flds2, $flds3 );
}
- Whether or not the content has at least one image attached to it. This should come from the FileField module.
- Whether a particular taxonomy term is present or not.
CCK hook_field()
function img_cap_tax_fld_field($op, $node, $field, &$items, $teaser, $page) {
if( $op == 'sanitize' ) {
img_cap_tax_fld_field_sanitize( $node, $field, $items, $teaser, $page );
}
return filefield_field( $op, $node, $field, $items, $teaser, $page );
}
function img_cap_tax_fld_field_sanitize($node, $field, &$items, $teaser, $page) {
$isplain = empty( $field['text_processing'] );
$check_access = is_null( $node ) ||
( isset($node->build_mode) && $node->build_mode == NODE_BUILD_PREVIEW );
foreach( $items as $delta => $item ) {
$dat = $item['data'];
if( !is_array( $dat )) {
$dat = unserialize( $dat );
}
$text = isset( $dat['caption'] ) ? $dat['caption'] : '';
if( $isplain ) {
$text = check_plain( $text );
} else {
$text = check_markup( $text, $item['format'], $check_access );
}
$items[$delta]['safe_caption'] = $text;
}
}
function person_fld_field($op, &$node, $field, &$items, $teaser, $page) {
switch ($op) {
case 'validate':
if (is_array($items)) {
foreach ($items as $delta => $item) {
if ($item['email'] != '' && !valid_email_address(trim($item['email']))) {
form_set_error($field['field_name'],t('"%mail" is not a valid email address',array('%mail' => $item['email'])));
}
}
}
break;
case 'sanitize':
foreach ($items as $delta => $item) {
foreach ( $item as $col => $dat ) {
$items[$delta]['safe_' . $col ] = check_plain($item[ $col ]);
}
}
break;
}
}
CCK hook_content_is_empty(), hook_default_value()
function img_cap_tax_fld_content_is_empty( $item, $field ) {
return filefield_content_is_empty( $item, $field );
}
function person_fld_content_is_empty($item, $field) {
if (empty($item['displayed_name'])) {
return TRUE;
}
return FALSE;
}
function img_cap_tax_fld_default_value(&$form, &$form_state, $field, $delta) {
return filefield_default_value($form, $form_state, $field, $delta);
}
Defining the Widget
CCK hook_widget_info()
function img_cap_tax_fld_widget_info() {
return array(
'img_cap_tax_sel_widget' => array(
'label' => t('Image, Caption, Taxonomy Select'),
'field types' => array('img_cap_tax'),
'multiple values' => CONTENT_HANDLE_CORE,
'callbacks' => array('default value' => CONTENT_CALLBACK_CUSTOM),
'description' => t('An edit widget for Image Caption Taxonomy fields that allows upload/preview of the image, and chooses taxonomy terms from a drop-down select list.' ),
),
);
}
function person_fld_widget_info() {
return array(
'person_entry' => array(
'label' => t('Text fields'),
'field types' => array('person'),
'multiple values' => CONTENT_HANDLE_CORE,
'callbacks' => array(
'default value' => CONTENT_CALLBACK_DEFAULT,
),
),
);
}
FAPI hook_elements()
function img_cap_tax_fld_elements() {
$imgel = imagefield_elements();
$elements = array( 'img_cap_tax_sel_widget' => $imgel[ 'imagefield_widget' ]);
$elements['img_cap_tax_sel_widget']['#process'][] = 'img_cap_tax_fld_widget_process';
$elements['img_cap_tax_sel_widget']['#element_validate']= array('img_cap_tax_fld_widget_validate');
return $elements;
}
function person_fld_elements() {
$elements = array( 'person_entry' =>
array(
'#input' => TRUE,
'#process' => array( 'person_fld_person_entry_process' ),
),
);
return $elements;
}
Process and Validate Callbacks for Widget Form
function img_cap_tax_sel_widget_process($element, $edit, &$form_state, $form) {
$defaults = $element['#value']['data'];
if( !is_array( $defaults )) {
$defaults = unserialize( $defaults );
}
$field = content_fields($element['#field_name'], $element['#type_name']);
$element['data']['caption'] = array(
'#title' => t( 'Caption' ),
'#type' => 'textarea',
'#rows' => $field['widget']['rows'],
'#cols' => $field['widget']['cols'],
'#default_value' => $defaults['caption'],
'#weight' => 4,
);
if (!empty($field['text_processing'])) {
$filt = isset( $defaults['format'] ) ? $defaults['format'] : FILTER_FORMAT_DEFAULT;
$par = $element['#parents'];
$par[] = 'data';
$par[] = 'format';
$element['data']['format'] = filter_form( $filt, 1, $par );
$element['data']['format']['#weight'] = 5;
}
$mult = $field['allow_multiple'];
$req = $field['required_term'];
$opts = content_taxonomy_allowed_values( $field );
if( !$req && !$mult ) {
$none = theme( 'content_taxonomy_options_widgets_none', $field );
$opts = array( '' => $none ) + $opts;
}
$element['data']['value'] = array(
'#title' => t( 'Taxonomy Terms' ),
'#type' => 'select',
'#default_value' => $defaults['value'],
'#options' => $opts,
'#weight' => 6,
);
if( $mult ) {
$element['data']['value']['#multiple'] = TRUE;
}
return $element;
}
function person_fld_person_entry_process($element, $edit, &$form_state, $form) {
$defaults = $element['#value'];
$field = content_fields($element['#field_name'], $element['#type_name']);
$element['displayed_name'] = array(
'#title' => t( 'Name' ),
'#type' => 'textfield',
'#default_value' => $defaults['displayed_name'],
'#weight' => 2,
);
$element['job_title'] = array(
'#title' => t( 'Job Title' ),
'#type' => 'textfield',
'#default_value' => $defaults['job_title'],
'#weight' => 3,
);
$element['phone'] = array(
'#title' => t( 'Phone' ),
'#type' => 'textfield',
'#default_value' => $defaults['phone'],
'#weight' => 4,
);
$element['email'] = array(
'#title' => t( 'Email' ),
'#type' => 'textfield',
'#default_value' => $defaults['email'],
'#weight' => 5,
);
return $element;
}
function img_cap_tax_fld_widget_validate(&$element, &$form_state) {
if (empty($element['fid']['#value'])) {
return;
}
$field = content_fields($element['#field_name'], $element['#type_name']);
$ftitle = $field['widget']['label'];
if ( !( $file = field_file_load($element['fid']['#value']))) {
form_error($element, t('The file referenced by the %field field does not exist.', array('%field' => $ftitle )));
}
}
Widget theme function
function theme_img_cap_tax_sel_widget(&$element) {
return theme('form_element', $element, $element['#children']);
}
function theme_person_entry($element) {
return $element['#children'];
}
.filefield-element .widget-edit, .filefield-element .widget-preview {
float: none;
}
CCK hook_widget()
- Our module contains a file called (module)_widget.inc (the filefield_widget() function will load it).
- The $items['delta'] array has been set up with an array of the default values for the text fields in our compound field, before filefield_widget() is called.
function img_cap_tax_fld_widget(&$form, &$form_state, $field, $items, $delta = 0) {
if (empty($items[$delta])) {
$items[$delta] = array('alt' => '', 'title' => '', 'caption' => '', 'value' => 0);
}
$element = filefield_widget($form, $form_state, $field, $items, $delta);
$element['#upload_validators'] += imagefield_widget_upload_validators($field);
return $element;
}
function person_fld_widget(&$form, &$form_state, $field, $items, $delta = 0) {
$element = array(
'#type' => $field['widget']['type'],
'#default_value' => isset($items[$delta]) ? $items[$delta] : '',
);
return $element;
}
switch( $field['widget']['type'] ) {
case 'first_widget_machine_name':
(code for this widget)
break;
case 'second_widget_machine_name':
(code for this widget)
break;
}
CCK hook_widget_settings() (image field only)
function img_cap_tax_fld_widget_settings( $op, $widget ) {
switch ($op) {
case 'form':
return img_cap_tax_fld_widget_settings_form($widget);
case 'validate':
return imagefield_widget_settings_validate($widget);
case 'save':
return img_cap_tax_fld_widget_settings_save($widget);
}
}
filefield_widget_settings() callbacks (image field only)
function img_cap_tax_fld_widget_settings_form( $widget ) {
$form = imagefield_widget_settings_form( $widget );
$form['custom_alt'] = $form['alt_settings']['custom_alt'];
$form['custom_alt']['#type'] = 'hidden';
$form['custom_alt']['#value'] = 1;
$form['alt'] = $form['alt_settings']['alt'];
$form['alt']['#type'] = 'hidden';
$form['alt']['#value'] = '';
unset( $form['alt']['#suffix'] );
unset( $form['alt_settings'] );
$form['custom_title'] = $form['title_settings']['custom_title'];
$form['custom_title']['#type'] = 'hidden';
$form['custom_title']['#value'] = 1;
$form['title'] = $form['title_settings']['title'];
$form['title']['#type'] = 'hidden';
$form['title']['#value'] = '';
unset( $form['title']['#suffix'] );
unset( $form['title_settings'] );
$rows = (isset($widget['rows']) && is_numeric($widget['rows'])) ? $widget['rows'] : 5;
$form['rows'] = array(
'#type' => 'textfield',
'#title' => t('Number of rows in caption field'),
'#default_value' => $rows,
'#element_validate' => array('_text_widget_settings_row_validate'),
'#required' => TRUE,
'#weight' => 8,
);
$cols = (isset($widget['cols']) && is_numeric($widget['cols'])) ? $widget['cols'] : 40;
$form['cols'] = array(
'#type' => 'textfield',
'#title' => t('Number of columns in caption field'),
'#default_value' => $cols,
'#element_validate' => array('_text_widget_settings_row_validate'),
'#required' => TRUE,
'#weight' => 9,
);
$form2 = content_taxonomy_options_widget_settings( 'form', $widget );
$form2['settings']['#title'] = t( 'Settings for Taxonomy' );
$form = $form + $form2;
return $form;
}
function img_cap_tax_fld_widget_settings_save( $widget ) {
$arr = imagefield_widget_settings_save( $widget );
$arr[] = 'rows';
$arr[] = 'cols';
$arr2 = content_taxonomy_options_widget_settings( 'save', $widget );
$arr2[] = 'allow_multiple';
$arr2[] = 'required_term';
return array_merge( $arr, $arr2 );
}Defining the Formatter and Theming
CCK hook_field_formatter_info()
function img_cap_tax_fld_field_formatter_info() {
return array(
'default' => array(
'label' => t( 'Image with Caption and Taxonomy Terms' ),
'field types' => array( 'img_cap_tax' ),
),
);
}
Core hook_theme()
function img_cap_tax_fld_theme() {
return array(
'img_cap_tax_sel_widget' => array(
'arguments' => array('element' => NULL),
),
'img_cap_tax_fld_formatter_default' => array(
'arguments' => array('element' => NULL),
),
);
}
Theme Functions
function theme_img_cap_tax_fld_formatter_default( $element = NULL ) {
if( empty( $element['#item'] )) {
return '';
}
$img = theme( 'imagefield_formatter_image_plain', $element );
$cap = $element['#item']['safe_caption'];
$tax = '';
$sep = '';
$val = $element['#item']['data']['value'];
if( !is_array( $val )) {
$val = array( $val );
}
foreach( $val as $tid ) {
$term = taxonomy_get_term( $tid );
$tax .= $sep . check_plain( $term->name );
$sep = ', ';
}
return '' .
'
' . $img . '' .
'
' . $cap . '' .
'
' . $tax . '' .
'';
}
function theme_person_fld_formatter_default($element = NULL) {
if(empty($element['#item'])) {
return '';
}
$stuff = $element['#item'];
$flds = array('displayed_name', 'job_title', 'phone');
$ret = '';
$sep = '';
foreach($flds as $fld) {
if(!empty($stuff['safe_' . $fld ])) {
$ret .= $sep . '' . $stuff['safe_' . $fld ] . '';
$sep = "
\n";
}
}
if(!empty($stuff['safe_email' ])) {
$ret .= $sep . '' . $stuff['safe_email' ] . "";
}
$ret .= '';
return $ret;
}Final Details
Tuesday, March 8, 2011
FB.login() called before calling FB.init(). Drupal
I got it fixed in this way today.
Friday, December 31, 2010
Sunday, May 23, 2010
Code Jam Round 1
Round 1 consisted of 3 sub rounds of 2hr 30min duration each and top 1000 finishers from each round were to qualify to Round 2.
Round 1A was at 6:00 AM, Saturday, May 22, 2010. I was in my friend’s home on that day. I woke up early with great enthusiasm after a 4 hours nap and started the computer. The development environment is not set on that system. “Its ok, no problem, lets setup the development environment”. It penalized me about 15 minutes. Started solving the first problem, applied brute force and it was accepted but I took 1hr 15min to solve it. Now I was just looking for one more solution for small input for a finish under top 1000. Started the second problem, solved it, submitted it and “Aah! INCORRECT RESULT”. I made another attempt and same result again. Round over and I ranked about 1360 with 23 points. After system tests, I managed to finish at 1269. I was pretty happy with my performance as I was very close for getting through. The person at 1000th place was also with the same score but with less time penalty i.e. 51min 40sec.
Round 1B was at 9:00 PM on the same day. O boy, power cutoff from 8:00 PM – 10:00 PM, but I will participate from 10:00 PM onwards. At 10:00 PM, I entered in to the contest. 1 hour is already spent in load shedding so I have to be fast and accurate. I started Problem A, solved it in almost 43 minutes and it got accepted. Problem B was also easy, just a bubble sort algorithm. I got it accepted in almost 35 minutes with one wrong try. I finished at 56 points with total time 2hr 26min 06sec (1hr 26min 06sec of contest + 1 hr of load shedding). Ranked 1410 and after System Tests 1352. The interesting part is that the person ranked 1000 spent 1hr 26min 15sec so I am qualified if I subtract 1 hour of load shedding. :-)
Round 1C was at 2:00 PM, Sunday, May 23, 2010. Load shedding from 2:00 - 4:00. No chance. So this is how I eliminated :-(.
Lessons Learned:
1. Most importantly, I need more practice as in Round 1A, I got complete time but was just making a stupid mistake in 2nd problem.
2. Make sure the development environment is setup and working before contest.
3. Take at least 8 hours sleep before any programming contest.
4. If above rules are being obeyed, no one can stop you from being qualified to Round 2 even a power cut off.
Country Statistics:
Click here to see the results of all countries.
Tuesday, May 4, 2010
Clean Code by Rober C. Martin (Uncle Bob)
Thursday, April 15, 2010
Implementation of Full Text Search using MySQL database
“Search? Aha…lets use wildcard for now”.
Sunday, December 13, 2009
More than 31 Style elements cause IE crash
"Oh IE I love, I can write an HTML file that can crash you"
After figuring out the JavaScript of that twitter widget and some Google work, I got to know that the basic cause of IE crash is not the Twitter widget. The basic cause was that twitter widget adds a "style" HTML element dynamically, that causes crash for IE.
I just squeeze all those 31 imports in one "<style> </style>" and hurray!!!! the problem is resolved.
Reference: Microsoft Support about 31 style tags
Thursday, October 29, 2009
Finding 100 factorial
Write a program that takes input between 1 and 100 and finds its factorial.
Solution
Often students find this problem as assignment or algorithm exercise. Some of them even get fed up and skip this problem because you have to make calculations on large numbers. We all know that C++ 32 bit unsigned integer can hold data up to 4294967295 and long long i.e. 64 bit integer can handle at max 264 - 1 = 18446744073709551615. What do you think what is the maximum value whose factorial can be saved in 64 bit int. You can't even store 25's factorial in it as 25! = 15511210043330985984000000 :)
In this post, I will explain how easy it is to actually implement this algorithm. In the second part of this post, we will optimize our algorithm and will reduce some calculations.
Let us start!
First thing we have to keep in mind that we actually need a function that has the capability to multiply fairly large numbers.
We multiply two numbers usually by multiplying each digit of first number with each digit of 2nd number. For example if I have to multiply 123 to 1234:
- I will actually find 3 x 1234 = 3702, 2 x 1234 = 2468 and 1 x 1234 = 1234.
- I also have to add some zeros on the right side as I move from right to left.
- And then I will add all these values i.e. 3702 + 24680 + 123400 = 151782.
Voila!!! you noted something, we have to implement another function that can add two large numbers. Don't worry, it is good that we have found it initially. Let us assume that we already have a function that can add two numbers 'string add(string str1, string str2)' Now the function mul is quite simple to write that will multiply two very large numbers.
string mul(string str1, string str2)
{
string ans;
for(int i = str1.size()-1; i>=0; i--)
{
string sum;
int carry = 0;
//Step 1. above
for(int j = str2.size()-1; j >=0; j--)
{
//multiply two digits and add carry
int k = ((str1[i]-'0')*(str2[j]-'0') + carry);
sum = (char)((k % 10) + '0') + sum;
carry = (k/10);
}
if(carry > 0)
{
sum = (char)(carry+'0') + sum;
}
//Step 2. above
for(int j = 0; j < str1.size() - 1 - i; j++)
{
sum+="0";
}
//Step 3. above
ans = add(ans, sum);
}
return ans;
}
And here we go with the add function, I think it is pretty simple to understand
string add(string str1, string str2)
{
int n1 = str1.size(), n2 = str2.size();
for(int i = 0; i < n1 - n2; i++) //Make 134 as 00134 if 2nd number is 12345
str2 = "0" + str2;
for(int i = 0; i < n2 - n1; i++)
str1 = "0" + str1;
string ans;
int carry = 0;
for(int i = str1.size() - 1; i >= 0; i--)
{
ans = (char)((str1[i] - '0' + str2[i] - '0' + carry) % 10 + '0') + ans;
carry = (str1[i] - '0' + str2[i] - '0' + carry)/10;
}
if(carry > 0)
ans = (char)(carry + '0') + ans;
return ans;
}
Now what is more difficult for you. Here comes the Factorial function:
int N = 25; //We need 25!
string ans = 1;
for(j = 1; j <= N; j++)
{
stringstream ss;
ss << j;
ans = mul(ss.str(),ans);
}
Optimization
Just check one important thing, even we have to multiply small numbers. we have to make large calculations.
For example, if I want to multiply 10000 to 9999. I have to make 20 calculations but it is possible in just 1 calculation and the result can also be saved in an integer so we can optimize our algorithm in this way.
We will not call mul( ) function, until and unless it exceeds the limit of an integer that is '2147483647' and then multiply it with the next number.
25! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22 x 23 x 24 x 25
Now we can find product upto 12 i.e. '479001600' and from 13 to 19 i.e. '253955520' and then call mul( ) function on these two strings.I am sure, it will save a lot of calculations.
Monday, October 12, 2009
Lecture about dynamic programming (Urdu)
While searching educational stuff on youtube, I found these videos those I would like to share with you.
and the next part is:
Saturday, September 26, 2009
Topcoder | SRM 449 experience
I spent some time on 250 ptr and just didn't understand that if I scale its lower parts to upward, it will become a bigger triangle, and I just have to find the lengths of base and perpendicular of that bigger triangle. The formula was sqrt(2)*(max(finish) - min(start)). This is the solution.
Just no idea clicked and I decided to open 500 ptr because I was pretty sure that it would have been a simpler one. It was simple(only problem statement :) ), as you might have seen but wasn't easy. Again it was a mathematical trick, because brute force solution will surely leads to time out. This was the logic behind it. (The following statements are copied from editorial)
-> If we see, the greatest odd divisor that divides N is N if N is odd or if N is even the greatest odd divisor of N is F(N/2).
-> For (1,N) if N is odd we get 1 + 3 + 5 + ...N + F(2) + F(4)+....F(N-1). The greatest even N is F((N-1)/2).
-> That means the sum F(2) + F(4)+...F(N-1) = F(1) + F(2) + F(3) + F((N-1)/2). Now this is our original problem with N as (N-1)/2.
-> In case of N as even our problem is split into 1+3+5+ ....N-1 and F(2)+ F(4) + ......+ F(N), which is again sum(1,N/2).
-> Now the sum of 1+3+5+.....+N= (N+1)*(N+1)/2
Click here for its solution.
After a sad Coding phase, I decided to gain some points in challenge phase, I was sure that many participants will attempt 500 ptr as brute force so I attacked them, I made 3 challenges one of them was wrong and finished at 75.
Next day, I opened the page to see how much rating points I lost, I was amazed that these were not too many.
Friday, September 4, 2009
Google Code JAM
I saw these stats about google code JAM and I would surely like them to share with all of my readers.
Language statistics
Solutions by Language
Regional Statistics
Hope this will help.
Wednesday, August 26, 2009
Topcoder | SRM 447 experience
Hi all,
Again a very interesting experience.
The most amazing thing was that the count of contestants from
The SRM was special in this sense because it was sponsored by facebook and top 3 positions of a room in DIV I and top 2 positions in DIV II got the prize money.
This time, again, I managed to solve only two problems.
The first problem was a bit simple. See the problem statement:
This simple problem took me 10 minutes to solve and the problem was lack of practice. There were two possible solutions for this problem:
- Sort both arrays in descending order and get the first ever value from “computers” that is greater than or equal to the current value of “complexity”. It can be done in just one loop iteration. See the code.
- Don’t sort the array and just solve it using nested loop. This strategy was a dirty one and I did this :P. See the code
The code for 500 pointer was a bit simple. Just do it as it is given in the problem statement. My code is here, let us see whether some better suggestions are there or not. Looking for comments
Oh! The code is here.
In challenge phase I didn’t participated because I was 3rd after coding phase in my room and there was a chance that after System Tests, I would have been managed to go to 2nd and qualify for the prize money, so same thing happened Al-hamdulillah and I finished at 2nd.