Topcoder Single Round Match 701

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
29:02:32
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 31:12:31

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	151

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Topcoder Single Round Match 701

Автор 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 .

topcoder, srm

memset0
8 лет назад
66

Комментарии (57)

Показать архивные | Написать комментарий?

Nickolas

8 лет назад, # |

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

→ Ответить

anakot

8 лет назад, # ^ |

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.

→ Ответить

vatsal

8 лет назад, # ^ |

+19

What's the criteria for getting t-shirts?

→ Ответить

Errichto

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.

→ Ответить

memset0

8 лет назад, # ^ |

+25

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

→ Ответить

fetetriste

8 лет назад, # ^ |

+31

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

→ Ответить

cgy4ever

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.

→ Ответить

I_love_Hoang_Yen

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?

→ Ответить

anakot

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.

→ Ответить

sidchelseafan

8 лет назад, # |

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.

→ Ответить

ladpro98

8 лет назад, # |

+18

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

→ Ответить

ffao

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

→ Ответить

Sandip_Jana

8 лет назад, # |

How to solve div2 900 problem ?? Any hints

→ Ответить

IfPossibleAgainInTheLife

8 лет назад, # |

How to solve Div2 900?

I saw only one person who passed all tests.

→ Ответить

Sandip_Jana

8 лет назад, # ^ |

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

→ Ответить

memset0

8 лет назад, # ^ |

Active contests -->>> SRM 701 --->>> Division summary

→ Ответить

Sandip_Jana

8 лет назад, # ^ |

got it. thanks..

→ Ответить

Djok216

8 лет назад, # |

How to solve div1 300 ?

→ Ответить

satyaki3794

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

→ Ответить

k0st1a

8 лет назад, # ^ |

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

→ Ответить

satyaki3794

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

→ Ответить

Nams

8 лет назад, # ^ |

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?

→ Ответить

satyaki3794

8 лет назад, # ^ |

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.

→ Ответить

BicameralMind

8 лет назад, # ^ |

← Rev. 2 →

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

#include <bits/stdc++.h>

using namespace std;

int dp[2][200]; int mask[100];

class PartisanGame { public: string getWinner(int n, vector a, vector b) {

memset(mask, 0, sizeof(mask));

    dp[0][0] = dp[1][0] = false;
    for(int i=1; i<200; i++) {
        dp[0][i] = dp[1][i] = false;
        for(int j=0; j<a.size(); j++) {
            if(a[j]<=i && !dp[1][i-a[j]]) {
                dp[0][i] = true;
            }
        }
        for(int j=0; j<b.size(); j++) {
            if(b[j]<=i && !dp[0][i-b[j]]) {
                dp[1][i] = true;
            }
        }

    }
    int sz = 5, len;

    for(int i=0; i<195; i++) {
        int nw = 0, k=0;
        for(int j=i+sz-1; j>=i; j--, k++) {
            if(dp[0][j]) {
                nw+=(1<<k);
            }
        }
        if(mask[nw]) {
            len = i-mask[nw];
            break;
        } else {
            mask[nw] = i;
        }
    }

    if(dp[0][n%len]) {
        return "Alice";
    }  else {
        return "Bob";
    }

}

};

→ Ответить

royappa

8 лет назад, # ^ |

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

→ Ответить

satyaki3794

8 лет назад, # ^ |

165 is enough. No special reason for 1e5.

→ Ответить

anh1l1ator

8 лет назад, # ^ |

← Rev. 2 →

Is this correct?

Code

#include<bits/stdc++.h>
using namespace std;
class PartisanGame
{
	public:
	string getWinner(int N, vector <int> a, vector <int> b);
};

string PartisanGame::getWinner(int N, vector <int> a, vector <int> b)
{
	string ret1 = "Alice";
	string ret2 = "Bob";
	vector < int > f(1<<21,0) , g(1<<21,0) , fail(1<<21,0);
	int j = 0 , i ;

	for(i=1;i<f.size();++i){
		for(auto &v:a)
			if(i>=v)
				f[i] = f[i] || !g[i-v];
		for(auto &v:b)
			if(i>=v)
				g[i] = g[i] || !f[i-v];
		if(i!=1){
			while(j && f[j+1]!=f[i])j = fail[j];
			if(f[i]==f[j+1])++j;
			fail[i]=j;
		}
	}
	int period = f.size()-1-j;
	--N;
	N%=period;
	return f[N+1]?ret1:ret2;
}

→ Ответить

Omar_Morsi

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.

→ Ответить

Arterm

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

class SquareFreeString():
	def isSquareFree(self,s):
		return any((lambda w: len(w)%2 == 0 and w[:len(w)/2] == w[len(w)/2:])(s[i:i+j]) for j in range(1,len(s)+1) for i in range(len(s)-j+1)) * "No" or "Yes"

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

