Post drought

To stop this post drought (while the next article on RJT Chess is tentatively being written), I shall post an error code arising from my randomings on C++.

invalid types 'int [((unsigned int)((int)(X*Y)))][]' for array subscript

That's quite a lot of brackets towards the middle.

Sails (IOI 2007 Problem)

The problem roughly goes: You have a ship with N<=100,000 flagpoles, and each flagpole has an integer height up to 100,000. Each flag can only occupy a height of the flagpole at integer heights. Because the ship should be as aerodynamic as possible, air resistance comes into play. For each flag (don't question the question), it contributes a drag of X Newtons, where X is the number of flags behind it (w.r.t. direction of movement) flying at the same height. Your task is to write a program to determine the minimum amount of drag induced by the flags in total given the height and number of flags on each flagpole.

Here is my proposed algorithm: subject to flaws major and minor:

We make a few random observations that I'm not too sure where they appear in the solution, but let's just list them down first:

1) Total drag = summation x(x-1)/2, where x is the number of flags at each height.
1.1) It doesn't matter what order the flagpoles are arranged in.

2) There exists an optimal solution where the number of flags in each height is non-decreasing as the height gets lower.
Proof: Consider an optimal solution (if it exists) where two consecutive heights are such that the higher height has more flags, then the flags can be shifted down (by Pigeonhole Principle or something, because on the same pole there will exist space for the flags to move down)

3) The objective is to try to spread flags out as far as possible.
"Proof": 3+5>4+4 (by 1 Newton of drag), since well, can't be bothered to explain this.

4) Assuming a/b>c/d, a,b>c,d>0,0 (improvised notation ftw), then (a-c)/(b-d)>c/d.

Proposed Solution Part 1: Definitions
-------------------------------------
Define the highest level of the highest flagpole to have height 1, the second highest level to be 2 and so on, until n.

Define g(i) to be the maximum number of flags you can fly at equal to or higher than the level i.

Define f(j,k)= |g(j)-g(k)/(k-j)| (modulus function ftw).

Proposed Solution Part 2: Calculating g(i)
------------------------------------------
Raise all flags to the maximum. The number of flags at or above height i is now g(i).

To calculate all g(i) in O(N) time, we let the flags at each flagpole by represented by a range (after being raised to the maximum).

The sum of the total length of all parts of all ranges above i is then g(i).

Hence, at the start of each range, we add 1 to an array, and minus 1 after the end of each range. (ie a[0]=0, a[1]=a[0]+number of ranges starting at 1 - number of ranges ending at 0)

g(i) is then the sum of a[0]+a[1]+...+a[i] (or something like that).

Proposed Solution Part 3: The Idea
----------------------------------
Since we wish to spread out the flags among heights evenly, we will try to see whether we can do this 100% efficient. As it turns out, we cannot, because the higher levels will not fit as many flags.

So, we will probably wish to stuff as many flags into the higher levels as possible before moving on to the lower levels.

Say for the highest 6 levels we can fit 5, 14, 14, 16, 17, 18 flags respectively. Then clearly the most optimal solution involves putting 3 flags in each level (assuming there are a lot of flags past the 6th level).

After that, we realise we have reduced the problem, but the condition "(assuming there are a lot of flags past the 6th level)" is a bit iffy, so let's formalise it.

If g(k)/k is minimal among all k from 1 to n, then:
1. The heights above k can have either floor(g(k)/k) or ceiling (g(k)/k) flags.
2. That is the most optimal way of arranging the flags.

Hence, if we can find the minimal g(i)/i, we can reduce the problem.

Proposed Solution Part 4: The Problem
-------------------------------------
If the i that minimises g(i)/i is say, 1, then the reduced problem will have different g(i)/i, since the maximal number of flags above a certain level j in the reduced problem is actually equivalent to |f(i,j)*(i-j)| (stupid definitions). Or I think I should say, f(i,j) is not equal to f(0,j). Yep. That makes more sense. Hence the next minimal f(i,j) might not be the minimal f(0,j). Which means that we have to recalculate everything, which is a lot too slow (O(n^2)).

Proposed Solution Part 5: The Win
---------------------------------
We shall pretend we are stupid (slightly) to solve the problem.

