c#

1026. Questions and answers

http://acm.timus.ru/problem.aspx?space=1&num=1026

Time Limit: 2.0 second
Memory Limit: 16 MB

Background

The database of the Pentagon contains a top-secret information. We don’t know what the information is — you know, it’s top-secret, — but we know the format of its representation. It is extremely simple. We don’t know why, but all the data is coded by the natural numbers from 1 up to 5000. The size of the main base (we’ll denote it be N) is rather big — it may contain up to 100 000 those numbers. The database is to process quickly every query. The most often query is: "Which element is i-th by its value?"— with i being a natural number in a range from 1 to N.

Problem

Your program is to play a role of a controller of the database. In the other words, it should be able to process quickly queries like this.

Input

Input of the problem consists of two parts. At first, a database is written, and then there’s a sequence of queries. The format of database is very simple: in the first line there’s a number N, in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written simply as well: in the first line of the sequence a number of queries K (1 ≤ K ≤ 100) is written, and in the next K lines there are queries one in each line. The query "Which element is i-th by its value?" is coded by the number i. A database is separated from a sequence of queries by the string of three symbols "#".

Output

The output should consist of K lines. In each line there should be an answer to the corresponding query. The answer to the query "i" is an element from the database, which is i-th by its value (in the order from the least up to the greatest element).

Sample

input	output
5 7 121 123 7 121 ### 4 3 3 2 5	121 121 7 123

Problem Author: Leonid Volkov
Problem Source: Ural State University Internal Contest October'2000 Junior Session

My Solution

using System;
using System.Collections;
using System.Globalization;
 
namespace acm.timus.ru_p1026
{
    class Program
    {
        static void Main(string[] args)
        {
            ArrayList list = new ArrayList(100000);
            NumberFormatInfo nfi = NumberFormatInfo.InvariantInfo;
            string[] input = Console.In.ReadToEnd().Split(new char[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
            int i = 0;
            int len1 = Int32.Parse(input[0]);
            for (i = 1; i <= len1; i++)
            {
                int n = Int32.Parse(input[i]);               
                list.Add(n);
            }
            int len2 = Int32.Parse(input[len1+2]) + len1 + 3;
            list.Sort();
            for (int j = len1 + 3; j < len2; j++)
            {
                int n = Int32.Parse(input[j])-1;
                Console.WriteLine(list[n]);
            }
        }
    }
}

Add new comment

Asp.net: File Download Handler

Recently I had the need to make a file download page where statistics could be collected and saved on each individual download. After a little research I found a nice way to get this task done easily.

Because it is only collecting stats about the download and then sending the file to the browser, I decided to use an Asp.net Generic Handler.

Download.ashx.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Services;
using System.IO;
 
namespace WriteFileTest
{
    [WebService(Namespace = "http://tempuri.org/")]
    [WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]
    public class Download : IHttpHandler
    {
 
        private string FilesPath
        {
            get
            {
                return @"C:\Users\John Boker\Documents\Visual Studio 2008\Projects\WriteFileTest\Files\";
            }
        }
 
        public void ProcessRequest(HttpContext context)
        {
            string filename = context.Request.QueryString["file"];
            if (!string.IsNullOrEmpty(filename) && File.Exists(FilesPath + filename))
            {
                context.Response.ContentType = "application/octet-stream";
                context.Response.AddHeader("Content-Disposition", string.Format("attachment; filename=\"{0}\"", filename));
                context.Response.WriteFile(FilesPath + filename);
            }
            else
            {
                context.Response.ContentType = "text/plain";
                context.Response.Write("Invalid filename");
            }
        }
 
