### mkagenius's blog

By mkagenius, history, 10 months ago,

They will live stream stuff, the schedule is here: https://tco19.topcoder.com/onsite-events/watch

The first one starts in half an hour.

Sadly all the algorithm rounds are at late at night.

They should have had them in the first half, when Eurasia is awake. Anyway.

• +3

By mkagenius, history, 11 months ago,

Quoting:

Tune in here to see this years winners LIVE reveal at 10am PDT / 1pm EDT / 6pm GMT / 10.30pm IST.

It starts in an hour.

Congratulations to winners:

Petr was first one to solve all problems though.

• +74

By mkagenius, history, 11 months ago,

For competitive programming this seems useful:

• +51

By mkagenius, history, 17 months ago,

# Single Round Match 757

Topcoder SRM 757 is scheduled to start at 21:00 UTC-4 on April 29, 2019.

Registration is now open for the SRM in the Arena or Applet and will close 5 minutes before the match begins, so make sure that you are all ready to go. Click here to what time it starts in your area.

• +52

By mkagenius, 7 years ago,

379F - New Year Tree

I wanted to go into details — but it would have been a full 30 minutes. Any suggestion/query is welcome.

• -1

By mkagenius, 7 years ago,

Bug in search box. Reproduction: 0. Visit : http://codeforces.com/contest/351/standings 1. Click on search arrow, the search box now shows up. 2. Type 'a'. Then press 'backspace'. 3. The page should have all the 100 results, but it is empty.

• +15

By mkagenius, 7 years ago,

• -9

By mkagenius, 8 years ago,

When I run "Run systest", it gives me segmentation fault. When I try the same test case in the applet's editor, it gives correct result.

Weird Compiler!

class TeamContest
{
public:
int worstRank(vector <int> strength)
{
if((int)strength.size()  == 3) {
return 1;
}
vector<int> remaining;
for(int i = 3; i < strength.size(); i++){
remaining.push_back(strength[i]);
}
sort(remaining.begin(), remaining.end());

int mn = min(strength[0], min(strength[1], strength[2]));
int mx = max(strength[0], max(strength[1], strength[2]));
int sum = mn + mx;
int end = (int)remaining.size() - 1;
int required = sum + 1 - remaining[end];
//            	cerr << required << endl;
for(int i = 0; i < remaining.size(); i++){
cout << remaining[i] << "  ";
}
//         	cerr << "-----------------------\n";
int ind = 0;
int cnt = 0;
while(((ind < end &mdash; 1))){
while((ind < end &mdash; 1) && (required > remaining[ind])){
ind++;
}
if(ind >= end -1) break;
//           		cerr << "[" << ind << "," << end << "]" << endl;
ind+=2;
end--;
cnt++;
if(end >= 0 && end < remaining.size())
required = sum+1-remaining[end];
}
return 1 + cnt;

}

};
[/code]



• +1

By mkagenius, 8 years ago,

See next SRM is on 13 dec 2012 — http://community.topcoder.com/tc

• -2

By mkagenius, 8 years ago,

You will need an account though. (or facebook login is also there)

• -7

By mkagenius, 8 years ago,

• +9

By mkagenius, 9 years ago,

otherwise — http://pastebin.ca/2121976

My approach,

Make a cumulative sum array.

Now for every index starting from 0, do binary search for k, k+mod, k + 2*mod, ..., k + 76*mod on range limited by previous max-length found, i.e. if we already have found an array of length L, which sum upto k (after doing mod) , then accordingly we have to modify the binary-search space, because we do not require a shorter-length answer.

Will this approach time-out ? As I can't submit there anymore, I need your help to see whether it is correct approach or not.

• 0

By mkagenius, 9 years ago,
Q. Find the kth element from the union of two sorted arrays.(one of size n, other of size m).
===================================
Although there are numerous resources on the web that claim to solve it in log(n) or log(k) . But I have not found a complete solution which takes care of all cases, such as  k  < n or k < m or k > 2*n etc.,
i mean none took care of all cases.

So, I tried to get log(n+m) complexity, but i could not achieve it taking all kind of cases into considerations, every time i miss some of the case.
===================================
A help is needed here to get a full solution.

• -7

By mkagenius, 9 years ago,
Hi,
I thought may be a dp solution is possible.
I have a solution but it does not work, any hint on how to apply dp.

Two lottery game. (div2 500pt) srm 418.

Thanks.
P.S : I can share my code, if needed, i used a dp[33][33][33][33] array.

• +16

By mkagenius, 9 years ago,
I was wondering how many websites are made by a topcoder member.
I was hoping you will help me.

www.quora.com
http://puzzlepicnic.com/genres

(Blogs may be excluded)

Thanks for helping.

• +2

By mkagenius, 9 years ago,

• -11

By mkagenius, 9 years ago,
Yeah , "This font" is Consolas. And "This font" is Courier. The choice is yours. :) All the best.

• -8