At each height, if f(i, i+1) is more than the previous minimum f(a,i), then we plonk it into a list of minimums. (Like, if say g(3)/3 is the true minimum value of g(i)/i, then f(3,4) may be the minimum value of f(3,i) .

If f(i, i+1) is less than the previous minimum f(a,i), then it must be true (by Observation 4) that f(a,i+1)
After this mess, we now know the minimum g(i)/i. We also know the minimum g(i)/i in the reduced problem, the doubly-reduced problem and so on. Hence, we can calculate the minimum drag the flags add to the ship.

Chess Match

FORMAT WXF
RED meeeep ; 1219 ;;
BLACK fishballwhite ; 1069 ;;
RESULT 1-0
DATE 2011-01-02 10:45:41
EVENT KGP Game ; 10m+0s
START{
1. C2.5 h2+3 2. P7+1 c2.1 3. H8+7 r1.2
4. R9+1 r2+6 5. E7+9 c8.5 6. H2+3 c1+4
7. R9.6 r2.3 8. R6+1 c1.5 9. H3+5 c5+4
10. A4+5 a6+5 11. C8+4 e7+5 12. R1.2 h8+7
13. R2+7 r9.7 14. P7+1 e5+3 15. R6+4 r3+1
16. R6.7 r3.1 17. R7+1 e+-5 18. C8.3 h7-6
19. C3-2 r1-1 20. K5.4 r7+4 21. C5.7 r7.6
22. A5+4 r6+3 23. K4.5 e3+1 24. C3.8 r1.2
25. C8+3 e5-3 26. C8+1 e3+5 27. R7.5 r2.3
28. C8+1 e1-3 29. C7+7 r3-6 30. R5.8 r6-1
31. R2.7 r3.2 32. R8+2 c5-2 33. R8-3 r6.5
34. K5.4 r5.6 35. K4.5 h6+8 36. R8.5 r6.5
37. K5.4 r5.6 38. K4.5 h8+6 39. R7-3 r6.7
40. R7.2 r7.5 41. K5.4 k5.6 42. R2+5 k6+1
43. R5.3 r5.6 44. K4.5 h6+8 45. R2-1 }END

Feeseeks Quest ion

The story goes like this. A person (Let's call him Suicy, since he is feeling suicidal.) wants to get knocked down by a car. Therefore, He wants to run onto the road and get knocked down by a car. Currently, he is standing A units away from the road, and a car is X units away from that point. This is better illustrated in the picture below.

<--------------X------------>
C
______________________________________________________
                            ^     | 
                            |     | 
                            |     | (A) 
                            |     | 
                            |     | 
                                  S

In the diagram above (I hope all the spacings work out fine), C represents the car, while S represents Suicy. The car will travel towards the right at constant speed, while Suicy can travel in any direction at constant speed too. However, the car always travels K times as fast as Suicy. So Suicy is lazy. He only wants to start moving at the latest possible moment. He wants to find the minimal X such that he will still be able to move in such a way that he will be able to crash into the car.

Just an example. Suppose Suicy just travels head-on. That means that he moves in the direction shown by the arrow in the picture above. Then X must be at least K*A. If not, Suicy will not hit the car. Obviously, that's not the optimal solution (Because WOODHEAD wants to suan your brain =P), so you need to think of the optimal solution.

In case you are wondering, OBVIOUSLY THE CAR TRAVELS FASTER THAN YOU (Note, that means K > 1)

PS: I noticed that I can write code here. Allow me to amuse myself.
P^2S: Edited out the nonsense.

For great chess puzzles!

This one is nice :) (but not that hard to solve)

Capital letters to move. (International Chess)

........
...B.pK.
........
q.......
.n..k...
........
P...P..P
.N......

Capital letters move up (yay this makes sense on a screen). Try not to think too much. This isn't a hard puzzle.

Substring Quiz

Find words with the following substrings: (eg aeiou ---> Aerious, Absteinous, Abstemious, Abstenious, Abstentious, Abstentiously, Aceriflorum, Aceriflorus, Acheilous, Acheirous, Acleistous, Adecticous, Adventious, Affectious, Aleikoum, Alpestrious, Anemious, Annelidous, Arsenious, Arteriosum, Arteriosus, Arterious, Avenious, Bacterious, Caesious, Camelious, Carnelious, Facetious, Fracedinous, Gareisoun, Gravedinous, Haeriously, Majestious, Materious, Parecious, Phragelliorynchus, Placentious or Tragedious or sacrilegious )

1) e-i-e-i-o
2) i-i-i-u
Meh...

Post Vocab-Mugging Session 3

This post is dedicated to Chops.

The bough of this tree is so huge that I can sit on it.

I am whetting my knife on this stone, so that I can make it so sharp that it can pierce through stone.

The dearth of misers has led to a bountiful increase in donations.

Having spent insufferable hours trapped in the traffic jam, being able to speed down the expressway is only a wistful longing.

His florid prose is complemented by the brevity of his writing.

The opacity of quantum cryptography makes it an esoteric subject that only makes sense to a small group of people.

How can you play such a banal variation in one of the most explosive and unexplored openings?

Watching others bungee jump gives me a vicarious thrill.

This law, implemented in 2011, is put into effect in 2010. Now that's retroactive.

Please stop making equivocal statements and state your point clearly.

Those boisterous boys are so obstreperous! Even the threat of grounding them cannot stop them.

Diffident people are usually very ingenuous, and this may be a stereotype.

People who are sanctimonious usually become very cantankerous when their moral capability has been impugned.

I shall contrive to clear this quagmire of problems and make a morally-edifying film to clear the world of vulgarities (*hint hint* BARR).

How can a highly esteemed scholar make some vapid statements?

Despite living through the horrors of the Holocaust, he spoke about the Germans without a hint of rancour.

He repudiated all offers to write a book about his philosophy because he felt that BARR's book on BARR"s philosophy repudiated his philosophy.

He is a doughty fellow, and managed to single-handedly stop the proliferation of nuclear weapons in the world.

