| ENG RUS | Timus Online Judge |
Discussion of Problem 1431. DiplomasNoob [NULP] About understanding of problem // Problem 1431. Diplomas 8 May 2021 12:17 Edited by author 21.05.2021 00:09 Dmitri Belous WA #14 // Problem 1431. Diplomas 19 Oct 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]. Evgeny Shulgin If you have WA6 or WA7 // Problem 1431. Diplomas 25 Mar 2015 16:26 See this test: 6 2 2 2 3 3 3 Bad answer: 5 Good answer: 3 Alias aka Alexander Prudaev there is a polynolyal time solution, my is O(N^3) [3] // Problem 1431. Diplomas 11 Aug 2008 06:36 Vedernikoff Sergey (HSE: EconomicsForever!) Re: there is a polynolyal time solution, my is O(N^3) // Problem 1431. Diplomas 11 Aug 2008 13:56 Mine is O(N) =) AlMag Re: there is a polynolyal time solution, my is O(N^3) [1] // Problem 1431. Diplomas 11 Aug 2008 20:33 of course, O(N) gautamvs Re: there is a polynolyal time solution, my is O(N^3) // Problem 1431. Diplomas 28 Nov 2013 00:00 sorting array can help improving O(N^3) to O(N^2) Vitalik What right answers? [3] // Problem 1431. Diplomas 28 Jun 2006 23:05 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!!! Alexey Re: What right answers? [2] // Problem 1431. Diplomas 29 Jun 2006 19:18 - 1. 3 - 2. 6 + 3. 6 - 4. 10 - 5. 10 + 6. 8 - 7. 11 - 8. 3 - 9. 15 + 10. 8 You have 30%. Work. trn Re: What right answers? [1] // Problem 1431. Diplomas 14 Jun 2011 17:24 >+ 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 Shushan Arakelyan Re: What right answers? // Problem 1431. Diplomas 7 Jun 2012 18:31 "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? temp5 ♠♠♠♦♦•◘How to slove this problem? [6] // Problem 1431. Diplomas 29 Jun 2007 17:30 please help. Thanks Vedernikoff Sergey Simply DP... [4] // Problem 1431. Diplomas 29 Jun 2007 23:14 Paradox(Petrosian Alexander){RAU}~ Re: Simply DP... [3] // Problem 1431. Diplomas 3 Jul 2007 15:32 Thanks. But I dont understand what is the DP. May be you mean Brut Forse CHIDEMYAN SERGEY Re: Simply DP... [2] // Problem 1431. Diplomas 4 Jul 2007 00:42 DP means dinamic program. Paradox(Petrosyan Alexandr){RAU}~ Re: Simply DP... [1] // Problem 1431. Diplomas 1 Jun 2008 12:46 Thanks and best wishes! ==) ☺ Denis Koshman Re: Simply DP... // Problem 1431. Diplomas 25 Jul 2008 17:57 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. [York Hotel] maple Re: ♠♠♠♦♦•◘How to slove this problem? // Problem 1431. Diplomas 18 Apr 2011 11:18 bipartite graph maximum matching Sandro (USU) Problem 1431 "Diplomas". Some new tests were added. (+) // Problem 1431. Diplomas 12 Feb 2011 18:08 24 authors lost AC after rejudge. Farhad Ghasemi Take this test into consideration // Problem 1431. Diplomas 25 Jan 2010 10:58 4 14 13 14 13 the answer is 2! Lampabash Very bad test, which fails many algos... (+) [7] // Problem 1431. Diplomas 20 May 2006 22:41 in: 10 3 5 out: 2 Taloi Bogdan Re: Very bad test, which fails many algos... (+) // Problem 1431. Diplomas 4 Apr 2007 21:40 How???????? I think that the answer is 3 Peter Huggy (Pskov) Re: Very bad test, which fails many algos... (+) [4] // Problem 1431. Diplomas 17 Sep 2007 20:19 if you mean: 3 10 3 5 then the answer (accepted) is 3 Morbidel Re: Very bad test, which fails many algos... (+) [3] // Problem 1431. Diplomas 14 Feb 2008 19:13 can't we split the 10 in 6 and 4 and then: 1 row: 6 5 2 row: 4 3 ? Seyyed Mehran Kholdi Re: Very bad test, which fails many algos... (+) [1] // Problem 1431. Diplomas 29 Jun 2008 23:53 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" Partisan Re: Very bad test, which fails many algos... (+) // Problem 1431. Diplomas 26 Jun 2009 15:54 I think, this comment should be added in statement, because it's easy to confuse, thinking that ALL designer claims were dismissed. Partisan Re: Very bad test, which fails many algos... (+) // Problem 1431. Diplomas 26 Jun 2009 16:26 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. And IV Re: Very bad test, which fails many algos... (+) // Problem 1431. Diplomas 24 Oct 2007 15:34 Надо учесть: И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду ................. why wa [7] // Problem 1431. Diplomas 25 Feb 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; } Squid Re: why wa [4] // Problem 1431. Diplomas 25 Feb 2006 15:07 try this test: 4 1 1 2 2 correct answer is 2 [AESC USU] Golubev_Sanja Re: why wa [3] // Problem 1431. Diplomas 25 Feb 2006 15:37 I have the same answer, but i still have WA 6. Could you give some more tests? Мадест Re: why wa [2] // Problem 1431. Diplomas 1 Mar 2006 17:21 Try this test: 5 5 7 6 7 4 Answer is 3 Nec_32 Re: why wa [1] // Problem 1431. Diplomas 2 Aug 2008 02:17 Мадест wrote 1 March 2006 17:21 Try this test: 5 5 7 6 7 4 Answer is 3 Why answer is 3 ??????????? Nec_32 Re: why wa // Problem 1431. Diplomas 2 Aug 2008 12:16 все понял 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 Trident Re: why wa [1] // Problem 1431. Diplomas 25 Feb 2006 16:38 You considered the problem to be too simple... Seishau Dongi Re: why wa // Problem 1431. Diplomas 25 Feb 2006 17:56 What do you mean? [AESC USU] Golubev_Sanja How the diplomas must alternate? [3] // Problem 1431. Diplomas 25 Feb 2006 14:44 [AESC USU] Golubev_Sanja Re: How the diplomas must alternate? [2] // Problem 1431. Diplomas 25 Feb 2006 15:46 Что значит "строгое чередование"? Aleksandr Klepinin Re: How the diplomas must alternate? [1] // Problem 1431. Diplomas 25 Feb 2006 23:05 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. Denis Koshman Re: How the diplomas must alternate? // Problem 1431. Diplomas 25 Jul 2008 17:59 and total number of diplomas must be odd SerailHydra Just simply Greedy [2] // Problem 1431. Diplomas 29 Aug 2007 20:56 There is no need to use DP. svr Re: Just simply Greedy [1] // Problem 1431. Diplomas 29 Aug 2007 21:08 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 Lomir Re: Just simply Greedy // Problem 1431. Diplomas 29 Aug 2007 23:56 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. Paradox(Petrosian Alexander){RAU}~ AC prog!!!all test gives OK but WA#8 PLEASE HELP [3] // Problem 1431. Diplomas 28 Jun 2007 23:01 #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 Mace(Lviv Polytechniс NU) Re: AC prog!!!all test gives OK but WA#8 PLEASE HELP [2] // Problem 1431. Diplomas 29 Jun 2007 03:36 If there is WA, program cant be called "AC" =) Paradox(Petrosian Alexander){RAU}~ Re: AC prog!!!all test gives OK but WA#8 PLEASE HELP // Problem 1431. Diplomas 3 Jul 2007 15:35 why? Edited by author 03.07.2007 15:36 Edited by author 01.06.2008 12:33 Paradox(Petrosian Alexander){RAU}~ Re: AC prog!!!all test gives OK but WA#8 PLEASE HELP // Problem 1431. Diplomas 3 Jul 2007 15:35 Mace(Lviv Polytechniс NU) wrote 29 June 2007 03:36 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 jackzengkk HOW TO USE THIS JUDGE SYSTEM? [1] // Problem 1431. Diplomas 8 Jul 2006 14:27 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! Dmitry 'Diman_YES' Kovalioff See FAQ - http://acm.timus.ru/faq.aspx (-) // Problem 1431. Diplomas 8 Jul 2006 15:20 Lampabash WA#10, plz give me some tests(-) // Problem 1431. Diplomas 15 May 2006 20:15 vano_B1 Does it is a valid one? // Problem 1431. Diplomas 17 Mar 2006 18:19 Does this position of the same diploma right? 1 1 and 1 1 1 Thanks. Edited by author 17.03.2006 18:21 Dzmitry WA3 // Problem 1431. Diplomas 1 Mar 2006 16:32 Please help with tests!
|