Win32 no more flicker

Thanks to this blog, solved that flicker problem by:

1. Painting to a back buffer instead of directly to screen
2. Overriding WM_ERASEBKGND with "return true" so that it doesn't erase the background every second/every time the screen is invalidated.

Code

Next, to get rid of the black background.

Codechef Jun 2013 Elephants (C++)

This code is simply a direct port from Python to C++. My Python submission gave a "time limit exceeded" error, while my C++ submission is perfectly accepted. Is Python really that slow?

	#include <iostream>
	#include <string>
	using namespace std;
	int main()
	{
	int T, n,m;
	int** influence = new int*[100];
	int*** dp = new int**[100];
	for (int i=0;i<100;i++)
	{
	influence[i] = new int[100];
	dp[i] = new int*[100];
	for (int j=0;j<100;j++)
	{
	dp[i][j] = new int[2];
	}
	}
	cin >> T;
	for(int t=0;t<T;t++)
	{
	cin >> n >> m;
	string* mapp = new string[n];
	// read map
	for (int n1=0;n1<n;n1++)
	{
	cin >> mapp[n1];
	}
	// initialisation
	for (int n1=0;n1<n;n1++)
	{
	for (int m1=0;m1<m;m1++)
	{
	influence[n1][m1] = 0;
	dp[n1][m1][0] = 0;
	dp[n1][m1][1] = 0;
	}
	}
	// create influence map
	for (int n1=0;n1<n;n1++)
	{
	for (int m1=0;m1<m;m1++)
	{
	if (mapp[n1].at(m1) == '1')
	{
	influence[n1][m1] += 1;
	if (m1-1 >= 0) influence[n1][m1-1]+=1;
	if (n1-1 >= 0) influence[n1-1][m1]+=1;
	if (m1+1 < m) influence[n1][m1+1]+=1;
	if (n1+1 < n) influence[n1+1][m1]+=1;
	}
	}
	}
	// run dp
	int x,y;
	for (y=0;y<n;y++)
	{
	for (x=0;x<m;x++)
	{
	int fromleft,fromtop;
	dp[y][x][0] += influence[y][x];
	dp[y][x][1] += influence[y][x];
	if (x-1 >= 0)
	{
	fromleft = min(dp[y][x-1][0], (y-1>=0)? (dp[y][x-1][1]-((mapp[y-1].at(x) == '1')?1:0)) : dp[y][x-1][1]);
	if (mapp[y].at(x)=='1') fromleft -= 1;
	if (mapp[y].at(x-1)=='1') fromleft -= 1;
	}
	if (y-1 >= 0)
	{
	fromtop = min(dp[y-1][x][1], (x-1 >= 0) ? dp[y-1][x][0]-(((mapp[y].at(x-1)=='1')?1:0)) : dp[y-1][x][0]);
	if (mapp[y].at(x)=='1') fromtop -= 1;
	if (mapp[y-1].at(x)=='1') fromtop -= 1;
	}
	if (x-1 < 0 and y-1 < 0)
	{
	} else if (x-1 < 0) {
	dp[y][x][0] += fromtop;
	dp[y][x][1] += fromtop;
	} else if (y-1 < 0) {
	dp[y][x][0] += fromleft;
	dp[y][x][1] += fromleft;
	} else {
	dp[y][x][0] += fromleft;
	dp[y][x][1] += fromtop;
	}
	}
	}
	cout << min(dp[y-1][x-1][0], dp[y-1][x-1][1])<<endl;
	}
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

More Win32 fun

Managed to set a timer to update the text on the screen every second, however, the window does not wipe itself clean after every update.

Code

After much research, came upon this solution: http://msdn.microsoft.com/en-us/library/ms632599(VS.85).aspx#layered

Instead of

	hWnd = CreateWindow(szWindowClass, 0, 0,
	CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

view raw gistfile1.txt hosted with ❤ by GitHub

I used

	hWnd = CreateWindowEx(WS_EX_LAYERED, szWindowClass, 0, 0,
	CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
	SetLayeredWindowAttributes(hWnd,RGB(255,255,255), 0, LWA_COLORKEY);

view raw gistfile1.txt hosted with ❤ by GitHub

That solved it. Code

Codechef June 2013 Elephants

	# wrong answer
	# standard DP problem with a twist.
	# the approach I chose:
	# 1. create an influence map not unlike those in game AI
	# 2. add the influence value at every point of the path
	# 3. deduct appropriate values when a mouse is double-counted
	# the rules for detecting double-counting mice:
	# 1. if a mouse moves right from tile x1 to tile x2 and there
	# is a mouse at x2, deduct 1
	# 2. if a mouse moves down from tile y1 to tile y2 and there
	# is a mouse at y2, deduct 1
	# 3. if a mouse moves from tile t to any tile, and there is a
	# mouse at t, deduct 1
	import sys
	T = int(sys.stdin.readline().strip())
	for t in xrange(T):
	n,m = sys.stdin.readline().strip().split()
	n,m = int(n), int(m)
	mapp = []
	# read map
	for i in xrange(n):
	mapp.append(sys.stdin.readline().strip())
	# create influence map
	influence = []
	for i in range(n):
	influence.append([0] * m)
	for y in xrange(n):
	for x in xrange(m):
	if mapp[y][x] == "1":
	influence[y][x] += 1
	if x-1 >= 0:
	influence[y][x-1] += 1
	if y-1 >= 0:
	influence[y-1][x] += 1
	if x+1 < m:
	influence[y][x+1] += 1
	if y+1 < n:
	influence[y+1][x] += 1
	# run DP
	dp = []
	for i in range(n):
	dp.append([0] * m)
	for y in xrange(n):
	for x in xrange(m):
	dp[y][x] += influence[y][x]
	# from left
	if x-1 >= 0:
	fromleft = dp[y][x-1]
	# rule 1
	if mapp[y][x] == "1":
	fromleft -= 1
	# rule 3
	if mapp[y][x-1] == "1":
	fromleft -= 1
	# from top
	if y-1 >= 0:
	fromtop = dp[y-1][x]
	# rule 2
	if mapp[y][x] == "1":
	fromtop -= 1
	# rule 3
	if mapp[y-1][x] == "1":
	fromtop -= 1
	if x-1 < 0 and y-1 < 0:
	pass
	elif x-1 < 0:
	dp[y][x] += fromtop
	elif y-1 < 0:
	dp[y][x] += fromleft
	else:
	dp[y][x] += min(fromtop,fromleft)
	print dp[y]
	print

view raw gistfile1.txt hosted with ❤ by GitHub

	# time limit exceeded for some reason
	# tested with 100x100 map and it runs fine locally
	# updated according to the editorial
	# catered to handle double-counting when turning a corner
	# without passing through mouse
	# standard DP problem with a twist.
	# the approach I chose:
	# 1. create an influence map not unlike those in game AI
	# 2. add the influence value at every point of the path
	# 3. deduct appropriate values when a mouse is double-counted
	# the rules for detecting double-counting mice:
	# 1. if a mouse moves right from tile x1 to tile x2 and there
	# is a mouse at x2, deduct 1
	# 2. if a mouse moves down from tile y1 to tile y2 and there
	# is a mouse at y2, deduct 1
	# 3. if a mouse moves from tile t to any tile, and there is a
	# mouse at t, deduct 1
	import sys
	T = int(sys.stdin.readline().strip())
	for t in xrange(T):
	n,m = sys.stdin.readline().strip().split()
	n,m = int(n), int(m)
	mapp = []
	# read map
	for i in xrange(n):
	mapp.append(sys.stdin.readline().strip())
	# create influence map
	influence = []
	for i in range(n):
	influence.append([0] * m)
	for y in xrange(n):
	for x in xrange(m):
	if mapp[y][x] == "1":
	influence[y][x] += 1
	if x-1 >= 0:
	influence[y][x-1] += 1
	if y-1 >= 0:
	influence[y-1][x] += 1
	if x+1 < m:
	influence[y][x+1] += 1
	if y+1 < n:
	influence[y+1][x] += 1
	# run DP
	dp = []
	for i in range(n):
	b = []
	dp.append(b)
	for j in range(m):
	b.append([0,0]) # 0 for left, 1 for top
	for y in xrange(n):
	for x in xrange(m):
	dp[y][x][0] += influence[y][x]
	dp[y][x][1] += influence[y][x]
	# from left
	if x-1 >= 0:
	fromleft = min(dp[y][x-1][0], dp[y][x-1][1]-int(mapp[y-1][x]) if y-1 >= 0 else dp[y][x-1][1])
	# rule 1
	if mapp[y][x] == "1":
	fromleft -= 1
	# rule 3
	if mapp[y][x-1] == "1":
	fromleft -= 1
	# from top
	if y-1 >= 0:
	fromtop = min(dp[y-1][x][1], dp[y-1][x][0]-int(mapp[y][x-1]) if x-1 >= 0 else dp[y-1][x][0])
	# rule 2
	if mapp[y][x] == "1":
	fromtop -= 1
	# rule 3
	if mapp[y-1][x] == "1":
	fromtop -= 1
	if x-1 < 0 and y-1 < 0:
	pass
	elif x-1 < 0:
	dp[y][x][1] += fromtop
	dp[y][x][0] += fromtop
	elif y-1 < 0:
	dp[y][x][0] += fromleft
	dp[y][x][1] += fromleft
	else:
	dp[y][x][0] += fromleft
	dp[y][x][1] += fromtop
	#print dp[y]
	print min(dp[y][x][0], dp[y][x][1])

view raw gistfile1.txt hosted with ❤ by GitHub

Codechef May 2013 Tree

	# a dive into the deep, a lot of concepts here
	# Kirchoff's Matrix Tree Theorem, Laplacian matrix, cofactors, a revision into
	# determinants
	# Revision: replacing a row by itself minus a multiple of another row:
	# doesn't change determinant
	# k=3, A =
	# 0,0,0,1,1,1,1,1,1.......1
	# 0,0,0,1,1,1,1,1,1.......1
	# 0,0,0,1,1,1,1,1,1.......1
	# 1,1,1,0,0,0,1,1,1.......1
	# 1,1,1,0,0,0,1,1,1.......1
	# 1,1,1,0,0,0,1,1,1.......1
	# 1,1,1,1,1,1,0,0,0.......1
	# 1,1,1,1,1,1,0,0,0.......1
	# 1,1,1,1,1,1,0,0,0.......1
	# ............
	# ............
	# 1,1,1,1,1,1,1,1,1,1,0,0,0
	# D =
	# 3n-3,0,0,0,0,0,.....
	# 0,3n-3,0,0,0,0,0,0..
	# 0,0,3n-3,0,0,0,0,0..
	# ....
	# ....
	# 0,0,0,0,0........0,0,3n-3
	# Laplacian matrix = D - A
	# =
	# 3n-3,0,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,3n-3,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,0,3n-3,-1,-1,-1,-1,-1,-1,-1....-1
	# .....
	# -1,-1,-1,-1,-1,-1,-1...........3n-3
	# taking away last row, and column
	# Laplacian matrix = D - A
	# =
	# 3n-3,0,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,3n-3,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,0,3n-3,-1,-1,-1,-1,-1,-1,-1....-1
	# .....
	# -1,-1,-1,-1,.......0,3n-3,0,-1-1
	# -1,-1,-1,-1,.......0,0,3n-3,-1-1
	# -1,-1,-1,-1,-1,-1,-1........3n-3,0
	# -1,-1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0 normalized = 1,-1,0000
	# 0,3n-3,3-3n,0,0,0,0............0 normalized = 0,1,-1,00
	# 1,1,3n-2,2-3n,-1,-1,0,0,0......0 -= row1 + row2*2
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0 # same
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0 # same
	# 0,0,0,1,1,3n-2,2-3n,-1,-1,0,0..0 # same
	# ....
	# 0,0,0..............3n-2,2-3n,-1
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,2-3n,-1,-1,0,0,0........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,2-3n,-1,-1,0,0....0
	# ....
	# 0,0,0.................3n,2-3n,-1
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0.................3n,2-3n,-1
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0 = 1,-1, 0, 0, 0 * 1
	# 0,3n-3,3-3n,0,0,0,0............0 = 0, 1,-1, 0, 0 * 2
	# 0,0,3n,-3n,0,0,0,0,0...........0 = 0, 0, 1,-1, 0 * 3
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0 = 0, 0, 0, 1,-1 * 4
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0 ......
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# ......... .0,0,0,3n-3,3-3n, 0, 0 = ............1,-1 * (3n-4)
	# 0,0,0..................3n,1-3n,0
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1...-1,-1,0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0..................3n,1-3n,0
	# 0,0,0................0,3n-3,3-3n
	# 0,0,0................3-3n,0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0...................3n,1-3n,0
	# 0,0,0..................0,3n-3,3-3n = 0,1,-1
	# 0,0,0..................3-3n,0,3n-3 = -1,0,1
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0..................1,0,0
	# 0,0,0..................0,3n-3,3-3n
	# 0,0,0..................3-3n,0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0..................1,0,0
	# 0,0,0..................0,3n-3,3-3n
	# 0,0,0..................0,0,3n-3
	# cofactor(3n,3n) = (3n-3)^(2n) * (3n)^(n-2)
	# finally correct; spent 3 hours figuring this out
	import sys
	def modular_exponent(a,b,n):
	binary = ""
	while b > 0:
	if b & 1 == 0:
	binary += "0"
	else:
	binary += "1"
	b >>= 1
	result = 1
	for k in xrange(len(binary)):
	result = (result * result) % n
	if binary[len(binary)-k-1] == "1":
	result = (result * a) % n
	return result
	T = sys.stdin.readline().strip()
	n,k = T.split()
	n = int(n)
	k = int(k)
	print (modular_exponent(k*(n-1),n*(k-1),10**9+7)* modular_exponent(k*n,n-2,10**9+7)) % (10**9+7)

view raw gistfile1.txt hosted with ❤ by GitHub

Google Code Jam Qualification Round 2009 Problem A. Alien Language

First time using Python sets.

	import sys
	# return a list of all tokens from a case
	# e.g. abc(abc)b(ab) returns [a,b,c,abc,b,ab]
	def getTokens(case):
	tokens = []
	token1 = case.split(")")
	for t in token1:
	t2 = t.split("(")
	for c in t2[0]:
	tokens.append(c)
	if len(t2) > 1:
	tokens.append(t2[1])
	return tokens
	# return all dictionary entries that has
	# that token at that position
	# e.g. getEntries(0,"ab") returns all entries
	# that has either a or b at pos 0
	# returns a set so no overlap/duplicate entry
	def getEntries(pos,token):
	result = set([])
	for c in token:
	if (pos,c) in sets:
	result |= sets[(pos,c)]
	return result
	L,D,N = sys.stdin.readline().strip().split()
	L = int(L)
	D = int(D)
	N = int(N)
	# initialize map of characters to dictionary entry
	# dictionary[(position, letter)] = set of all dictionary entries
	# that has that letter at that position
	sets = {}
	for d in xrange(D):
	entry = sys.stdin.readline().strip()
	l = 0
	for c in entry:
	if (l,c) in sets:
	sets[(l,c)].add(entry)
	else:
	sets[(l,c)] = set([entry])
	l += 1
	for n in xrange(N):
	# 1. read case, split into tokens
	# 2. for each position/token get all entries that has that token at position
	# 3. then get the entries common to all tokens/is present at every position
	case = sys.stdin.readline().strip()
	tokens = getTokens(case)
	possible = getEntries(0,tokens[0])
	for l in xrange(1,L):
	possible &= getEntries(l, tokens[l])
	print "".join(["Case #",str(n+1),": ",str(len(possible))])

view raw gistfile1.txt hosted with ❤ by GitHub

Win32 programming: random messages on the screen

I've always wondered how typical keygen programs, when run, doesn't create a window on screen. Or rather, technically, it's still a window, but there are no title bars, no _ □ X buttons, no borders, and even the background is transparent. Well, after viewing some basic Win32 tutorials and meddling with windows style I managed to satisfy my curiosity:

	#include "stdafx.h"
	#include "win32_gui_test.h"
	#define MAX_LOADSTRING 100
	// Global Variables:
	HINSTANCE hInst; // current instance
	TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
	TCHAR szWindowClass[MAX_LOADSTRING]; // the main window class name
	// Forward declarations of functions included in this code module:
	ATOM MyRegisterClass(HINSTANCE hInstance);
	BOOL InitInstance(HINSTANCE, int);
	LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
	INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);
	int APIENTRY _tWinMain(HINSTANCE hInstance,
	HINSTANCE hPrevInstance,
	LPTSTR lpCmdLine,
	int nCmdShow)
	{
	UNREFERENCED_PARAMETER(hPrevInstance);
	UNREFERENCED_PARAMETER(lpCmdLine);
	// TODO: Place code here.
	MSG msg;
	HACCEL hAccelTable;
	// Initialize global strings
	//LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, 0, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_WIN32_GUI_TEST, szWindowClass, MAX_LOADSTRING);
	MyRegisterClass(hInstance);
	// Perform application initialization:
	if (!InitInstance (hInstance, nCmdShow))
	{
	return FALSE;
	}
	hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_WIN32_GUI_TEST));
	// Main message loop:
	while (GetMessage(&msg, NULL, 0, 0))
	{
	if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
	{
	TranslateMessage(&msg);
	DispatchMessage(&msg);
	}
	}
	return (int) msg.wParam;
	}
	//
	// FUNCTION: MyRegisterClass()
	//
	// PURPOSE: Registers the window class.
	//
	// COMMENTS:
	//
	// This function and its usage are only necessary if you want this code
	// to be compatible with Win32 systems prior to the 'RegisterClassEx'
	// function that was added to Windows 95. It is important to call this function
	// so that the application will get 'well formed' small icons associated
	// with it.
	//
	ATOM MyRegisterClass(HINSTANCE hInstance)
	{
	WNDCLASSEX wcex;
	wcex.cbSize = sizeof(WNDCLASSEX);
	wcex.style = CS_HREDRAW | CS_VREDRAW ;
	wcex.lpfnWndProc = WndProc;
	wcex.cbClsExtra = 0;
	wcex.cbWndExtra = 0;
	wcex.hInstance = hInstance;
	wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_WIN32_GUI_TEST));
	wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground = (HBRUSH)0;//(HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName = 0;//MAKEINTRESOURCE(IDC_ARK2_GUI);
	wcex.lpszClassName = szWindowClass;
	wcex.hIconSm = 0;//LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));
	return RegisterClassEx(&wcex);
	}
	//
	// FUNCTION: InitInstance(HINSTANCE, int)
	//
	// PURPOSE: Saves instance handle and creates main window
	//
	// COMMENTS:
	//
	// In this function, we save the instance handle in a global variable and
	// create and display the main program window.
	//
	BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
	{
	HWND hWnd;
	hInst = hInstance; // Store instance handle in our global variable
	hWnd = CreateWindow(szWindowClass, 0, 0,
	CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
	SetWindowLong(hWnd, GWL_STYLE, ~WS_CAPTION & ~WS_VSCROLL & ~WS_HSCROLL & ~WS_THICKFRAME);
	if (!hWnd)
	{
	return FALSE;
	}
	ShowWindow(hWnd, nCmdShow);
	UpdateWindow(hWnd);
	return TRUE;
	}
	//
	// FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
	//
	// PURPOSE: Processes messages for the main window.
	//
	// WM_COMMAND - process the application menu
	// WM_PAINT - Paint the main window
	// WM_DESTROY - post a quit message and return
	//
	//
	LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
	{
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;
	HFONT font;
	RECT rect;
	switch (message)
	{
	case WM_COMMAND:
	wmId = LOWORD(wParam);
	wmEvent = HIWORD(wParam);
	// Parse the menu selections:
	switch (wmId)
	{
	case IDM_ABOUT:
	DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
	break;
	case IDM_EXIT:
	DestroyWindow(hWnd);
	break;
	default:
	return DefWindowProc(hWnd, message, wParam, lParam);
	}
	break;
	case WM_MOVE:
	GetClientRect(hWnd, &rect);
	InvalidateRect(hWnd,&rect, true);
	break;
	case WM_PAINT:
	hdc = BeginPaint(hWnd, &ps);
	SetBkMode(hdc, TRANSPARENT);
	GetClientRect(hWnd, &rect);
	//DrawText(hdc, TEXT("Hello, win32!"),-1,&rect,DT_SINGLELINE | DT_CENTER | DT_VCENTER);
	SetTextColor(hdc, RGB(255,0,0));
	font = CreateFont(46*2, 28*2, 215, 0,
	FW_NORMAL, FALSE, FALSE, FALSE,
	ANSI_CHARSET, OUT_DEFAULT_PRECIS,
	CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY,
	DEFAULT_PITCH | FF_ROMAN,
	L"Times New Roman");
	SelectObject(hdc, font);
	TextOut(hdc, 50, 400, L"HELLO WIN32", 12);
	EndPaint(hWnd, &ps);
	break;
	case WM_DESTROY:
	PostQuitMessage(0);
	break;
	default:
	return DefWindowProc(hWnd, message, wParam, lParam);
	}
	return 0;
	}
	// Message handler for about box.
	INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
	{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
	return (INT_PTR)TRUE;
	case WM_COMMAND:
	if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
	{
	EndDialog(hDlg, LOWORD(wParam));
	return (INT_PTR)TRUE;
	}
	break;
	}
	return (INT_PTR)FALSE;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

Next step, to make it drag-able!

Codechef May 2013 WitMath

I thought that by referencing the editorial and following faithfully I could have the solution out in minutes. Turned out to be hours..totally forgot how to do repeated squaring. Good revision, this was.

	# My first attempt at implementing Miller-Rabin primality test
	# decided to implement it instead of stealing from somewhere
	# in order to understand it
	# v2. fixed the miller rabin pass function. Now correct.
	# v3. a**s is too slow for large numbers
	# v4. using def apowbmodn(a,b,n):
	# if b==1: return a
	# return apowbmodn(a*a,b/2,n) if b%2==0 else apowbmodn(a,b-1,n)*a
	# is too slow! My guess is that the stack isn't that huge to accomodate such
	# computation.
	# v5. redesigned my modular exponential function.
	# I studied the solution from
	# http://www.codechef.com/viewsolution/2167990
	# got an Non Zero Exit Code error =\
	# v6. getting an OverflowError in the statement for i in xrange(N-1)
	# fixed; no longer using xrange
	import random
	import sys
	def miller_rabin_pass(a,r,n):
	a = a % n
	if a == 1: return True
	for z in xrange(r-1):
	if a == n-1: return True
	a = (a*a) % n
	return a == n-1
	def apowbmodn(a,b,n):
	binary = ""
	while b > 0:
	if b & 1 == 0:
	binary += "0"
	else:
	binary += "1"
	b >>= 1
	result = 1
	for i in xrange(len(binary)):
	result = (result * result)%n
	if binary[len(binary)-i-1] == "1":
	result = (result * a)%n
	return result
	def isProbablyPrime(n):
	if n == 2: return True
	if n % 2 == 0: return False
	random.seed()
	if n < 100:
	for i in xrange(2,n): # lazy to put sqrt
	if n%i ==0: return False
	return True
	else:
	s = n-1
	r = 0
	while s % 2 == 0:
	r += 1
	s /= 2
	for z in xrange(30):
	a = int(random.random() *(n-1))+1
	if not miller_rabin_pass(apowbmodn(a,s,n),r,n):
	return False
	return True
	T = int(sys.stdin.readline().strip())
	for z in xrange(T):
	N = int(sys.stdin.readline().strip())
	while 1:
	if isProbablyPrime(N):
	print N
	break
	N -= 1

view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Delish

I worked for hours on this one, just for my solution to be rejected. =( But the hard work paid off, my solution came very close to the one in the editorial =) This one didn't get accepted:

	# just some test inut
	# 10 -1 -1 -1 -1 1 -9 8 -99 2000 0 -1 -1
	# and just playing around with DP
	# 6 -4 -3 -2 -1
	# 7 -3 -2 -1 0 1
	# -2 -12 -11 -10 -9 -8 -9
	# 6 -4 -3 -2 -1 0 -1 8
	# -84 -94 -103 -102 -101 -100 -99 -100 -91
	# Managed to hit upon this property after thinking for hours
	# Edit: This is mentioned in the editorial too
	# Property 1:
	# j and k cannot have gap
	# because if have gap > 0, one side will eat it up
	# hence for each middle position j or k
	# calculate the min/max values for each section, one to the left
	# and one to the right of j/k
	# then calculate the largest absolute difference between each
	# pair of left/right sections
	# Property 2:
	# if I need the minimum value, and the sum of all elements
	# before this is > 0, then why shouldn't I leave them all out?
	# I should do this checking at every point where the previous
	# value is positive and my current number is negative.
	# EDIT: from the editorial I learnt that I should check at every
	# point, not just the points I've chosen.
	# need to speed it up
	import sys
	T = int(sys.stdin.readline().strip())
	for z in range(T):
	N = int(sys.stdin.readline().strip())
	numbers = []
	leftMins = []
	leftMaxs = []
	rightMins = []
	rightMaxs = []
	max_delish = 0
	lines = sys.stdin.readline().strip()
	for n in lines.split(" "):
	numbers.append(int(n))
	leftMins.append(10000001)
	leftMaxs.append(-10000001)
	rightMins.append(10000001)
	rightMaxs.append(-10000001)
	i_min = 0
	i_max = 0
	leftMins[0] = numbers[0]
	leftMaxs[0] = numbers[0]
	rightMins[len(numbers)-1] = numbers[len(numbers)-1]
	rightMaxs[len(numbers)-1] = numbers[len(numbers)-1]
	# for left sides
	for j in range(1,N-1):
	# for minimums
	if numbers[j] <= 0 and numbers[j-1] > 0:
	# try to move i
	if leftMins[j-1] >= 0:
	i_min = j
	leftMins[j] = numbers[j]
	else:
	leftMins[j] = leftMins[j-1] + numbers[j]
	else:
	leftMins[j] = leftMins[j-1] + numbers[j]
	# for maximums
	if numbers[j] >= 0 and numbers[j-1] < 0:
	# try to move i
	if leftMaxs[j-1] <= 0:
	i = j
	leftMaxs[j] = numbers[j]
	else:
	leftMaxs[j] = leftMaxs[j-1] + numbers[j]
	else:
	leftMaxs[j] = leftMaxs[j-1] + numbers[j]
	l_min = len(numbers)-1
	l_max = len(numbers)-1
	# for right sides
	for z in range(1,N-1):
	j = N - 1 - z
	# for minimums
	if numbers[j] <= 0 and numbers[j+1] > 0:
	# try to move i
	if rightMins[j+1] >= 0:
	l_min = j
	rightMins[j] = numbers[j]
	else:
	rightMins[j] = rightMins[j+1] + numbers[j]
	else:
	rightMins[j] = rightMins[j+1] + numbers[j]
	# for maximums
	if numbers[j] >= 0 and numbers[j+1] < 0:
	# try to move i
	if rightMaxs[j+1] <= 0:
	l_max = j
	rightMaxs[j] = numbers[j]
	else:
	rightMaxs[j] = rightMaxs[j+1] + numbers[j]
	else:
	rightMaxs[j] = rightMaxs[j+1] + numbers[j]
	max_delish = 0
	for j in range(N-1):
	k = j+1
	delish = max(rightMaxs[k] - leftMins[j], leftMaxs[j] - rightMins[k])
	if delish > max_delish:
	max_delish = delish
	print max_delish

view raw gistfile1.txt hosted with ❤ by GitHub

Did my correction and got it accepted:

	# Correction after viewing the editorial
	# Property 1:
	#j and k cannot have gap
	#because if have gap > 0, one side will eat it up
	# hence for each middle position j or k
	# calculate the min/max values for each section, one to the left
	# and one to the right of j/k
	# then calculate the largest absolute difference between each
	# pair of left/right sections
	import sys
	T = int(sys.stdin.readline().strip())
	for z in range(T):
	N = int(sys.stdin.readline().strip())
	numbers = []
	leftMins = []
	leftMaxs = []
	rightMins = []
	rightMaxs = []
	max_delish = 0
	lines = sys.stdin.readline().strip()
	for n in lines.split(" "):
	numbers.append(int(n))
	leftMins.append(10000001)
	leftMaxs.append(-10000001)
	rightMins.append(10000001)
	rightMaxs.append(-10000001)
	leftMins[0] = numbers[0]
	leftMaxs[0] = numbers[0]
	rightMins[len(numbers)-1] = numbers[len(numbers)-1]
	rightMaxs[len(numbers)-1] = numbers[len(numbers)-1]
	# for left sides
	for j in range(1,N-1):
	# for minimums
	if leftMins[j-1] >= 0:
	leftMins[j] = numbers[j]
	else:
	leftMins[j] = leftMins[j-1] + numbers[j]
	# for maximums
	if leftMaxs[j-1] <= 0:
	leftMaxs[j] = numbers[j]
	else:
	leftMaxs[j] = leftMaxs[j-1] + numbers[j]
	# for right sides
	for z in range(1,N-1):
	j = N - 1 - z
	# for minimums
	if rightMins[j+1] >= 0:
	rightMins[j] = numbers[j]
	else:
	rightMins[j] = rightMins[j+1] + numbers[j]
	# for maximums
	if rightMaxs[j+1] <= 0:
	rightMaxs[j] = numbers[j]
	else:
	rightMaxs[j] = rightMaxs[j+1] + numbers[j]
	max_delish = 0
	for j in range(N-1):
	k = j+1
	delish = max(rightMaxs[k] - leftMins[j], leftMaxs[j] - rightMins[k])
	if delish > max_delish:
	max_delish = delish
	print max_delish

view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Wstring

Seen the editorial, the algorithm described is exactly the same as what I did..but my solution is not accepted. I don't know why ='(

	# 1. partition into substrings separated by #
	# 2. for every substring, create map of symbols and their frequencies
	# 3. for every set of 3 points, from the first 3 to the last 3, compute longest length
	# 4. length for each set of points = longest length for the 4 partitions:
	# a. all partitions, merged as one, before P1
	# b. partition between P1 and P2
	# c. partition between P2 and P3
	# d. all partitions, merged as one, after P3
	# can optimize step 4 by maintaining a map for 4a and 4b each.
	import sys
	def getMaxFrequency(freq):
	maxFreq = 0
	key = -1
	for k in freq.keys():
	if freq[k] > maxFreq:
	maxFreq = freq[k]
	key = k
	return maxFreq
	def compileFrequencies(flist):
	a = {}
	for f in flist:
	for k in f.keys():
	if k in a:
	a[k] += f[k]
	else:
	a[k] = f[k]
	return a
	def minusFrequencies(one, two):
	a = one
	for k in two.keys():
	a[k] -= two[k]
	return a
	T = int(sys.stdin.readline().strip())
	for z in range(T):
	S = sys.stdin.readline().strip()
	# create partitions and frequency dictionary
	partitions = []
	prevIndex = S.find("#")
	frequencies = {}
	for c in S[:prevIndex]:
	if c in frequencies:
	frequencies[c] += 1
	else:
	frequencies[c] = 1
	partitions.append(frequencies)
	while prevIndex != -1:
	nextIndex = S.find("#", prevIndex+1)
	frequencies = {}
	if nextIndex == -1:
	for c in S[prevIndex+1:]:
	if c in frequencies:
	frequencies[c] += 1
	else:
	frequencies[c] = 1
	else:
	for c in S[prevIndex+1:nextIndex]:
	if c in frequencies:
	frequencies[c] += 1
	else:
	frequencies[c] = 1
	#print getMaxFrequency(frequencies)
	partitions.append(frequencies)
	prevIndex = nextIndex
	# cannot have empty partitions
	error = False
	for p in partitions:
	if len(p) == 0:
	error = True
	if len(partitions) < 4:
	error = True
	#print partitions
	if error != True:
	max_length = 0
	allLeft = partitions[0]
	allRight = compileFrequencies(partitions[3:])
	#print allRight
	i = 0
	max_length = 3 + getMaxFrequency(allLeft) + getMaxFrequency(partitions[i+1]) + getMaxFrequency(partitions[i+2]) + getMaxFrequency(allRight)
	for i in range(1,len(partitions)-3):
	# alter allLeft and allRight
	allLeft = compileFrequencies([allLeft, partitions[i]])
	allRight = minusFrequencies(allRight, partitions[i+3])
	length = 3 + getMaxFrequency(allLeft) + getMaxFrequency(partitions[i+1]) + getMaxFrequency(partitions[i+2]) + getMaxFrequency(allRight)
	if length > max_length:
	max_length = length
	#length = 3 + 1
	print max_length
	else:
	print 0

view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Predictopus

Was wondering for a while if the each test case is accumulative from the previous...turned out it was not. Accepted!

	# Let p = probability that team A win
	# M = amount of rupees bet on team A
	# R = number of rupees = 10000
	# E = max expected rupees
	# Hence,
	# R-M = number of rupees bet on team B
	# 1-p = probability that team B wins
	# Expected rupees
	# = p(M + M * (2-2p)) + (1-p)((R-M) + (R-M) * (2-2(1-p)))
	# = pM + pM(2-2p) + (1-p)(R-M) + (1-p)(R-M)(2p)
	# = pM + 2pM -2ppM + R-Rp -M +pM + (2p-2pp)(R-M)
	# = 4pM - 2ppM +R-Rp-M + 2pR - 2ppR -2pM +2ppM
	# = 2pM + R -Rp - M + 2pR - 2ppR
	# = 2pM + R - M + pR - 2ppR
	# = M(2p-1) + R - pR - 2ppR
	# For each case, p and R are constant.
	# Take the derivative of E against M
	# to find value of M which E is greatest
	# That value = 2p-1.
	# If p > 0.5, increasing M will increase E
	# If p < 0.5, increasing M will decrease E
	# Hence if p > 0.5 bet everything on team A
	# else if p < 0.5 bet everything on team B
	# Verification: expected rupees
	# = p[M( 1 + (2-2p))] + (1-p)[(R-M)(1+2p)]
	# = pM(3 - 2p) + (R-M) (1+p-2pp)
	# = 3pM - 2ppM + R + Rp - 2ppR - M - pM + 2ppM
	# = 2pM + R + Rp - 2ppR - M
	# = pM - M + pM + R + Rp - 2ppR
	# = M(p-1) + pM + R(1+p-2pp)
	import sys
	T = int(sys.stdin.readline().strip())
	R = 10000
	for i in range(T):
	p = float(sys.stdin.readline().strip())
	if p > 0.5:
	print(p*(R+R*(2-2*p)))
	else:
	print((1-p)*(R+R*2*p))

view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Lapindromes

Accepted!

	# 1. split string into two sections along the middle
	# 2. use a associative array to store frequency of letters in each part
	# 3. compare the 2 associative arrays
	# 4. win!
	import sys
	T = int(sys.stdin.readline().strip())
	for i in range(T):
	p = sys.stdin.readline().strip()
	if (len(p) % 2 == 0):
	# even
	part1 = p[0:(len(p)/2)]
	part2 = p[len(p)/2:]
	else:
	# odd
	part1 = p[0:int(len(p)/2)]
	part2 = p[int(len(p)/2)+1:]
	a = {}
	b = {}
	for c in part1:
	if (c in a):
	a[c]+=1
	else:
	a[c] = 1
	for c in part2:
	if (c in b):
	b[c]+=1
	else:
	b[c]=1
	palid = True
	for key in a.keys():
	#print(key, ":", a[key])
	if key not in b or a[key] != b[key]:
	palid = False
	for key in b.keys():
	#print(key, ":", a[key])
	if key not in a or a[key] != b[key]:
	palid = False
	if palid:
	print ("YES")
	else:
	print("NO")

view raw gistfile1.txt hosted with ❤ by GitHub

Google Code Jam 2009, Round 1C, Problem A: All Your Base

Here is a nice summary of the approach to this problem.

The above problem statement, requires the output to be the minimum possible number. The first step is to understand that the number would be smaller if you take the smallest possible 'Base System' for the number. To find the base system that you want, you would have to find the number of unique symbols in the input string. If there are 2 'Unique' symbols in the string, take it as 'Base 2' system. If there are 10 unique symbols, take it as 'Base 10 (Decimal)' system.....and so on. Since the 'Unary System' is not used, ignore that. 

After that, we need to find how we can make the sum, as minimal as possible. Since we don't know which digit stands for what, we have to make a decision for each symbol, so as to make the number, as small as possible. Since the left most digit carries more weight, this digit should be multiplied by the smallest digit. But since the left-most digit can't be zero (0), make it '1'. Use the Zero (0) for the second left-most digit (if there is 2nd digit in the number). Then use '2' for the third left most digit (if it is unique), '3' for the 4th left most digit (if it is unique)..and so on, unitl the end of the string with symbols. 

	// Google code jam Round 1C 2009
	// Problem A: All Your Base
	// sirpoot
	#include <iostream>
	#include <string>
	#include <map>
	#include "math.h"
	#include "bigint.h"
	using namespace std;
	BigInt power(int one, int two)
	{
	if (two == 0) return 1;
	BigInt a = one;
	for (int i=1;i<two;i++)
	{
	a *= one;
	}
	return a;
	}
	int main()
	{
	int T;
	cin >> T;
	for (int n=0;n<T;n++)
	{
	string input;
	map <char, int> val;
	cin >> input;
	//cout << input << endl;
	// 1. count number of unique symbols
	int symbols = 0;
	for (int i=0;i<input.size();i++)
	{
	if (val.count(input.at(i)) <= 0)
	{
	symbols++;
	val[input.at(i)] = -1;
	}
	}
	// 2. assign values to symbols. First encountered symbol has value of 1, second encountered is 0
	// third encountered symbol is 3, 4th is 4, 5th is 5....
	int nextVal = 0;
	for (int i=0;i<input.size();i++)
	{
	if (val[input.at(i)] == -1)
	{
	val[input.at(i)] = nextVal == 0 ? 1 : (nextVal == 1 ? 0 : nextVal);
	//cout << input.at(i) << " = " << (nextVal == 0 ? 1 : (nextVal == 1 ? 0 : nextVal)) << endl;
	nextVal++;
	}
	}
	// 3. calculate minimum seconds remaining
	BigInt sum = 0;
	int base = symbols;
	base = base < 2 ? 2 : base; // not using unary
	for (int i=0;i<input.size();i++)
	{
	//cout << power(base, input.size()-1-i) * val[input.at(i)]<< " + ";
	sum += power(base, input.size()-1-i) * val[input.at(i)];
	}
	cout << "Case #" << n+1 << ": " << sum << endl;
	}
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

^^

ACM 103 Stacking Boxes

Greedy problem. For each box, sort each dimension from biggest to smallest. Then, sort all boxes from smallest to biggest. Apply some dynamic programming and viola!

	// acm uva 103 stacking boxes
	// sirpoot
	#include <iostream>
	#include <algorithm>
	using namespace std;
	#define MAX 30
	int dimension;
	int num_box;
	int** box;
	int max_length[MAX];
	int from[MAX];
	int label[MAX];
	using namespace std;
	bool can_nest(int* inner, int* outer)
	{
	for (int i=0;i<dimension;i++)
	{
	if (inner[i] >= outer[i])
	return false;
	}
	return true;
	}
	void recursePrint(int box)
	{
	if (from[box] != -1)
	recursePrint(from[box]);
	cout << label[box] << " ";
	}
	int main()
	{
	while (cin >> num_box >> dimension)
	{
	// input
	box = new int*[num_box];
	for (int i=0;i<num_box;i++)
	{
	box[i] = new int[dimension];
	for (int k=0;k<dimension;k++)
	{
	cin>>box[i][k];
	}
	sort(box[i], box[i]+dimension);
	}
	// done input, init
	for (int i=0;i<MAX;i++)
	for (int j=0;j<MAX;j++)
	{
	max_length[i] = 1;
	from[i] = -1;
	label[i] = i+1;
	}
	// done init, process
	// first, sort boxes from smallest to biggest
	for (int i=0;i<num_box;i++)
	{
	for (int j=i-1;j>=0;j--)
	{
	if (can_nest(box[j+1],box[j]))
	{
	int* temp;
	// swap box
	temp = box[j];
	box[j] = box[j+1];
	box[j+1] = temp;
	// swap label
	int temp2;
	temp2 = label[j];
	label[j] = label[j+1];
	label[j+1] = temp2;
	}
	}
	}
	// do the DP
	for (int i=0;i<num_box;i++)
	{
	// with i as end point
	for (int j=i-1;j>=0;j--)
	{
	if (i==j) continue;
	if (can_nest(box[j],box[i]))
	{
	if (max_length[j] + 1 >= max_length[i])
	{
	max_length[i] = max_length[j] + 1;
	from[i] = j;
	}
	}
	}
	}
	// processing done, analyze results
	int max_max_length = 0;
	int max_box = -1;
	for (int i=0;i<num_box;i++)
	{
	if (max_length[i] > max_max_length)
	{
	max_max_length = max_length[i];
	max_box = i;
	}
	}
	// analysis done, output
	cout << max_max_length << "\n";
	recursePrint(max_box);
	cout <<"\n";
	}
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub