It would be greatly appreciated if someone could write up a mini-editorial, just expounding on the idea is enough and bonus points if you could link your submission for the problem as well. The folks at Codechef seem to take the editorial business not so seriously and have been late once again.

Thanks.

The Problems are here

P.S. If you're really short on time, you could skip explaining the first three problems (since they're easy) and explain the rest.

Hello Codeforces community, I resumed solving SPOJ problems a week or so back. I have noticed that you're no longer able to view the complete user submission history (either normally or via signed list) for any user apart from yourself. This is an impediment. I personally look up to a few users and solve problems that they're solving( I'm sure there are many others like me) and also see what order the top/popular users have solved the problems in, this also spares me the trouble of spending time on finding good/challenging problems on SPOJ.

I kindly request "top" users of SPOJ or just about anyone who has done a lot of SPOJ (a lot of means arbitrary lets just put 300-400+) and benefited from it to "try" and post their submission history (You could put your own signed list in a text file and host it on pastebin). It would be extremely helpful for newbie coders and for anyone who does a lot of SPOJ by following what other solve.

Thanks.

P.S. I have also sent a mail to SPOJ explaining my predicament.

Hello everyone,

I have a conceptual doubt/problem about Segment Trees and Lazy Propagation in general. I was solving this problem, 52C - Циклические RMQ.

It is a simple Range Minimum Query problem with range updates (Negative numbers are also present). And I submitted two solutions , One which doesn't involve Lazy Propagation and the other one which does. The first one got WA and the second one Ac'ed. I am curious. Have a look at the implementations.

Without Lazy Propagation — 12476539

With Lazy Propagation — 12477535

Isn't lazy propagation just a technique to do Range Updates Faster ? I had tried my first implementation on many Segment Tree based problems before and it had AC'ed.

The TL for this problem is 3s and its very liberal and hence I decided to code a normal Seg Tree without lazy propagation.

Link from where I got my Seg Tree

Don't both of them do Range updates in the same time O(log(n)) ? Can someone help me out. Thanks.

This is regarding 144D - Ракетные шахты. The problem gives an weighted undirected graph and asks us to calculate all points (not just vertices, they can be points on edges as well ) which have shortest distance equal to some given value.

I realise this is a simple Djikstra, but I am unable to understand the three cases that are given here Editorial .

I am having a real hard time understanding it(I tried reading others code, but still couldn't get it), Could someone please explain it to me. Thanks. Much appreciated.

Hello,

I was trying this problem 510C - Fox And Names, basically it asks us to do a topological sort on a DAG. I used a modified

DFS to do that — 11664540.

I do a DFS to check for a cycle, then I do a topological sort on the DAG if there are no cycles. But I was getting

WA 12th case. I tried reading others' solutions but couldn't find what was wrong with my code. I then used an O(V^2)

topological sort and it passed. Can someone point my mistake. Thanks , Help much appreciated :)

Hello, I was trying the problem HANOI07 a.k.a Building The Tower on SPOJ.

Problem link

So, I realized it is a DP problem. And hence began forming the recurrence. Condensing the problem statement you have n blocks, you need to make a tower of height h such that the bottom most level has m blocks and on each level, number of blocks should be one greater or one lesser than the previous level.

If you have n=7,h=3,m=2 then allowed tower is 2-1-2 and 2-3-2. Constraints are n<=32767,h<=60,m<=10.

My recurrence consists of three states such that f(n,h,m) = f(n-m,h-1,m+1) + f(n-m,h-1,m+1), where f(i,j,k) indicates number of ways you can form a tower consisting of n blocks , of height h and no. of top level blocks being m.

I wrote a top-down and bottom up approach the complexity being O(N*H*M), after some observation You can reduce N by a huge factor (not relevant to the current discussion, i suppose). I did that too.

But I still get TLE, I would submit my links. Could someone please help me with this. Thanks :).

Code

Hello, The May Long contest just concluded. I need some help regarding the problem CHEFCK. Unfortunately I couldn't solve it , even though I tried it for 4-5 days :( .

(http://www.codechef.com/MAY15/problems/CHEFCK).

I would describe my approach(es) to this problem and would appreciate it if someone could tell me where my thought process was slow/wrong. All of my codes are correct, I couldn't clear the 3rd subtask of the problem.

1st Approach

I initially , tried solving it by using A segment tree. The time was O(n + Q*log(2*k)), it timed out.

the link — http://www.codechef.com/viewsolution/6912313.

2nd Approach

I then got to know about Range Minimum Query from Topcoder. I read the article and then built the sparse table as described. Even that timed out. I divide the table into blocks of size log(n) and create a ST on the block minimums and then create ST for each and every block. Even this timed out.

The Link -; http://www.codechef.com/viewsolution/6928522

3rd Approach

Further optimization, I banged my head a little bit more and got to know about Cartesian Trees from Stanford CS166. I learn that there are only a limited number of block types for RMQ for a size b, there are 4^b rmq structures possible and that can be calculated using Cartesian Trees. I did that too. I calculate Cartesian tree number for each block and if it hasn't been calculated before, I calculate and memoize it in a table otherwise I reuse the already calculated RMQ structure. Unfortunately Even this timed out. I coded the approach given here and it was O(n*log(log(n) + (n/log(n))*(log(n/log(n)) + (4^b)*b*b)

(http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/01/Slides01.pdf)

[submission link] — (http://www.codechef.com/viewsolution/6960288)http://www.codechef.com/viewsolution/6960288

4th and Final Approach

I then realized that the pseudo random generator was periodic (duh!) and the same block was repeating in the array A. I also got to know about Sliding Range Minimum Query , I implemented a solution but cleared just one testcase of the 3rd subtask. [Submission] — (http://www.codechef.com/viewsolution/6971896).

Could someone tell me What I failed to observe to solve this problem. Also, could someone brief me on how and when I should be using the Sliding RMQ method, The WCIPeg website is very brief about it. Would appreciate if someone could also tell me how they implemented the approach given on Topcoder using Euler Tour of the Cartesian Tree and so forth. I am reading the codes and the editorial and trying to understand now and would appreciate some help.

Sorry for the long post and not using latex for posting complexities. Thanks :)

Your text to link here... Hi, I was doing this problem on SPOJ. It basically asks us to find total number of distinct slopes among n different points. Pretty easy( n <= 200).

So I did it using two approaches. First, I run two loops calculating all the slopes (the points are integers,and I took care and took input as doubles) and insert them in a set < double > taking care of case when dx =0 (slope = dy/dx). This approach got WA.

In second, I do the same thing but I push the slopes in a vector and then sort the vector and take care of duplicates. This Got AC.

Your text to link here...- Approach 1.-WA

Your text to link here...- Approach 2.- AC.

Can someone explain me the reason for this.

Thank You.

6306167