By mkagenius, 9 years ago,

This is how we can use hashing to solve #Petr :

First how to hash all sub-strings of S of length n in O(n)  :

Let the string be  "abcdefgh"

We will do cumulative hashing as following :
Lets take a prime number p;
(here a , b , c , ... , h are ascii values of 'a' , 'b' ,'c' , .. ,'h' )
hash[0] = a;
hash[1] = a*p + b;
hash[2] = a*p^2 + b*p + c;
hash[3] = a*p^3 + b*p^2 + c*p + d;
like-wise up-to hash[7] = a*p^7 + b*p^6 + ... + g*p + h;

So, you must have figured out the recursive relation for finding hash[x].
hash[x] = hash[x-1]*p + s[i].
(base case: hash[0] = s[0] )

Now as we are done with finding cumulative hash value. We need to find the hash value of any substring.
Lets see this thing:
Let there is a string "dabctabc" ,
now "abc" at 1 and "abc" at 5 are same strings , and we must wish to have same hash value for both of them . We propose that every hashed value should be of form :
(for a substring of s from i to j inclusive.)
n = length of the whole string .
s[i]*p^n + s[i+1]*p^(n-1) + .. + s[j] *p^(n-length_substring);

Can you feel/see that if we maintain this proposition above , "abc" at 1 and "abc" at 5 will have same hash values .
(make sure we understand this before moving further)

For maintaining above proposition  , we maintain an array: step[]
step[x] = step[x-1]*p ;
(base case: step[0] = 1)

Now from hash[] and step[] we can calculate hash values of each of the substrings.
Lets remind us we are talking about the string "dabctabc" :
For any substring starting at i and ending at j (inclusive) :
for "abc" at 1:
substring_length = 3.
so, hash_value should according to our proposition should be:
a*p^7 + b*p^6 + c*p^5 .
See,
hash[3]  = d*p^3 + a*p^2 + b*p + c;
hash[0]  = d;
so our required value will be : (hash[3] - hash[0]*p^3)*(p^(8-3))
i.e (hash[3] - hash[0]*step[substring_length])*step[n - length_of_substring]

So, generalised formula for any substring starting at i and ending at j (inclusive) :
(hash[j] - hash[i]*step[substring_length])*step[n - substring_length] )

Now use the above formula for calculating hash value of "abc" at 5.
We will see that this "abc" also hash the same value that is "a*p^7 + b*p^6 + c*p^5".

Our job is almost done . :)

• 0

By mkagenius, 9 years ago,
Let there be a sequence of integers : 3,1,6,3,7,8,2,7 ;

If you insert this sequence in set<int> after sorting the, time taken as a whole ( i.e sorting + inserting) will be lesser than direct insertion into the set without sorting.

• 0

By mkagenius, 9 years ago,
Can someone explain how do to get the array of LIS , that is the dp[] array we normally get in LIS using n^2 algo. using nlogn algo. that is patience sort ? Thanks.

• 0

By mkagenius, 9 years ago,

Code:

#include
int main()
{
char *s[]={"codeforces","russia","contest"};
char **p;
p = s;
printf("%s ",++*p);
printf("%s ",*p++);
printf("%s ",++*p);
scanf("%*d");
return 0;
}

Output: odeforces odeforces ussia

Please someone explain the output( 2nd and 3rd string).

• +9

By mkagenius, 9 years ago,

I think it has happened a while ago on codeforces itself, but I forgot the reason why this happens:
See this code and code below.
http://ideone.com/N7vzQ

and added 1 "cout"  to the code at 119 and result changes:
http://ideone.com/OXHpO

By adding cout <<" "; should not change 39 to 2. :|

My guess is , its compilers problem.

• -2

By mkagenius, 9 years ago,
I loved the solutions of Codeforces round 74 problem B div 1 .
It required (not necessarily) the use of structs.

I would like to know , is there any internet site where good tutorial is there.
And Is there any previous questions similar to this question.

• 0

By mkagenius, 9 years ago,
(I know I should have asked this in topcoder forums , but I thought , its possible that someone can help me out here as well  =) )
I want to login in the arena using proxy settings:
for example ::
ip: 172.xxx.xxx.xxx
port : 9401 ( now this must be 9401)
pass::zyx

I heard that topcoder applet/jws uses 5001 as a port (or 80 also).
1.Can I use 9401 as a port?

But when I am using the above settings. It does not connect.
It says ==> (the connection to the server cannot be established..)
I have also tried the 4 tunnels.
2.So, what can be done?

3.Also, Is there any way that I  can tell the applet/jws to "use the proxy settings in the browser" ?

• 0

By mkagenius, 9 years ago,
This is the problem , I was trying to solve:

I think , that each row  should be treated as a sub-game.
And we need to find a grundy-value for each row and then we need to Xor the values to get the result.

The problem I am facing is that I am not able to extract the grundy number from each sub game.
Your Help will be highly appreciated.
Thanks.