code

  public static int getMinimalSize(int[] a) {
    int n = a.length;
    int[] b = new int[n];
    for (int i = 0; i < n; ++i)
      b[i] = a[i];

    Arrays.sort(b);

    int ans = n;
    for (int i = 0; i < n; ++i)
      if (a[i] == b[i])
        --ans;

    return ans;
  }

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

code

  public static String get(int n, int m) {
    long full = (1l << m) - 1;
    long mask = full;

    for (int i = 0; i <= n; ++i) {
      int win;
      if (Integer.bitCount(i) % 2 == 1 || mask != full)
        win = 1;
      else
        win = 0;

      mask = ((mask << 1) | win) & full;
    }
    
    return (mask & 1) == 1 ? "Alice" : "Bob";
  }

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

class PartisanGame():
	def getWinner(self,n,a,b):
		a = list(a)
		b = list(b)
		if n == 0: return "Bob"
		MAXK = 5
		lw = (1<<(MAXK<<1))
		def getNext(mask):
			amask = mask >> MAXK
			bmask = mask & ((1<<MAXK)-1)
			winA = not all(bmask&(1<<(MAXK-w)) for w in a)
			winB = not all(amask&(1<<(MAXK-w)) for w in b)
			amask = (amask>>1) | (winA << (MAXK-1))
			bmask = (bmask>>1) | (winB << (MAXK-1))
			return (amask << MAXK) | bmask
			
		def mult(p,q):
			return [p[q[i]] for i in xrange(lw)]

		perm = [getNext(i) for i in xrange(lw)]
		ret = [i for i in xrange(lw)]

		n += 1
		while n > 0:
			if n % 2 == 1:
				ret = mult(ret, perm)
			perm = mult(perm, perm)
			n >>= 1

		return (ret[lw-1] >> (2*MAXK-1)) * "Alice" or "Bob"

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

public static long count(String s, String p) {
    int n = s.length();
    int m = p.length();
    long[][] d = new long[n + 1][n + 1];

    d[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= i; ++j) {
        int l = j;
        int r = n - 1 - (i - j);

        if (l >= m || s.charAt(i) == p.charAt(l))
          d[i + 1][j + 1] += d[i][j];

        if (r >= m || s.charAt(i) == p.charAt(r))
          d[i + 1][j] += d[i][j];
      }
    }

    long ans = 0;
    for (int j = 0; j <= n; ++j)
      ans += d[n][j];

    return ans;
  }

  public static String getKth(String s, long k) {
    --k;
    int n = s.length();
    String ans = "";

    for (int i = 0; i < n; ++i) {
      for (char c = 'a'; c <= 'z'; ++c) {
        String p = ans + Character.toString(c);

        long cnt = count(s, p); 
        if (cnt <= k) {
          k -= cnt;
        } else {
          ans = ans + Character.toString(c);
          break;
        }
      }
    }
    
    return ans;
  }

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

  public static int add(int x, int y) {
    x += y;
    if (x >= mod)
      x -= mod;
    return x;
  }

  public static int sub(int x, int y) {
    x -= y;
    if (x < 0)
      x += mod;
    return x;
  }

  public static int mul(int x, int y) {
    long p = (long) x * (long) y % mod;
    return (int) p;
  }

  public static int binpow(int x, int to) {
    int y = 1;
    while (to > 0) {
      if ((to & 1) == 1)
        y = mul(x, y);
      x = mul(x, x);
      to >>= 1;
    }
    return y;
  }

  public static int inv(int x) {
    assert(x != 0);
    return binpow(x, mod - 2);
  }

  private static class Matrix {
    int n;
    int[][] a;

    public Matrix(int size) {
      n = size;
      a = new int[n][n];
    } 

    public Matrix one() {
      Matrix ans = new Matrix(n);
      for (int i = 0; i < n; ++i)
        ans.a[i][i] = 1;
      return ans;
    }

    public Matrix mul(Matrix other) {
      Matrix ans = new Matrix(n);
      for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k)
          for (int j = 0; j < n; ++j)
            ans.a[i][j] = add(ans.a[i][j], FibonacciStringSum.mul(a[i][k], other.a[k][j]));
      return ans;
    }
  }

  public static Matrix binpow(Matrix x, int to) {
    Matrix y = x.one();
    while (to > 0) {
      if ((to & 1) == 1)
        y = y.mul(x);
      x = x.mul(x);
      to >>= 1;
    }
    return y;
  }

  public static int[] getCoefficients(int n) {
    int[] a = new int [2 * n + 1];
    a[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 2 * n; j >= 0; --j) {
        int nw = sub(0, a[j]);
        if (j >= 1)
          nw = sub(nw, a[j - 1]);
        if (j >= 2)
          nw = add(nw, a[j - 2]);
        a[j] = nw;
      }
    }
    return a;
  }

  public static int[] getSequence(int cnt, int a, int b) {
    int[] fact = new int[cnt + 1];
    int[] ans = new int[cnt];
    fact[0] = 1;
    for (int i = 1; i < fact.length; ++i)
      fact[i] = mul(i, fact[i - 1]);

    BiFunction<Integer, Integer, Integer> binom = (Integer n, Integer k) -> {
      if (n < 0 || k < 0 || n < k)
        return 0;
      int res = fact[n];
      res = mul(res, inv(fact[k]));
      res = mul(res, inv(fact[n - k]));
      return res;
    };

    for (int n = 0; n < cnt; ++n) {
      for (int k = 0; 2 * k - 1 <= n; ++k) {
        int bon = binom.apply(n - k + 1, k);
        bon = mul(bon, binpow(k, b));
        bon = mul(bon, binpow(n - k, a));
        ans[n] = add(ans[n], bon);
      }
    }

    return ans;
  }

  public static int get(int n, int a, int b) {
    int m = a + b + 1;
    int[] c = getCoefficients(m);
    int depth = c.length - 1;

    Matrix A = new Matrix(depth);
    for (int i = 0; i < depth; ++i)
      A.a[0][i] = sub(0, c[depth - i - 1]);
    for (int i = 1; i < depth; ++i)
      A.a[i][i - 1] = 1;

    A = binpow(A, n);

    int[] seq = getSequence(depth, a, b);

    int ans = 0;
    for (int i = 0; i < depth; ++i)
      ans = add(ans, mul(A.a[depth - 1][i], seq[depth - i - 1]));

    return ans;
  }

