| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| About understanding of problem | Noob [NULP] | 1431. Сертификаты | 8 май 2021 12:17 | 1 |
Edited by author 21.05.2021 00:09 |
| WA #14 | Dmitri Belous | 1431. Сертификаты | 19 окт 2017 18:59 | 1 |
WA #14 Dmitri Belous 19 окт 2017 18:59 If you have WA #14 you need to know that the 14th test contains both numbers 29 and 30 in the row. Check range of numbers: [1, 30]. |
| If you have WA6 or WA7 | Evgeny Shulgin | 1431. Сертификаты | 25 мар 2015 16:26 | 1 |
See this test:
6
2 2 2 3 3 3
Bad answer: 5
Good answer: 3 |
| there is a polynolyal time solution, my is O(N^3) | Alias aka Alexander Prudaev | 1431. Сертификаты | 28 ноя 2013 00:00 | 4 |
sorting array can help improving O(N^3) to O(N^2) |
| What right answers? | Vitalik | 1431. Сертификаты | 7 июн 2012 18:31 | 4 |
My program is mistaken on 3 test!!!
Give right answers on these tests and please help me to find a mistake!
1 test:
5
5 6 7 7 4
My answer: 4
2 test:
6
1 1 1 1 1 1
My answer: 3
3 test:
8
3 8 2 9 1 5 5 29
My answer: 6
4 test:
10
1 1 1 1 1 1 1 1 1 30
My answer: 6
5 test:
12
15 12 1 23 5 12 27 3 21 11 10 4
My answer: 9
6 test:
13
4 2 3 7 6 1 5 2 4 4 6 5 25
My answer: 8
7 test:
15
4 7 2 8 6 1 12 30 1 2 4 8 10 10 3
My answer: 9
8 test:
6
1 2 3 4 5 6
My answer: 5
9 test:
15
6 2 4 8 12 14 18 20 24 28 2 4 26 30 22
My answer: 10
10 test:
12
14 2 6 7 3 9 7 1 2 1 2 1
My answer: 8
In advance thanks!!! - 1. 3
- 2. 6
+ 3. 6
- 4. 10
- 5. 10
+ 6. 8
- 7. 11
- 8. 3
- 9. 15
+ 10. 8
You have 30%. Work. >+ 10. 8
12
14 2 6 7 3 9 7 1 2 1 2 1
let's take
12
{10,4} 2 6 {5,2} 3 9 7 1 2 1 2 1
then we have seven pairs (is not true)?:
(2,1) (2,1) (1,2) (6,7) (2,3) (4,5) (10,9)
P.S. sorry for eng. and I got AC.
Edited by author 14.06.2011 17:25
Edited by author 14.06.2011 17:25 "A hired designer reckons that all diplomas of the same kind (for example, for winning semifinals) must be in the same row"
Doesn't that mean, that we can't separate 14 as 10 and 4? |
| ♠♠♠♦♦•◘How to slove this problem? | temp5 | 1431. Сертификаты | 18 апр 2011 11:18 | 7 |
Thanks. But I dont understand what is the DP.
May be you mean Brut Forse DP means dinamic program. Thanks and best wishes! ==)
☺ Greedy algo. merge amt-1 with amt-2. merge leftover of amt-2 with amt-3, merge leftover of amt-3 with amt-4 (amt-N stands for number-of-types-of-diplomas-with-amount-N). Whatever remains umerged consumes dedicated row. bipartite graph maximum matching |
| Problem 1431 "Diplomas". Some new tests were added. (+) | Sandro (USU) | 1431. Сертификаты | 12 фев 2011 18:08 | 1 |
24 authors lost AC after rejudge. |
| Take this test into consideration | Farhad Ghasemi | 1431. Сертификаты | 25 янв 2010 10:58 | 1 |
4
14 13 14 13
the answer is 2! |
| Very bad test, which fails many algos... (+) | Lampabash | 1431. Сертификаты | 26 июн 2009 16:26 | 8 |
How????????
I think that the answer is 3 if you mean:
3
10 3 5
then the answer (accepted) is 3 can't we split the 10 in 6 and 4 and then:
1 row: 6 5
2 row: 4 3
? No, we can't. You can refer to the problem statement:
"A hired designer reckons that all diplomas of the same kind (for example, for winning semifinals) must be in the same row" I think, this comment should be added in statement, because it's easy to confuse, thinking that ALL designer claims were dismissed. It's interest to solve problem if we can split. I have O(2^(3*n/2)) probably right solution using DP of bitmasks. If we have group of k diplomas where no 2 of them cannot be fully situated exactlty in one row, than we can situate these k diplomas in k or k-1 rows. For each bitmask we check, can we situate its k(mask) diplomas in k-1 rows. Than in DP for mask with k bits we check all submasks with size of <=k/2 as first such group. These get us the complicity written before. Надо учесть:
И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду |
| why wa | ................. | 1431. Сертификаты | 2 авг 2008 12:16 | 8 |
why wa ................. 25 фев 2006 13:29 #include <iostream> #include <algorithm> using namespace std; int n; int a[30]; int main() { cin >> n; int i; for (i=0;i<n;i++) cin >> a[i]; sort(a,a+n); int ans=n; for (i=0;i<n-1;i++) if (a[i+1]-a[i]==1) { i++; ans--; } cout << ans << endl; cin >> n; } try this test:
4
1 1 2 2
correct answer is 2 Re: why wa [AESC USU] Golubev_Sanja 25 фев 2006 15:37 I have the same answer, but i still have WA 6. Could you give some more tests? Try this test:
5
5 7 6 7 4
Answer is 3 Try this test:
5
5 7 6 7 4
Answer is 3 Why answer is 3 ??????????? все понял
a=5
b=7
c=6
d=7
e=4
-------------
______|
__aeaeaeaea
bcbcbcbcbcbcb
___ddddddd
Accepted 0.001 141 КБ )))
Edited by author 02.08.2008 12:17 You considered the problem to be too simple... |
| How the diplomas must alternate? | [AESC USU] Golubev_Sanja | 1431. Сертификаты | 25 июл 2008 17:59 | 4 |
Что значит "строгое чередование"? It means that, for example, sequence
1 2 1 2 1 2 1
is valid, while sequence
1 1 2 1 2 1 1
is invalid.
More precise: if we put two different types of diploma into the same row, then no two diploma of the same type should be adjacent. and total number of diplomas must be odd |
| Just simply Greedy | SerailHydra | 1431. Сертификаты | 29 авг 2007 23:56 | 3 |
There is no need to use DP. Can your write proveness of Greedy for this problem?
Dp as a rule absolute correct optimization method
but greedy often well to next rejudgement.
Yes!! AC
Very hidden information needed: Dimploms of
one type must be placed in one row.
During a long time I thought that after changing
conditions we can placed them in any different rows.
Edited by author 24.01.2008 11:04 Let's try to proove it with one additional statement: "There is only one type of diploms with some size S".
First we put all type of diploms in seperate lines. Now we must minimize the number of rows.
By the problem description we have:
We can merge two (x and y) rows into one if and only if equality is statisfied:
|size(x)-size(y)| == 1
So, some diplom row x can be merged only with row y. Where: size(y) == size(x)+1 or size(y) == size(x)-1.
If none of y diploms row exist, then row x can not be merged and it must stay.
If only one dimplom row y exist, then we must do this megre not looking on y at all. Even if y has other possible merging global minimus isn't affected. If we can megre x and y or y and z, we can merge only one pair.
The last type of merge left, then x can be merged from both sides. Here we cant choose the prefered merge so easily.
So let's sort all rows and analise them in accessing order.
Then this situation just can not happen, cause all size(y)-1 merging row will be merged before, then analysing Y row.
Now lets apply this proof to out problem. We just have to divide all dimploms into sets. In set A goes all dimpols x with size(x) == A. So we must minimize the sum of all set's power by same apporach. |
| AC prog!!!all test gives OK but WA#8 PLEASE HELP | Paradox(Petrosian Alexander){RAU}~ | 1431. Сертификаты | 3 июл 2007 15:35 | 4 |
#include <iostream> #include <algorithm> using namespace std; int n; int a[30],b[30]={0}; int main(){ cin>>n; int i,j; for(i=0;i<n;i++) cin>>a[i]; sort(a,a+n); int ans=n; for (i=n;i>=0;i--){ if(b[i]==1)continue; for(j=i;j>=0;j--){ if(a[i]-a[j]==1&&b[j]!=1){ // i++; b[j]=1; ans--; } } } cout<<ans<<endl; // cin>>n; return 0; } Thanks If there is WA, program cant be called "AC" =) why?
Edited by author 03.07.2007 15:36
Edited by author 01.06.2008 12:33 Yes [AC code is moderator] but this prog is the best.]:---} Edited by author 03.07.2007 15:41 Edited by author 01.06.2008 12:34 Edited by author 01.06.2008 12:35 |
| HOW TO USE THIS JUDGE SYSTEM? | jackzengkk | 1431. Сертификаты | 8 июл 2006 15:20 | 2 |
I AM A BEGGINNER OF C ,I AM SAD THAT I DON'T KNOW HOW TO USE THIS JUDGE SYSTEM?WHO CAN TELL ME?THANKS! |
| WA#10, plz give me some tests(-) | Lampabash | 1431. Сертификаты | 15 май 2006 20:15 | 1 |
|
| Does it is a valid one? | vano_B1 | 1431. Сертификаты | 17 мар 2006 18:19 | 1 |
Does this position of the same diploma right?
1 1
and
1 1 1
Thanks.
Edited by author 17.03.2006 18:21 |
| WA3 | Dzmitry | 1431. Сертификаты | 1 мар 2006 16:32 | 1 |
WA3 Dzmitry 1 мар 2006 16:32 |