Years of indoctrination has ossified their mindsets, make them unwilling to change their minds.

The surreptitious salvo of bullets killed everyone in the courtroom.

She is a demure teacher and accepts no nonsense from her students.

Barr is angry because he received laudatory comments vitiated with stinging sarcasm.

Barr shot him an incredulous look, unable to believe that someone does not know what a kernel is (I wonder who is that someone XD).

His sermons are full of puns and conceits (whatever this means).

The warm rays of the sun was soon supplanted by frigid snow.

Aftering ousting Gennady Korotevich and becoming IOI champ, Penguin is inundated with requests for autographs.

We are concordant that we should pepper our daily speeches with more sophisticated vocabulary, like concordant (Ok lah, maybe not that cheem for some people).

The vignette of this treatise between China and US shows that this document puts down the rudimentary framework of the New World Order.

When sheep are allowed to frolic in gargantuan fields, they are virtually intractable.

A thin veneer of politeness hid BARR's growing anger.

The shopping list needs to be winnowed to a single page, so that carrying the items back will not be too encumbersome a task.

Misers are parsimony.

I feel august in August, because August is such an august month.

This obnoxious BARR likes to embellish his sentences with vulgarities.

This TV channel is so partisan; they only support the Republicans.

The decorous behaviour of a BARR is to pull a smug face everywhere he goes.

This avant-garde play is so modern and shocking! In other words, its so BARR!

Legends says that anyone cursed by this malediction will commit a lot of malapropism if he or she walks onto a prairie.

BARRs have the propensity to talk about byzantine topics such as mergeable heaps and AVL trees when they get bored.

Although this MacDonald's burger has been left on the shelf for eons, it still appears unsullied.

His venal ways are finally revealed, and his contract has been annulled.

Voracious people are usually supercilious because they believe that they can hold more in their stomach.

Although he is down with cancer, he is still remarkably spry.

This controversial book elicited a gamut of responses from the readers.

Fusion trees do not make BARRs fazed; on the other hand, BARRs make confusing fusion trees.

Flouting school rules fills him with mirth.

Your radical political views are repugnant to me.

The venerable BARR receives adulation from everyone (although, unlike adulation, he deserves it).

He is such a pedantic person that he makes changes to every single minutiae grammar mistake.

Although this charlatan claims to know the answer to the universe, he only knows how to shout "42!!!".

This vociferous debater likes to make known his opinions in an irate manner.

These proverbs are used so often that they have now become inane platitudes.

This porous surface allows water to flow through.

This erudite man is irascible, so you need to hold your temper if you want to learn anything from him.

He is such a capricious person that you do not need to write a polemical piece of work to convince him that your views are correct.

Drug traffickers have used this country as a conduit for shipments to the US.

People with too much hubris usually use a lot of vituperation on people who dare contradict them.

This whimsical play, although funny, transgress our notions of morality.

Qiang people are know in common parlance as "ImBARR people".

Although this job requires you to be peripepatic, it is a remunerative job.

Her vivacious personality makes her very likeable.

This problem seems to have many solutions. I vacillated between DP and comp-geom, and spent so much time deciding between the two that I have no time left to complete my code.

This garrulous person can rhapsodise about anything for 42 years without stopping.

There are many recent reports of milk adulterated with melamine.

It is useless to continually hark back to the past.

He revelled in his new found fame.

As he is a stoic person, he can only show his emotions though his anthology of poems and short stories.

The Yellow River meanders across China, making a totaly of 97 turns (if I did not remember wrongly).

Cows like to meander over the grasslands and slowly nibble the grass.

This verbatim account of our interview is only possible due to the invention of the tape recorder.

Peasants live in squalors.

This bigot has a mellifluous voice, which he uses to manipulate others to believe in his point of view.

The schism of this huge Caucus has immense implications on the world.

Even though I am extremely busy now, I can vouchsafe a reply to your question about whether Israel will vouchsafe the Palestinians' return to their homeland.

Mutations have caused his legs to atrophy.

His didactic stories are very prosaic and make me want to sleep.

Spamming your sentences with grandiloquent words will result in circumlocutory replies that beat around the bush and are not direct and to the point.

Einstein believes in the mutability of space and time.

I spoke to my interlocutor in a coarse manner.

He is a philistine and cannot appreciate art or music, as he only knows how to mug.

Your should cut your straggly hair.

The AVL tree became emblematic of imBARRness.

The Harry Potter Series is a progeny of a train ride.

These bastions act as an bulwark against frontal attacks.

Fashion is ephemeral and evanescent, and changes every summer.

This despotic ruler is killed by the rebels.

He is always an amenable child, and listens to his parent's admonishments without a single objection.

Stop being so fickle; instead of changing your mind every second, set your heart down to doing something!

Even though BARR is, well, a BARR, people lionise him.

Bush was vilified in the press for starting the Iraq War.

He is a pious man, but he makes pious speeches, so do not harbour any pious hopes that he is sincere.

Uncle BARR gave an avuncular pat on BARR's shoulder.

This person is a pugnacious person who loves to fight with others.