I_love_tigersugar's blog

TopCoder SRM 632
By I_love_tigersugar, 10 years ago, In English

Tommorow, the SRM 632 will be held at 7:00 EDT. This is the last chance for you to use the web arena and be able to win TC prizes (a trip to TCO14 or a T-shirt!). Don't forget to use the web arena and "test your luck".

I wish you would be "lucky enough" to win prizes!he

Happy coding.

P/s: The SRM schedule of this year is fully updated.

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

»
10 years ago, # |
  Vote: I like it +47 Vote: I do not like it

I_love_tigersugar is a lot more reliable at reminding me of SRMs than topcoder's email reminders...

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

    Oh really? I always save all programming contest events in my phone's calendar and it always reminds me one day before each contest. I don't usually check for new email so I don't know when they send email about upcoming contest.

    Btw, sorry for any inconvenience.

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

Hey! Quick question for Java-Guru Topcoders: when I run "javaws ContestAppletProd.jnpl" in terminal, applet creates two configuration files in my home directory *.conf and *.conf.bak. How can I avoid such behavior? Can I set location of these files in command line of Java Web Start?

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

When I try to open arena (file ContestAppletProd.jnlp) in ubuntu using Iced Tea I got this error , I tried to press "clean all cache" but it's unable to delete the cache , How can I fix it ?

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

    Same problem. However, I managed to clean cache after rebooting computer. Didn't help.

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

      I tried to reboot but still unable to delete the cache :(

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

        Now it works. No idea what happened.

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

    I am an ubuntu newbie, but typing "ControlPanel" in terminal and deleting temporary Java files in "Temporary files setting" helped me.

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

    You should try command "javaws -Xclearcache" to clear cache.

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

Tried web client of arena. Looks fine, but problems were listed in wrong order (medium — small — large). Damn.

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

Could you please explain a DP in div1-hard?

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

    Key observation: you can delete the node after you visit it. Let's create the sequence from the end. Let DP[i][j] be the number of ways to create a pattern and end up with i nodes in first row and j nodes in second row, while you start from the first row. Transitions: you got here from the other row ((j + 1)·DP[j + 1][i]) or from one of two neighbors in the same row (2·DP[i + 1][j]). Answer is 2·DP[1][0].

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

    First thing to notice is that all configurations of x unused dots in a row are equivalent, because you can only move to the next dot to the right or left anyway.

    Let s(x, y) be the number of ways you can make a pattern, if you have x unused dots in first row, y unused dots in second row, and you can be anywhere in first row.

    You can move to the left or right in the first row, either of this leads you to s(x-1, y). So sum 2*s(x-1, y) to answer.

    You can also go to the second row, this brings you to s(y, x-1). Remember you can be anywhere on first row, so add x * s(y, x-1) to answer.

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

      what's the meaning of “you can be anywhere on first row”?I have got it.

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

      I don't get how this part works:

      _ You can move to the left or right in the first row, either of this leads you to s(x-1, y). So sum 2*s(x-1, y) to answer._

      How about when n=2? You van only go one direction, as there aren't two neighbours in the same row for any node

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

        Say you are calculating s (2,2) , so you can be in 2 different positions in first row.

        If you are in the right position and move left, you can now only be in a single position in first row, so s (1,2).

        If you are in the left position an move right, you can only be in the right position, so you get s (1,2).

        The total is still 2*s(1,2). What you may have missed is that the edges are already accounted for when you move left and get s(x-1, y), that is, you can only move left from x-1 different positions (the "-1" is the edge, and you can't go left from there).

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

I solved div1 medium using DSU and passed system test , Who too solved it using DSU? I think it's not the intended solution because it quite strange solution and I couldn't prove it , see my code it's quite clear.

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

    It is rather easy to see that you basically add edge to graph from end to start and you do not add edges that would make 0 and N — 1 connected, but add theit cost to the answer. That is the intended solution, you just make it linear while it was easier to do it in qudratic time

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

    I think it is the intended solution. Only one thing I still don't get is why the cost is 3i instead of 2i. Is the power of 2 too mainstream?

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

      Next time they should use something like 1337i or 747474i for extra coolness.

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

        Giving 3i instead if 2i is enough to make somebody fail system test because of calculating pow like x=(x*3)%MOD in integers:)

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

          Sounds like another reason to use 2i to me, do you really want someone to fail because of this?

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

            I am writer. I don't notice the potential bug. I use 3i becuase I think using 2 is too normal. I prefer unusual thing >_<.

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

            why not? and Python is always there.

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

        Or 998244353, to make people think a very bizzare FFT is necessary?

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

    DSU is what I intend exactly. Because max flow equal to min cut, we can try to find min cut instead to max flow. In a cut, points of a graph will be divide to two group. we will try to make the edge of larger costs connect the points of same group due to 3i > 31 + 32 + ... + 3i - 1

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

      Can you please explain your max flow solution in slightly more detail especially the cut part?

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

Anyone could help me out with Div2 1000? The code I have gives me TLE on only 1 of the 93 cases. Anything I could do to optimize it?

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

    I'm actually kinda surprised the bruteforce only times out for a single case.

    But you can transform it into correct solution easily: note that if your current product is not a divisor of goodValue, it's impossible to make it equal to goodValue by doing multiplications. So you should only add something to buffer when it divides goodValue.

    This code passes systests spending less than 10 ms per case.

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

What is the solution for DIV 2 HARD 1000 pts problem ? I tried it using DP in the practice , but 2 tests are getting TLE while the others passed. The reason to me seems that I use map to represent the state and in these two cases the size of the map gets very large.. Still if any one has a better approach please share it.

#include <bits/stdc++.h>
using namespace std;

#define P first
#define Q second
#define pb push_back

#define MOD 1000000007
typedef long long LL ;
typedef pair < int , int > ii ;
map < ii , int > DP ;


vector < int > A ;

int rec ( int cur , LL prod , LL GD , int size ){

	if( prod > GD)
	return 0 ; 
   
    if( prod == GD && cur > size )
    return 1 ;
   
    if( cur > size )
    return 0 ;
    
    ii state = ii(cur,prod) ;
    if( DP.count(state) == 0)
    DP[state] = -1;
    
   //cout << cur <<" "<<prod<<" "<<GD<<" "<<size << endl;
    if( DP[state] != -1)
    return DP[state] ;
    DP[state] = 0 ; 
    if( prod == 0){
            DP[state] += rec(cur+1 , 0 , GD , size) ;
		    
		    DP[state] += rec( cur+1 , A[cur], GD , size) ;
		    if(DP[state] >= MOD)
     	    DP[state] -= MOD ; 
		    
    }  
    else{
     DP[state] += rec(cur+1 , prod*A[cur] , GD , size) ;
     DP[state] += rec( cur+1 ,prod, GD , size) ;
        if(DP[state] >= MOD)
     	DP[state] -= MOD ;
    }
    return DP[state] ;
}

class  GoodSubset {
   
   public :
   int numberOfSubsets(int goodValue, vector <int> d){
      LL GD = goodValue ;
      for ( int i = 0 ; i < d.size() ;i++)
      A.pb(d[i]) ;
      bool f =true ;
      int ans = rec(0,0,GD , d.size()-1 );
      ans = ans%MOD ; 
      cout <<DP.size() << endl;
      return (int)ans ;

   }

};``
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I found my mistake , at each stage we have to ensure that the current product is a divisor of the GOODVALUE. Thanks ffao.

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

As I see, the way to solve Div2 1000 is to use Map.
Can someone tell me what is algorithm to solve that problem and how does Map help us?

Thank you

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

    People used dynamic programming to solve the problem. state dp(i,p) // i is the ith element and p is current product. Problem is p can be up to 2000000000. So we can not use such a huge memory for memoization purpose. For that people used map to save the states.

    → Reply