Hello there,

Several days ago I came across this problem 100712L — Alternating Strings II in gym 2015 ACM Amman Collegiate Programming Contest

Given a string S consists of 0's and 1's only, and given K, we define the alternating string is that the string that starts with 0 and then alters 1 then 0... to the end of the string or vice versa starts with 1, for example, 101,01,010 are alternating strings, while 110,0,01011 are not.

1 <= K <= |S| <= 100000, you are to find the minimum number of cuts you have to make to break the string down into non-alternating strings that each of them has at most K digits .

I tried to solve it this way, let dp[i] be the minimum number of partitions that needed to split S as the problem states, assuming the indexing starts with 2 being the first character, and n is the length of the string, then the answer to the problem will be dp[n+1]-1

alt[i] contains the length of the longest alternating string that ends at position i.
Now let dp[1] = 0 and start iterating over the string from 2 to n+1, initially dp[i] = dp[i-1]+1 that we made a cut at position i then let's look at the longest alternating string in the range [i-k,i], let this value be e, if e is less than the length of the range [i-k,i] then for sure this range doesn't form an alternating string, so we look up the minimum value of dp in the range [i-k-1,i-1] and update dp[i] with min(dp[i],minValue+1) .

Here's my code, I keep getting WA I tried to figure out where I'm going wrong but no use, I would be so grateful if someone could indicate what's wrong with this algorithm/code .

All submissions since almost 15 mins till now are being in queue!!

Hello Codeforces,

Recently I decided to start learning geometry so I found out that I have to start with the simple geometry, basic shapes, basic laws and cakewalk problems to set off my journey with geometry and computational geometry then, so I came across this problem from the gym,

Given a circle (the center of the circle |x|,|y| <= 1000, and the radius r <= 10000) .
Given a rectangle (the coordinates of the bottom-left corner and the upper-right corner, |x|,|y| <= 1000 as well) .
It's guaranteed that the upper-left corner of the rectangle is inside the circle, the width and the height of the rectangle are longer than 2.r .
you're to calculate the area of the intersection between the circle and the rectangle .

Here's what I did :



- Obtain the two lines P2-P3 let's say L1 and P2-P1 let's say L2 .
- Find the points of the intersection between the lines L1,L2 and the the circle, They're CL1, CL2 .
- Compute the angle (CL1 C CL2) theta .
- Compute the area of the circular sector determined by theta, say A .
- Subtract the area of the triangle (CL1 C CL2) from A .
- Add the area of the triangle (CL1 P2 CL2) to A and A is the answer .

So I keep getting WA for the couple past days. Since it's being the first time I write a geometry code I know it'd be so buggy and really it was, I've been debugging it for hours and I re-wrote it several times, and eventually I had no thing to do with it, I badly ran out of my shots :(
Here's my code .

It would be really appreciated if someone tells me what's going wrong (maybe it's my algorithm though, Now I doubt it's absolutely correct) Thanks in advance .

By the way, any advice, references, and problems would help a noob to kick-off in geometry would be highly appreciated as well .

Hello there,

I was trying to solve this problem on Hackerearth the problem asks for the length of the longest substring which is repeated at least K times, 1 <= K <= |S| <= 10^6

I built the suffix array of the string and built the LCP array then get the maximum element among the minimum elements in all possible consecutive segments of length K-1 in the LCP array, Thus, if the LCP array was [0,1,2,3,2,3] and K was 4 then we have :

1. [0,1,2] min is 0
2. [1,2,3] min is 1
3. [2,3,2] min is 2
4. [3,2,3] min is 2

Now the maximum element is 2 and this is the answer, My solution keeps getting WA on some test files, and unfortunately editorial page has no explanation about the solution, just two codes, one uses an absolutely different idea where it uses hashing and binary search (No idea!!) and the other one slightly uses the same idea using suffix tree instead but it's so messy and couldn't track it down.

Here's my code .
Any help would be highly appreciated .

Hello coders,
Hope everyone's fine and doing well,

I need your help folk, I'm trying to solve this problem C. Watto and Mechanism and got stuck for a couple of days .

The problem in a nutshell : Given n strings then m queries (each query is a string) 0 <= n,m <= 3*10^5 for each query determine if the string mi exists in the set of n with at most one mismatch .

What I did : put all the n strings in a Trie then for each query traversal the trie and allow just one character to mismatch, if the query ended in a leaf then return true, else return false .

I'm not sure if this approach will pass in the TL but at least I think it's true .
Here's my code .
I'm still getting WA on test 6 and test 6 is too long to be shown, I really tried so many arbitrary test cases and my code could produce the right output for them I revised the code and the algorithm multiple times but could not find what's going wrong!

Any help would be highly appreciated,
Thanks in advance .

Hey codeforces,

I wanna ask about the special character that be appended to the string when building its suffix array, Why this character is important ?
I do understand the functionality of it in the suffix tree and in the construction of the suffix array using DC3 (Difference Cover) algorithm (actually 2 special characters should be appended in this algo) .
But when neither the construction nor the traversal requires it why to append it !?

This question came out after solving this problem (11512 — GATTACA) (given a string find the LRS (Longest Repeated Substring) and how many times the LCS occurs) , when I was solving it I faced such an odd issue I was almost sure that everything is right but still getting WA more than 10 times, I tried more than 100 testcases and my code could produce the right output for them .
Eventually just added this line to my code strcat(text,"$"); and got AC, I spent my whole day trying to figure out what a spell this line does, but ended up with nothing .
Here's my code, you can try it yourself .
Any explanation, elaboration, and help in this issue would be appreciated,

Thank you all :D .

Hey Codeforces,
I wish everyone is doing well and happy .

Lately I learned Suffix Array and I'm trying to solve this problem (UVA — 760 DNA Sequencing), the problem is a merely application on finding the LCS (Longest Common Substring) of two strings .

- The problem in a nutshell : given two strings A,B (|A|,|B| <= 300) print all LCS of these two strings in lexicographical order .
- What I did : concatenate the two strings in a third string C and build the suffix array and the LCP (Longest Common Prefix) for C then iterate over the LCP table and find the longest LCP among all LCPs, say maxLCP then iterate over the LCP table again, now once an LCP matches maxLCP check whether the two suffixes belong to a different strings (A,B) if they do, print this LCP, if there is no LCP found print "No Common Sequence" as the problem states .

Here is my code .
Code after removing the duplicated LCS .
Shouldn't my approach work ?
I've tried many testcases and my code does produce the correct output for them, I got stuck on this problem for more than two days, read the code and revise the algorithm so many times, and couldn't figure out where's my fault .

Any help would be highly appreciated,
Thanks in advance and thank you for taking time to read my blog and good luck in the upcoming round tomorrow :D .

UPD : Thanks community, got AC after 15 submissions :D, as Urbanowicz indicated, I should print just unique LCSs