cgy4ever's blog

By cgy4ever, history, 3 years ago, In English,

As Errichto suggested here, I will post date/time of upcoming SRMs once I know, and will update it about 24 hours before the contest so it will be in the "Recent Actions" list.

SRM 702 will start on Nov 14 at 9pm EST. Note that Daylight Saving Time will end on Nov 6.

This is the last SRM before Topcoder Open 2016, so please come and compete if you want to practice once more. :)

Update: the contest will start in less than 1.5 hours.

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

»
3 years ago, # |
  Vote: I like it +125 Vote: I do not like it

Update: SRM 702 will start in 24 hours.

»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it
  1. Woke up at 5:00
  2. A connection to the server could not be established

Will be fun to get this on TCO.

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

    I'm sorry, looks like my internet provider blocks arena :(

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

How to Solve div2 1000 points problem?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -35 Vote: I do not like it

    What I did is as follows :

    Made a recursive function with memorization (Dynamic Programming), which will return expected value given a subset of block (call it mask) and the face vector.

    For each subset I calculated the result when a particular faces comes up with probability equal to 1/face.size() and for this face removed a subset, which sums to the number on this face, from mask, which will be most favorable (meaning which enable us create most of the numbers on the faces after removing the face).

    I am NOT passing all testcases with this approach. Passing 6 out 7 given test cases.

    Can anyone please explain where I am going wrong ?

    Here is my code if you would like to have a look :

    #include <iostream>
    #include <vector>
    #include <set>
    #include <map>
    #include <algorithm>
    
    using namespace std;
    
    int test = 0;
    
    class SubsetSumExtreme{
    	public :
    		int subset[4100];
    		int perms[4100];
    		double dp[4100];
    		double getExpectation(vector <int> block, vector <int> face, int mask){
    			if(dp[mask]!=-1.0) return dp[mask];
    			double ans = 0.0;
    			double n = (double)(face.size());
    			int len_block = block.size();
    			for(auto f : face){
    				map < int, vector <int> > mp;
    				for(int i = 0; i<(1<<len_block); i++){
    					if((mask | i) == mask){
    						if(subset[i]==f) mp[perms[mask-i]].push_back(i);
    					}
    				}
    				if(mp.size()){
    					for(auto p : mp.rbegin()->second){
    						ans += getExpectation(block,face,mask-p)/n/mp.rbegin()->second.size();
    					}
    				}else{
    					double z = 0.0;
    					for(int i = 0; i<(len_block); i++){
    						if(mask & (1<<i)) z+= block[i];
    					}
    					ans += z/n;
    				}	
    			}
    			return dp[mask] = ans;
    		}
    		
    		double getExpectation(vector <int> block, vector <int> face){
    			sort(face.begin(),face.end());
    			sort(block.begin(),block.end());
    			int len_block = block.size();
    			for(int i = 0; i<(1<<len_block); i++){
    				int sum = 0;
    				for(int j = 0; j<(len_block); j++){
    					if(i & (1<<j)) sum += block[j];
    				}
    				subset[i] = sum;
    				//cerr<<i<<" "<<sum<<endl;
    			}
    			for(int i = 0; i<(1<<len_block); i++){
    				int count = 0;
    				for(int j = 0; j<(1<<len_block); j++){
    					if((i | j) == i){
    						if(binary_search(face.begin(),face.end(),subset[j])) count++;
    					}
    				}
    				perms[i] = count;
    				//cerr<<i<<" "<<count<<endl;
    			}
    			for(int i = 0; i<(1<<len_block); i++) dp[i] = -1.0;
    			return getExpectation(block,face,(1<<len_block)-1);
    		}
    };
    
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't understand the problem , didn't get the part about finding the minimum expected score . Can someone explain why the answer for {1,2,1} , {1,2} is 0.5 ?

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

      Imagine you are Bob and you rolled a 2 in the first round. You can now either discard two 1s or you can discard a single 2. What should you do? Clearly, it's better to discard the 2. If you don't see it yet, let's examine what happens in both cases:

      If you are left with the blocks {1,1}: Regardless of what you roll next, you will be able to discard some more blocks. If you roll a 2 next, you will discard everything. If you roll a 1 followed by a 1, you will discard everything. And if you roll a 1 followed by a 2, you will discard one of the blocks and then the game will end with score 1. The expected score in this case is (1/4)*1 = 0.25.

      If you are left with the block {2}: If your next roll is a 1, your game is over and your score is 2. If your next roll is a 2, you discard the block and your game will then end with score 0. In this case, your expected score is (1/2)*2 = 1, which is way worse.

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

What's the point in div1 500? Was the intended solution different from what most people have submitted?

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

    The intended solution is like most submission.

    Maybe it is too much like a brain teaser, but I think it is still legit to use it — at least it is kind of novel and the result (pass rate and score distribution) looks good.

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

      I guess the main thing was to notice that it's not the same as correct bracket sequence in usual understanding. I was ready to start coding dp solution for usual correct bracket sequence but was lucky enough to decide to double-check the statement first as the it looked too suspicious. I think more people would've solved this problem if there was an example with some short string like "()(())" saying it's not "good" by the definition from the statement.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve div1 1000pts?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +30 Vote: I do not like it

    First, let's binary search for answer. So problem reduces to finding if there exists a happy sublist with length at least m and value k.

    For each number, we can compute the closest index on the left that has absolute value at most k, and the closest index on the right that has absolute value at most k.

    For example, if the list is equal to [8,1,10,2,9,7], and k=2, then left = [-1,-1,0,1,2,4], and right = [2,3,4,6,5,6]. This is a pretty standard problem and can be solved using some binary indexed trees and takes O(n log n) time.

    Now, consider the following pseudocode to check if all sublists are not happy:

    def all_bad(s, e):
      if e-s <= m: # all subarrays are too short, so they are all bad
        return true
      find an index i such that left[i] < s and right[i] > e
      if no index exists: # all numbers are not lonely if we take the entire subarray
        return false
      # any subarray that contains index i will be bad, so we just need to check the two cases below.
      return all_bad(s, i-1) and all_bad(i+1, e)
    

    This is correct, but it is too slow. In particular, the line for finding the index is too slow if we try the straightforward loop from s to e. Instead, let's just scan from both ends simultaneously. This now becomes O(n log n) (basic idea is the recurrence is now T(n) = T(a) + T(b) + min(a,b)).

    Overall time complexity is O(n log^2 n).

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

      Thanks so much.By the way,the idea to scan from both ends simultaneously is so fantastic!

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Finding left and right via offline processing using sets in nlogn gives TLE: http://ideone.com/K9Jdoo on test case #35.

      So, nlog^2(n) had to be implemented carefully?

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I missed a lot of SRMs in the last 2 months. I think you should post the announcement of upcoming SRM 48 hours before it starts, and push the blog on top of recent actions again 24 hours later. Thank you very much for your reliable reminder :)

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

I will post date/time of upcoming SRMs once I know

Is there any possibility to subscribe to these notifications via email?

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

    You can sign up for the TopCoder Newsletter. You get all the information about upcoming contests (SRMs, Marathon etc) in advance, at least I do.

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

      Newsletter reports about upcoming SRM in about 24 hours.