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

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

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 .

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    What's the criteria for getting t-shirts?

»
8 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +83 Проголосовать: не нравится

    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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div2 900 problem ?? Any hints

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 900?

I saw only one person who passed all tests.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve div1 300 ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

              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
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Is this correct?

    Code
»
8 лет назад, # |
  Проголосовать: нравится -39 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    Code
    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

      __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
    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +16 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +34 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

              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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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