        public bool IsReusable
        {
            get
            {
                return false;
            }
        }
    }
}

One advantage to this method is the files do not have to be in the website directories and public, extra authentication can be done and the download can be disallowed if necessary.

To test this i created a small Default.aspx page containing:

<%@ Page Language="C#" AutoEventWireup="true" CodeBehind="Default.aspx.cs" Inherits="WriteFileTest._Default" %>
 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title></title>
</head>
<body>
    <form id="form1" runat="server">
    <div>
        <a href="Download.ashx?file=FileZilla_3.3.0.1_win32-setup.exe&d=<%= DateTime.Now.Ticks %>">FileZilla_3.3.0.1_win32-setup.exe</a>
        <br />
        <a href="Download.ashx?file=gimp-2.6.7-i686-setup.exe&d=<%= DateTime.Now.Ticks %>">gimp-2.6.7-i686-setup.exe</a>
        <br />
        <a href="Download.ashx?file=jdk-6u17-windows-x64.exe&d=<%= DateTime.Now.Ticks %>">jdk-6u17-windows-x64.exe</a>
        <br />
        <a href="Download.ashx?file=WampServer2.0i.exe&d=<%= DateTime.Now.Ticks %>">WampServer2.0i.exe</a>
    </div>
    </form>
</body>
</html>

As you can see i added another argument to the QueryString; this is to keep the browser from caching files with the same link and filename.

WriteFile Default Page Image

The results after clicking the filezilla link:

WriteFile Save Dialog

This was a very simple method to take care of multiple issues including:

Download Tracking
Alternate File Locations
Browser Caching Issues
Extra Authentication

StringBuilder vs. Concatenation

1: Intro

After the if vs. ternary deathmatch I started wondering just how much slower string concatenation was versus using a StringBuilder. Below are the test and results, not very surprising though.

2: Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
 
namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] words = ("Quisque in neque at orci congue " +
                            "tempor. Donec id eros velit, eu " +
                            "sodales est. Sed purus eros, tempor  " +
                            "id ultricies eget, volutpat a mauris.  " +
                            "Suspendisse potenti. Suspendisse id  " +
                            "ligula nec felis mattis pellentesque  " +
                            "nec quis ipsum. Vivamus sed metus nunc,  " +
                            "non eleifend ligula. Sed mollis sagittis  " +
                            "pellentesque. Nam sit amet ante ut risus  " +
                            "pulvinar rhoncus. Vestibulum molestie  " +
                            "feugiat leo sed placerat. Sed consectetur " +
                            "velit ut magna molestie molestie tincidunt " +
                            "magna viverra. Quisque eu diam lacus. Sed  " +
                            "blandit, felis vel sollicitudin pellentesque, " +
                            "sapien nisl ullamcorper mauris, dapibus  " +
                            "accumsan diam augue et diam. Ut suscipit  " +
                            "nibh pretium nisi pulvinar vitae condimentum  " +
                            "felis mattis. Donec justo orci, gravida in  " +
                            "aliquam et, cursus sit amet sapien. Pellentesque " +
                            "mauris ipsum, ornare ac blandit nec, pretium  " +
                            "nec purus. Curabitur malesuada, lectus at  " +
                            "fermentum tempus, risus orci condimentum  " +
                            "lorem, id consequat dolor velit sed arcu.  " +
                            "Duis hendrerit rutrum tellus, a dignissim  " +
                            "velit facilisis ac. Curabitur pretium quam a " +
                            "metus sagittis mattis. Cum sociis natoque  " +
                            "penatibus et magnis dis parturient montes,  " +
                            "nascetur ridiculus mus.").Split(" ".ToCharArray());
 
 
            TimeSpan concatenationTestTime = TestConcatenation(words);
            TimeSpan stringbuilderTestTime = TestStringBuilder(words);
 
            Console.WriteLine(string.Format("StringBuilder: {0}", stringbuilderTestTime));
            Console.WriteLine(string.Format("Concatenation: {0}", concatenationTestTime));
 
            Console.ReadLine();
 
        }
 
        static TimeSpan TestConcatenation(string[] words)
        {
            string finalResult = string.Empty;
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < 100; i++)
            {
                foreach (string word in words)
                {
                    finalResult = finalResult + word;
                    finalResult = finalResult + " ";
                }
            }
            sw.Stop();
            return sw.Elapsed;
        }
 
        static TimeSpan TestStringBuilder(string[] words)
        {
            string finalResult = string.Empty;
            StringBuilder full = new StringBuilder();
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < 100; i++)
            {
                foreach (string word in words)
                {
                    full.Append(word);
                    full.Append(" ");
                }
            }
            finalResult = full.ToString();
            sw.Stop();
            return sw.Elapsed;
        }
    }
}

3: Results

The not too surprising results: StringBuilder is a lot faster than string concatenation.
Results

If vs Ternary: Deathmatch

1: INTRO

The Fun With the ?? Operator in C#: if { } or ?? – Which is Faster? article by Keith Elder got me thinking about the if statement and the ternary operator.

Is there a real difference or are they both the same?

To answer this question I put together a little project that tests both cases and times them.

2: CODE

using System;
using System.Diagnostics;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
 
            string[] strArray = new string[20000];
            Random r = new Random((int)DateTime.Now.Ticks);
            for (int i = 0; i < 500; i++)
            {
                int rnum = r.Next();
                if (rnum % 2 == 0)
                {
                    strArray[i] = null;
                }
                else
                {
                    strArray[i] = rnum.ToString();
                }
            }
 
            TimeSpan ts1 = TimeSpan.Zero;
            TimeSpan ts2 = TimeSpan.Zero;
 
            for (int i = 0; i < strArray.Length; i++)
            {
                ts2 = ts2.Add(countWithTernary(strArray));
                ts1 = ts1.Add(countWithIf(strArray));
            }
 
            for (int i = 0; i < strArray.Length; i++)
            {
                ts1 = ts1.Add(countWithIf(strArray));
                ts2 = ts2.Add(countWithTernary(strArray));
            }
 
            Console.WriteLine("     if: " + ts1.TotalMilliseconds.ToString());
            Console.WriteLine("ternary: " + ts2.TotalMilliseconds.ToString());
            Console.ReadLine();
        }
 
 
        private static TimeSpan countWithIf(string[] arr)
        {
            Stopwatch sw = new Stopwatch();
            int len = arr.Length;
            int count = 0;
            sw.Start();
            for (int i = 0; i < len; i++)
            {
                if (arr[i] == null)
                {
                    count += 1;
                }
                else
                {
                    count += 2;
                }
            }
            sw.Stop();
            return sw.Elapsed;
        }
 
        private static TimeSpan countWithTernary(string[] arr)
        {
            Stopwatch sw = new Stopwatch();
            int len = arr.Length;
            int count = 0;
            sw.Start();
            for (int i = 0; i < len; i++)
            {
                count += arr[i] == null ? 1 : 2;
            }
            sw.Stop();
            return sw.Elapsed;
        }
    }
}