memset0's blog

Topcoder Single Round Match 701
By memset0, history, 8 years ago, In English

Hi All,

Topcoder Single Round Match 701 will be held 26 October 05:00 PM BDT

Wish you all good luck. Let's discuss the problems after the contest .

EDIT : This match is sponsored by booz allen hamilton. winners will get t-shirts from Booz Allen Hamilton .

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

Comments Comments (57)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The match announcement promises t-shirts from Booz Allen Hamilton again (and this should really be included in the blog announcement, not in the comments). Not sure whether this is a copy-paste error, I guess we'll just have to wait and see :-)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I could not find the t-shirt announcement in the web arena. ( It only mentions sponsored by BAH). I guess its there in the applet. To popularise it better, the announcement should also be put in Web arena.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    What's the criteria for getting t-shirts?

    → Reply
»
8 years ago, # |
  Vote: I like it +64 Vote: I do not like it

I would prefer srm announcements from one person and I think that cgy4ever is the best option. Finding an old discussion would be so much easier then, just scrolling through his blogs. Searching the blog in google or in codeforces-search doesn't give instant results sometimes.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    then I will cordially request cgy4ever for posting srm announcements from next SRMs

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    I think a special account made for Topcoder admins is an even better option.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +83 Vote: I do not like it

    Okay, I will add a blog for each SRM once I know it — so you can view my blog to see the schedule of upcoming SRMs.

    And I will update it about 24 hours before the contest so that it will be in the "recent actions" list.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

Has anyone used the Web Arena recently? Has it improved? (e.g. stable to use, can challenge normally, etc.)

Also is there any way to generate class definition, test codes... for the web arena?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    It is definitely a lot more stable than it was before. Not faced any issue in the past few srms i participated.

    I have not yet found any method to generate these.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The competition just finished. Can someone please tell me how to solve Div2. 1000 pointer ? I partially computed the state (win/lose) for numbers upto 1,000,000. For numbers greater than that I used recursion to reach numbers <= 1,000,000. But It didn't work, I was getting seg fault. Anyone who solved the problem, Kindly share the approach and if possible, a link for the code. Much Thanks.

→ Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Any hint for Div1.600 ? There seems to be a crucial insight ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    The first character of the string can either be at the first position or the last (since only reversal m affects it).

    Then, of the remaining positions of the final string that aren't fixed, the second character of the original string can either be at the first position or the last, and so on...

    Now use this observation to make a DP function that counts how many of the resulting strings have a prefix p. My DP state was (how many characters in front, how many characters in back).

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2 900 problem ?? Any hints

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 900?

I saw only one person who passed all tests.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to view the global leaderboard ?? I could only find the room summary leaderboard. I am new to topcoder .

    → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve div1 300 ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    What I did was this, the boolean value DP[0][n] denotes whether it is a winning position for Alice or not, and DP[1][n] denotes the same for Bob. I calculated these values till 1e5. Consider any 5 consecutive values of DP[0] array. There are at most 2^5 = 32 such sequences. So if you precompute till 1e5, one is bound to repeat. Using that I found the length of the cycle (let it be len). Then answer is DP[0][n % len].

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider any 5 consecutive values of DP[0] array. Why 5 elements is enough, but not 1+2+3+4+5=16?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Because you take either 1,2,3,4 and/or 5 elements from the pile. So, DP[0][i] depends on DP[1][i-1], DP[1][i-2], DP[1][i-3], DP[1][i-4] and/or DP[1][i-5]. :)

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hey satyaki3794, I was looking at your code for this problem. I couldn't understand one thing. Why don't you break off the loop once you have the cycle value for the first time.I mean shouldn't the cycle value remain constant?

          I tried this but this gives a WA? Can you please explain what is wrong with this idea?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, cycle value should remain constant. Breaking off the loop when you get cycle value for the first time shouldn't change the answer. There must be some other bug in your code.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it +1 Vote: I do not like it

              Hi satyaki3794, even i tried by the same approach but breaking off when i get the cycle for first time fetched WA. Gives AC when submitted without the break statement.

              Code
              → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm trying to understand why you picked 1e5. If each group has 5 things and there are 32 possible groups, then after 5*32=160, the next group should be a repeat. So is checking 165 enough, or was 1e5 significant for some other reason? Thanks.

      (I just noticed that 165 and 1e5 are similar, with e being upside down 6 :-)

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Is this correct?

    Code
    → Reply
»
8 years ago, # |
  Vote: I like it -39 Vote: I do not like it

I need some Help :D Here's my solution for 250 Div2

#include <bits/stdc++.h>
#define pb(x) push_back(x)
#define bug cout<<"HERE"<<endl;
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define clr(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(),v.end()
#define FOR(i,l) for(int i=0;i<l;++i)
#define FOR1(i,s,l) for(int i=s;i<l;++i)
#define FOR2(i,s) for(int i=s;i>=0;--i)
#define fast 	ios_base::sync_with_stdio(0); cin.tie(0);
#define inp freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
using namespace std;

typedef long long ll;
typedef vector<int> vi;
inline int toInt(string s){int v; istringstream sin(s);sin>>v;return v;}
inline ll toll(string s){ll v; istringstream sin(s);sin>>v;return v;}


class SquareFreeString{
public :

	string isSquareFree(string s){
		int n = (int)s.length();
		bool f = 0;
		FOR(i,n){
			FOR1(j,i+1,n){
				string cur = "";
				for(int k=i;k<=j;++k)cur+=s[k];
				if(cur.length()%2==0){
					if(cur.substr(0,cur.length()/2)==cur.substr(cur.length()/2,cur.length())) f = 1;
				}
			}
		}
		return f ?"not square-free\n":"square-free\n";
	}
};

//int main (){
//	SquareFreeString x ;
//
//	cout <<x.isSquareFree("")<<"\n";
//	return 0 ;
//}

and here's my code for the 500 Div2

~~~~~ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.*;

public class SortingSubsets {

static int getMinimalSize(int[] a) {
    int b[] = new int[a.length];
    for (int i = 0; i < a.length; ++i) b[i] = a[i];
    Arrays.sort(a);
    int cnt = 0;
    for (int i = 0; i < a.length; ++i) cnt += (a[i] != b[i]) ? 1 : 0;
    return cnt;
}

}~~~~~

Both failed at System Test , So Any help will be appreciated.

→ Reply
»
8 years ago, # |
  Vote: I like it +37 Vote: I do not like it

I was a writer this time. That's my 4th Single Round Match at TopCoder) Sorry for inconvinience in PartisanGame, I forget to add constraint that a and b are non-empty, so this case was not present at samples. Hope you liked the tasks anyway) Short editorials:

div2-easy SquareFreeString:
Just check each substring.

code

div2-medium SortingSubsets:
Which elements will remain on its own positions after sorting? Precisely this elements we will not take to our set.

code

div-2 hard ThueMorseGame:
O(n) solution using bitmasks.

code

div1-easy PartisanGame:
One can see that we win/lose on next position for Alice and Bob depends only on last five positions, so period will be not greater than 1024 (in fact, maximal period is around 20).

code

div1-medium KthStringAgain:
One can notice that strings in the collection can be obtained using following pseudocode: 

L = 0, R = |s|-1, 
res[0...(|s|-1)] (resulting string)  
from c = s[0] to s[|s| - 1] we can choose one of:  
  1. res[L++] = c  
  2. res[R--] = c  
add res to collection

Using this, we can easily calculate number of strings with given prefix.

code

div1-hard FibonacciStringSum:
This hard intended to be easier than usual.
One can notice and prove that for fixed a and b answer f(n, a, b) will be linear combination of f(n-1, a, b) ... f(n-2 * (a + b + 1), a, b).
Coefficients of linear reccurence can be found using gauss elimination or directly (say, using generating functions or other reasoning).

code
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    One can see that we win/lose on next position for Alice and Bob depends only on last five positions

    How to prove this formally?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could someone explain the solution for Div2. 900 ? Thanks.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You store the answers for last 50 states (one can use queue, but the writer has done using bit masks). I understood it. It is quite elegant. The idea is to reduce memory while the time complexity stays the same.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I can't understand your code for Div2 900...

    Could you please give some hints?Thank you very much for that.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Why do i get tle with the following O(N) solution for div2-hard ?

    Code
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      __builtin_popcount is slow. This takes 0.4 seconds in the worst case (I didn't check to see if it actually passes system test, so it may have some bug):

      Code
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      i cant understand your(fauzdar65) solution. would you mind explaining?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I move from one losing position to the next losing position. If at the end i stop at n, then its a losing position, otherwise i skip n, that means it is a winning position.

        0 is the first losing position. If X is a losing position, then surely X+1,X+2....X+m are winning positions as we can move to X. So, from X we move to X+m+1. If this number has even number of set bits, then this is the next losing position, otherwise this becomes a winning position, and next candidate for losing position is the next number i.e (X+m+1)+1 . So, we keep adding 1 till we find next losing position.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why If this number has even number of set bits, then this is the next losing position ?

          → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    One can notice and prove that for fixed a and b answer f(n, a, b) will be linear combination of f(n-1, a, b) ... f(n-2 * (a + b + 1), a, b).

    How to notice and/or prove this? I'm just trying to understand what's the intuitive way of noticing this fact and believing in it during the contest as for me the only way of thinking was to try to derive f(n, a, b) from f(n - 1,  * ,  * ) and f(n - 2,  * ,  * ) (which can be done but it requires raising 702x702 matrix to 109-th power and is most likely too slow).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      If you write y=(n-x), then you can expand (n-x)^b, so you can notice you only need the powers x^0, x^1, ..., x^(a+b).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This would be an intuitive reason to change the a, b parameters, but why does this give a recurrence on n?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Hmm, I guess I don't know the answer to that. This was more if you're looking to solve it by exponentiating a matrix, this is the most intuitive way I think.

          Is there a way to translate the matrix to a recurrence? I'm not sure if this is even possible in general.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +34 Vote: I do not like it

            Yes there is. f(n) = Anij (that is any coefficient in fixed position in matrix powers) obey recurrence relation, which coefficients are coefficents of χA (characteristic polynomial). That is follows from Cayley-Hamilton formula χA(A) = 0.
            Take

            for example.

            χA(λ) = λ2 - λ - 1.

            So,

            obey reccurence

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it +10 Vote: I do not like it

              And what is that matrix A you're talking about? It should be of size a + b. I know only the matrix of size (a+1)*(b+1)*2 (number of taken zeros, ones and the last bit).

              Upd: Well, I got the solution described above: just understand, that f(n,a,b) = sum {one^a*(n-one)^b}. So you can take the matrix of size (a+b+1)*2 (powers of taken 1s and the last bit) and the answer is weighted sum of coefficients of this vector: (A^n * v0).

              But the weights in this sum depend on n, so how do you get a recurrent?

              P.s. I solved the problem from the different angle: I need to find sum(x_i) ^ a * sum(!x_i)^b, so need to count number of ways to choose not intersecting multisets of sizes a and b, so I just counted the answer for n,a,b with the first and the last bits fixed. After that I split n in two parts and check that both middle bits are not equal to 1. I got accepted with n -> [n/2], [(n+1)/2], and so I needed map, but actually if you divide n into (2^r) > (n — 2^r), than you don't need any map, and it works in log(10^9) * a^2*b^2.

              → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I have a question about div1 300 ptr. I failed that problem because I did not cover the special case when the vector was empty. Was not mentioning that fact explicitly and not add it to examples done on purpose?

    Also the wording in the constraints was confusing for me and I did not think about empty vector at all.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      That is kind of accident and totally not on purpose, I'm sorry for that.

      There was one more constraints like "a will contain between 1 and 5 elements, inclusive." Then I guess Arterm notice "all number in a will be distinct" + "all number in a will be between 1 and 5" can imply this, so he removed that constraint.

      It can be confusing but we think empty set is valid based on this: https://en.wikipedia.org/wiki/Vacuous_truth

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the answer. I just want to make sure that I do understand correctly:

        1. You wanted to make the vectors non empty explicitly.
        2. You thought that the other 2 constraints assure that, so you removed that constraint.
        3. You did not add a checker for empty vectors test cases.
        4. Author's solution was working correctly on empty vectors.
        5. Somebody created challenges with empty vectors and you decided that in fact these 2 constraints allow empty vectors. So you left results as is?
        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, your understanding is right.

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, that's my fault. I commented two constraints to remove "redundancy". When cgy4ever noticed that it was too late to do anything.

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain me solution of div 2 hard by bitmask?

    → Reply
»
8 years ago, # |
  Vote: I like it +44 Vote: I do not like it

I added a quick editorial on the site: https://apps.topcoder.com/wiki/display/tc/SRM+701

Just wondering, do people find these useful? (i.e. on the actual site as opposed to a comment on CF) I just happened to do this one and 700 because I was involved in preparing the rounds. It seems the view counts are relatively low.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +11 Vote: I do not like it

    Yes, they are valuable. But it's hard to find them.
    Thank you for giving an explicit link!

    And if it is possible, could you add a few more sentences after the sentence: Namely, a number is winning if and only there exists a losing number. ? :)
    I don't understand what that means exactly.

    → Reply
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Best code ever :D

https://community.topcoder.com/stat?c=problem_solution&rm=329368&rd=16822&pm=14413&cr=22263204

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 hard is a kind of Bash Game.But when I used TC test,I found that data 499... 1 run 2.4s~2.7s,so I just bruteforce when m==1.When m==2,it runs 1.7s :)

→ Reply