Блог пользователя mkagenius

Автор mkagenius, история, 4 года назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор mkagenius, история, 4 года назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +74
  • Проголосовать: не нравится

Автор mkagenius, история, 4 года назад, По-английски
  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

Автор mkagenius, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор mkagenius, 10 лет назад, По-английски

379F - Новогоднее дерево

Video Link

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

Автор mkagenius, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор mkagenius, 11 лет назад, По-английски
  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

Автор mkagenius, 11 лет назад, По-английски

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]

Полный текст и комментарии »

Теги srm
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор mkagenius, 11 лет назад, По-английски
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски

Contest @ https://summergames.interviewstreet.com

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски
Теги tco
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски
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
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски
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.

Полный текст и комментарии »

Теги dp
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски
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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски
  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

Автор mkagenius, 12 лет назад, По-английски
Yeah , "This font" is Consolas. And "This font" is Courier. The choice is yours. :) All the best.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски
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
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски
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.

Полный текст и комментарии »

Теги lis
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски
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. :)

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски
(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 =)


Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор mkagenius, 13 лет назад, По-английски
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.


Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится