11394 - Digit Blocks

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

11394 - Digit Blocks

Post by pineapple » Sat Jan 12, 2008 6:18 pm

who can give me some hint for this problem?
I always got TLE by backtracking + combinatorics.
what is the optimal algorithm?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Jan 12, 2008 7:33 pm

You can apply dynamic programming on the state dp[1<<16][5];

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple » Sat Jan 12, 2008 7:35 pm

thanks very much,sohel!I will try it soon.
it looks like G,I got it in 0.060s.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Jan 12, 2008 8:35 pm

I love this kind of problems! :D

I should have participated in the contest.. Forgotten the contest time...... I would have solved 9 problems (haven't read F yet). :(
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal » Sat Jan 12, 2008 8:52 pm

sohel wrote:You can apply dynamic programming on the state dp[1<<16][5];
What is the answer if the input is "55"? Is it 2 or 4?

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

Post by luishhh » Sat Jan 12, 2008 8:55 pm

The answer for 55 is 2, the only two possibilities are 5 and 55
"From lost to the river" --> Spanish quote

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sat Jan 12, 2008 8:57 pm

jvimal wrote: What is the answer if the input is "55"? Is it 2 or 4?
My Ac program gives 2.....

gl! Eric.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal » Sat Jan 12, 2008 9:10 pm

luishhh wrote:The answer for 55 is 2, the only two possibilities are 5 and 55
okay, was wondering if the blocks are distinguishable or not :)

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal » Sat Jan 12, 2008 10:02 pm

How could I speed up this code?
I kinda dislike how I am doing it, but ... :-)

Code: Select all


#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

#define FOR(x,a,b) for(int x=(a); x<(b);x++)
#define LET(x,a) __typeof(a) x(a)
#define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define EACH(it,v) IFOR(it,v.begin(),v.end())
#define REP(i,n) for(int i=0;i<n;++i)

#define INF (0x7FFFFFFF)
#define pb push_back
#define GI ({int t; scanf("%d", &t); t;})
#define sz size()

typedef long long LL;

set<multiset<char> > vis;

int n;
char num[17];

inline int dig(char a) {
  if(a <= '9') return a-'0';
  return a-'A'+10;
}

inline multiset<char> get(int mask) {
  multiset<char> s;
  REP(i, n) if(mask&(1<<i)) s.insert(num[i]);
  
  return s;
}

LL fact[17];

LL go(int mask) {
  if(vis.count(get(mask))) return 0;
  
  multiset<char> s = get(mask);
  vis.insert(s);
  
  int count[16]; memset(count, 0, sizeof(count));
  int sum = 0;
  int c = 0;
  
  REP(i, n) if(mask & (1<<i))
    sum = (sum+dig(num[i])), count[dig(num[i])]++, c++;
  
  if(sum%5 != 0) return 0;
  LL den = 1;
  REP(i, 16) if(count[i]) den *= fact[count[i]];
  
  return fact[c]/den;
}

int main()
{
  fact[0] = 1; FOR(i,1,17) fact[i] = fact[i-1]*i;
  while(scanf("%s", num)+1) {
    if(num[0] == '#') break;
    n = strlen(num);
    vis.clear();
    unsigned long long ans = 0;
    
    FOR(i,1,(1<<n)) ans += go(i);
    
    printf("%lld\n", ans);

  }
  return 0;
}


User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jan 13, 2008 10:42 am

Hmm.. your code looks very complex.

What you need is a state dp[1<<16][5]

in the recursive fun, you need two parameters state & mod

state -> an integer that denotes the blocks which has been chosen so far.
mod -> (the number formed by concatanating the digits) % 5

In a particular depth, you have to ensure that you don't pick two blocks with the same digit. This has to be done so that we don't end up getting 2 results with the same value.

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

Post by tanaeem » Tue Jan 15, 2008 4:38 am

I am getting WA, can someone verify following outputs
Input

Code: Select all

555AAA
55AA
5A
55AAFF
5AF
12345
#
output

Code: Select all

68
18
4
270
15
161

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Tue Jan 15, 2008 4:49 am

My AC program gives the same output. gl! Eric.

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

Post by tanaeem » Tue Jan 15, 2008 4:52 am

So is there any tricky case, like empty line in input?

Some more I/O from my WA code

input

Code: Select all

AAAAAAAAAAAAAA
A
AA
AAAAAAAAAAAAAAAA
AAAAA55555FFFFF
AAAAA5555FFFFF55
123456789ABCDEF
123456789ABCDEF5
1123456789ABCDEF
#
output

Code: Select all

14
1
2
16
2435199
6529444
1682843078091
14096761539970
1743530301000

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Tue Jan 15, 2008 5:16 am

I dont know tricky cases... but my program now gives:

Code: Select all

14
1
2
16
2435199
6529444
1757073698223
14635897285138
4133746960368
gl! Eric.

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

Post by tanaeem » Tue Jan 15, 2008 5:40 am

Thanx for help, I have got AC.
There was problem in my initialization of memo.
And I have solved this using 16X16X5 memo.

Post Reply

Return to “Volume 113 (11300-11399)”