→ Ответить

k0st1a

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?

→ Ответить

sidchelseafan

8 лет назад, # ^ |

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

→ Ответить

bhikkhu

8 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

IfPossibleAgainInTheLife

8 лет назад, # ^ |

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

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

→ Ответить

IfPossibleAgainInTheLife

8 лет назад, # ^ |

+10

Finally I understand it.

Very nice problem. Thank you~

→ Ответить

fauzdar65

8 лет назад, # ^ |

+11

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

Code

string get(int n,int m)
{
    int currl = 0;
    while(currl + m + 1 <= n)
    {
       currl+= m + 1;
       while(currl<=n && (__builtin_popcount(currl) & 1))++currl;
    }
    if(currl == n)return "Bob";
    return "Alice";
}

→ Ответить

ffao

8 лет назад, # ^ |

← Rev. 3 →

__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

int popc[66000];

int popcount(int x) {
	return popc[x & 0xffff] + popc[(x>>16) & 0xffff];
}

string ThueMorseGame::get(int n,int m)
{
	popc[0] = 0;
	for (int i = 1; i < (1<<16); i++) popc[i] = popc[i & (i-1)] + 1;
    
    int currl = 0;
    while(currl + m + 1 <= n)
    {
       currl+= m + 1;
       while(currl<=n && (popcount(currl) & 1))++currl;
    }
    if(currl == n)return "Bob";
    return "Alice";
}

→ Ответить

fauzdar65

8 лет назад, # ^ |

Yeah , it passes now :(

→ Ответить

bhikkhu

8 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

fauzdar65

8 лет назад, # ^ |

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.

→ Ответить

nuradil

8 лет назад, # ^ |

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

→ Ответить

KADR

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 10⁹-th power and is most likely too slow).

→ Ответить

Lewin

8 лет назад, # ^ |

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

→ Ответить

ffao

8 лет назад, # ^ |

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

→ Ответить

Lewin

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.

→ Ответить

Arterm

8 лет назад, # ^ |

+34

Yes there is. f(n) = Aⁿ_ij (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

$\text{[math]}$

for example.

χ_A(λ) = λ² - λ - 1.

So,

$\text{[math]}$

obey reccurence

$\text{[math]}$

→ Ответить

-XraY-

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.

→ Ответить

P___

8 лет назад, # ^ |

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.

→ Ответить

cgy4ever

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

→ Ответить

P___

8 лет назад, # ^ |

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

You wanted to make the vectors non empty explicitly.
You thought that the other 2 constraints assure that, so you removed that constraint.
You did not add a checker for empty vectors test cases.
Author's solution was working correctly on empty vectors.
Somebody created challenges with empty vectors and you decided that in fact these 2 constraints allow empty vectors. So you left results as is?

→ Ответить

cgy4ever

8 лет назад, # ^ |

Yes, your understanding is right.

→ Ответить

Arterm

8 лет назад, # ^ |

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

→ Ответить

nuradil

8 лет назад, # ^ |

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

→ Ответить

Lewin

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.

→ Ответить

egor.okhterov

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.

→ Ответить

Lewin

8 лет назад, # ^ |

Sorry, I missed some words. I added a few more.

In general, all editorials can be found here: https://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis

They haven't been kept up to date in the past few months, so that's probably why you can't find some.

→ Ответить

Al.Cash

8 лет назад, # |

+24

Best code ever :D

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

→ Ответить

Ray4ever

8 лет назад, # |

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.12.2024 12:32:29 (i1).

Десктопная версия, переключиться на мобильную.

При поддержке