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

TopCoder SRM 632
Автор I_love_tigersugar, 10 лет назад, По-английски

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.

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

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

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

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

    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.

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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?

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

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 ?

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

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

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

Could you please explain a DP in div1-hard?

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

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

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

    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.

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

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

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

      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

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

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

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

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.

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

    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

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

    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?

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

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

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

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

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

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

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

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

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

    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

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

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?

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

    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.

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

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 ;

   }

};``
→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

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

    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.

    → Ответить