mkagenius's blog

By mkagenius, history, 5 years ago, In English

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

The first one starts in half an hour.

Direct twitch link: https://www.twitch.tv/topcoder_official

Sadly all the algorithm rounds are at late at night.

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

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By mkagenius, history, 5 years ago, In English

Link: https://www.facebook.com/hackercup

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.

Edit: Submissions so far: https://www.facebook.com/hackercup/scoreboard/327966064573355/?filter=everyone

Edit: Live stream link https://www.facebook.com/pg/hackercup/videos/?ref=page_internal

Congratulations to winners:

  1. tourist
  2. LHiC
  3. Petr

Petr was first one to solve all problems though.

Full text and comments »

  • Vote: I like it
  • +74
  • Vote: I do not like it

By mkagenius, history, 5 years ago, In English

Here: https://docs.python.org/3/whatsnew/3.8.html

For competitive programming this seems useful:

Full text and comments »

  • Vote: I like it
  • +51
  • Vote: I do not like it

By mkagenius, history, 6 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

By mkagenius, 11 years ago, In English

379F - New Year Tree

Video Link

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

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By mkagenius, 11 years ago, In English

Bug in search box. Reproduction: 0. Visit : http://codeforces.me/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.

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

By mkagenius, 12 years ago, In English
  • Vote: I like it
  • -9
  • Vote: I do not like it

By mkagenius, 12 years ago, In English

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]

Full text and comments »

Tags srm
  • Vote: I like it
  • +1
  • Vote: I do not like it

By mkagenius, 12 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By mkagenius, 12 years ago, In English

Contest @ https://summergames.interviewstreet.com

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

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By mkagenius, 12 years ago, In English
Tags tco
  • Vote: I like it
  • +9
  • Vote: I do not like it

By mkagenius, 13 years ago, In English

Here is the problem statement- if u can login — https://bytecode.interviewstreet.com/challenges/dashboard/#problem/4f497b0018bad

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
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.

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
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.

Full text and comments »

Tags dp
  • Vote: I like it
  • +16
  • Vote: I do not like it

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

To start with : www.codeforces.com :D
www.quora.com
http://puzzlepicnic.com/genres

(Blogs may be excluded)

Thanks for helping.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
  • Vote: I like it
  • -11
  • Vote: I do not like it

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

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

By mkagenius, 13 years ago, In English

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 . :)






           

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
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.

Full text and comments »

Tags lis
  • Vote: I like it
  • 0
  • Vote: I do not like it

By mkagenius, 13 years ago, In English

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).

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By mkagenius, 13 years ago, In English

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.
Thanks in Advance.

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
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.

Thanks in Advance. :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By mkagenius, 13 years ago, In English
(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)
username: xyz
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" ?

Thanks in advance =)


Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By mkagenius, 14 years ago, In English
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.


Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it