11394 - Digit Blocks
Moderator: Board moderators
11394 - Digit Blocks
who can give me some hint for this problem?
I always got TLE by backtracking + combinatorics.
what is the optimal algorithm?
I always got TLE by backtracking + combinatorics.
what is the optimal algorithm?
I love this kind of problems!
I should have participated in the contest.. Forgotten the contest time...... I would have solved 9 problems (haven't read F yet).

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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
How could I speed up this code?
I kinda dislike how I am doing it, but ...
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;
}
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.
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.
I am getting WA, can someone verify following outputs
Input
output
Input
Code: Select all
555AAA
55AA
5A
55AAFF
5AF
12345
#
Code: Select all
68
18
4
270
15
161
So is there any tricky case, like empty line in input?
Some more I/O from my WA code
input
output
Some more I/O from my WA code
input
Code: Select all
AAAAAAAAAAAAAA
A
AA
AAAAAAAAAAAAAAAA
AAAAA55555FFFFF
AAAAA5555FFFFF55
123456789ABCDEF
123456789ABCDEF5
1123456789ABCDEF
#
Code: Select all
14
1
2
16
2435199
6529444
1682843078091
14096761539970
1743530301000
I dont know tricky cases... but my program now gives:
gl! Eric.
Code: Select all
14
1
2
16
2435199
6529444
1757073698223
14635897285138
4133746960368