| Show all threads Hide all threads Show all messages Hide all messages |
| WA1. Is first test different, or it's problem with IO? | Ionkin M [Samara SAU #617] | 1142. Relations | 19 Sep 2020 00:49 | 2 |
I have correct answer at least on first test, but I got WA1! Why? Is first test different with a test in a problem's description?
I write each line of my answer via Scala println (similar with Java), and read with StdIn.readLine.
Edited by author 25.08.2019 19:14
Edited by author 25.08.2019 19:15 |
| Sterling number of second kind | Rishabh Jain | 1142. Relations | 3 Sep 2020 18:30 | 1 |
|
| Any Help/Hint | Amil Khare | 1142. Relations | 27 Sep 2017 15:33 | 5 |
Hello,
I am not that strong in DP but I have been trying hard to understand the problem. I tried coming up with a solution however got WA. I cannot completely understand the hints given before, PLEASE HELP !!! There are two dp-approaches already described on the webboard So I have accepted with dp
I have two dp
Stirling numbers of the second kind and factorial
Then precalculate answer array I have seen the 2 DP solutions however I still don't understand how do they arrive at the relation?
Can you describe in detail if possible, Please ! There are X groups consisting of equal numbers. X=1,2,..n. What does it mean, to put some '<' and '>' signs between them? It is just to define some order relation. Just assign one group as the greatest, another group as the second greatest etc. So we find number of ways to make groups and multiply it by number of ways to make ordering https://ideone.com/00UUdf |
| thanks for interesting task | kasarino | 1142. Relations | 24 Jan 2015 14:01 | 1 |
Thanks to the author for the interesting task in combinatorics and integer partitioning! |
| combinatorics | staticor | 1142. Relations | 4 Jul 2013 20:32 | 1 |
use DP, mainly involved with:
permutation and combination
A(n,k)
C(n,k)
or, you can think about there is a x-Axis.
two points (a, b) can be placed --a--b-- --b--a-- || --(ab)-- the first two solution has two groups, and the last one has one groups for the overlap.
|
| Some hint for you (Very exciting problem, although it's easy at the first time). | Phan Hoài Nam (Harvey Nash) | 1142. Relations | 16 Oct 2012 11:29 | 2 |
Let a be the number of objects.
Let b be the number of objects in a group.
Let A[a] is the number of permutations of a objects ( A[2] = 2, A[3] = 2*3, A[4] = 2*3*4...)
So:
f[a][b] is the number of groups with b objects.
You have the formula:
f[a][b] = f[a-1][b] * b + f[a-1][b-1];
And the result = f[n][1] * A[1] + f[n][2] * A[2] + ... + f[n][3] * A[3]
A group is formed by equal objects in a relation.
For example:
a = b < c = d (2 groups ab and cd)
a = b < c < d (3 groups ab, c and d)
...
I think when N is increased to 1000, everyone will solve it by DP or maths, not cheat :-)
thank you for your idea.
I had learnt a lot from yours. |
| Can be this case? a=b<c=d<e=f. | Hrayr | 1142. Relations | 13 Jan 2012 03:42 | 3 |
Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com Yes, you can have this case.
Your hint has helped my solve the problem.
KEYWORDS: Stirling numbers of 2nd kind, Factorial |
| Whats wrong with my formula? | Dijkztra | 1142. Relations | 18 Oct 2010 18:12 | 3 |
z = fact(z)/(2*pow(log(2),n+1));
if(fmod(z,1)>=0.5) z = floor(z) + 1;
else z = floor(z);
I tried the example test case and got true, but got WA with 1st test case... T_T I sent your formula and got AC. Try to output answer so:
cout << fixed << setprecision(0) << z;
or so:
printf("%.0lf",z);
And you must use double instead of float function g(x,k:longint):comp;
var i:longint; q:comp;
begin
q:=1;
for i:=1 to k do q:=q*i;
g:=q*x;
end;
var
f:array[0..20,0..20] of longint;
a:array[0..20] of comp;
i,j,n,k:longint;
begin
for i:=0 to 10 do begin f[i,1]:=1; f[i,i]:=1; end;
f[0,1]:=0;
for i:=1 to 10 do
for j:=2 to i-1 do f[i,j]:=f[i-1,j-1]+f[i-1,j]*j;
for i:=2 to 10 do
for j:=1 to 10 do a[i]:=a[i]+g(f[i,j],j);
readln(n);
while n>0 do
begin
writeln(a[n]:0:0);
readln(n);
end;
end. |
| How to count? | Pier Paolo Guillen Hernandez | 1142. Relations | 26 Jul 2010 16:31 | 4 |
Any hint on how to count all relations?
Thanks! use DP. your function will be F(n, k) where N is the amount of number in the relation and K is the number of groups.
For example:
a=b=c=d - 1 group
a=b<c=d - 2 groups
a<b<c<d - 4 groups
equal numbers form one group.
Edited by author 09.05.2005 05:40 It's a maths problem. Like that puting N balls into M boxes.
Edited by author 28.01.2008 07:01 Thank you! The idea of puting balls into boxes helped me. |
| Hint(+) | Smusenok Sergiy Andriyovich (KhAI) | 1142. Relations | 28 Aug 2009 15:48 | 1 |
Hint(+) Smusenok Sergiy Andriyovich (KhAI) 28 Aug 2009 15:48 You must use PolyLogaryphm, formula a[n]=1/2*PolyLog[-n,1/2];
P.S. AC 0.015 229 kb |
| what's the answer of 5 = =" | suckychild | 1142. Relations | 28 Jan 2008 08:43 | 2 |
what's the answer of 5 = =" Can u tell me..?
I have no hint.. T_T
Can i accept by use relation of sequence? |
| What is answer for N = 4? | Nikolai Sakharnykh | 1142. Relations | 5 Dec 2007 20:26 | 3 |
75 (-) shitty.Mishka 26 Jan 2002 14:31 |
| Please help me if 2<n<100!!! | CLASSIC | 1142. Relations | 30 Mar 2007 10:57 | 2 |
Please help me if 2<n<100!!! There is a recurrence relation for these numbers.
something like
a(n+1) = 1 + sum {k=1,k=n; binomial(n+1, k)*a(k)} |
| What's the output for n=10? (-) | asif | 1142. Relations | 1 May 2005 15:58 | 2 |
|
| Why does my program not work? | Teh Ming Han | 1142. Relations | 1 May 2005 15:57 | 2 |
// USU Problem 1142
// Relation
// Done by Teh Ming Han
#include <iostream.h>
int main(){
int i,n;
unsigned long fact[10];
fact[1] = 1;
for (i=2;i<=10;i++)
fact[i] = fact[i-1]*i;
while (!cin.eof()){
cin>>n;
if (n>=1) cout<<(fact[n]*(n-1))+1<<endl;
else break;
}
return 0;
} the problem is not in your code. your idia is wrong.
i looked at your sors. it will only work when there is only one sign '='.
Edited by author 01.05.2005 16:01 |
| Hint for this problem? | Marko Tintor (marko@pkj.co.yu) | 1142. Relations | 14 Mar 2003 16:29 | 3 |
got AC! Marko Tintor (marko@pkj.co.yu) 22 Jul 2002 16:08 > >email at"daniciuc_marian@yahoo.com" |
| Some Useful hint is here... anyone view: | Locomotive | 1142. Relations | 11 Feb 2003 12:35 | 1 |
HI all
For solving this problem use dynamic programming
as this way:
for finding answer of k... do it:
for i:=1 to k do
f[k]:=f[k]+c(i,k)*f[k-i];
which c(i,k) is amount of ways to choose i thing from k thing:
c(i,k)= k! / (i!*(k-i)!)
ans its proof is:
variable i is amount of '='s that use
if 1time '=' use then it we should choose 2 operand in both sides of
= operator
and if 2= uses then we should chose 3operand (form k operand that we
have)...
ans etc.
mail me for more explaination:
aidin_n7@hotmail.com
|
| what's the answer for N=4 and N=10 ? | Elielson Barbosa Rodrigues | 1142. Relations | 29 Dec 2002 21:53 | 4 |
|
