Блог пользователя SecondThread

Meta Hacker Cup Round 1 Editorial

Автор SecondThread, история, 20 месяцев назад, По-английски

Meta Hacker Cup Round 1 Editorial

Good morning!

As usual, written editorials are available in the solution section of all problems on the Hacker Cup site. I thought this post might also be useful to see what people thought of the problems. After all, feedback is a gift, right?

A1/A2: Consecutive Cuts

Feedback

B1/B2: Watering Well

Feedback

C: Lemonade Life

Feedback

Feel free to leave your thoughts on the problems below :)

hackercup, round1

SecondThread
20 месяцев назад
34

Комментарии (28)

Показать архивные | Написать комментарий?

chromate00

20 месяцев назад, # |

← Rev. 2 →

+18

Question: is this for the qualification round or round 1? saying this because the links, title, problems are all mixed up (title is mixed, "Hacker Cup" link goes to the qualification round, problems are for round 1)

edit: noticed the fix. thank you!

→ Ответить

SecondThread

20 месяцев назад, # ^ |

Ah, thanks, fixed the link

→ Ответить

lucasxia01

20 месяцев назад, # |

← Rev. 2 →

+26

C for me personally didn't run in time (took 6 min to run), and seeing the scoreboard, that seemed to happen to many other people as well. Not sure what could be done here since ideally the slower solutions on faster computers shouldn't pass as well. Hopefully, future iterations have judging servers, so this won't be an issue, but maybe you guys should try testing with worse computers as well, since I doubt everyone has a top-tier computer to run on.

I appreciate all of the team's effort on creating and testing the round. I had a good time overall :).

→ Ответить

SecondThread

20 месяцев назад, # ^ |

+35

FWIW a lot of people tried a version with quadratic memory and 35k^2*log memory, which we wanted to fail, yeah.

→ Ответить

Dipankar_Kumar_Singh

20 месяцев назад, # |

← Rev. 3 →

-21

→ Ответить

collares

20 месяцев назад, # ^ |

+24

That's not how the contest format works. Besides, what does it matter? The number of advancers is not bounded.

→ Ответить

jeal0uspengu1n

20 месяцев назад, # ^ |

It does matter!!!

→ Ответить

collares

20 месяцев назад, # ^ |

+11

I encourage you to read the contest rules. The number of points distributed is the "sum of the point values for all of the input sets he or she correctly solves in that Round", and an "input set" is defined as the downloaded input file (as can be seen by the part which says you should upload the source code and the "output file generated when the competitor's source code is run on the relevant input set"). If you upload an output file with correct answers corresponding to the input you downloaded, as well as a source file which generates the given output provided the downloaded input, then the solution receives the corresponding points. Even if the source does not match the output exactly, that might not matter (see Section 8). Therefore, for the purposes of scoring, it does not matter that the solution fails on test cases outside the downloaded input file.

→ Ответить

jeal0uspengu1n

20 месяцев назад, # ^ |

Can you please quote the exact section where it says

Spoiler

I actually found this

→ Ответить

collares

20 месяцев назад, # ^ |

← Rev. 2 →

The part you quote deals with the scenario in which the uploaded source code does not produce the uploaded output file. It says that a trivial discrepancy does not remove the contestant's points, but only adds a 6-minute penalty. This is what I was referring to when I said a discrepancy might not matter.

More importantly, though, the part you quoted does not refer to the case in which the answers are correct for the downloaded input file and the uploaded source file produces the uploaded output file. In that case, the solution receives full points and that's it.

Please be specific: Are you saying that some solution was marked as correct while failing a test case contained in the corresponding user's downloaded file? I doubt that's the case because grading is automatic. Of course, if that's the case then it should be fixed. As far as I can tell, however, the OP asked for regrading because the solution failed on a test case outside the downloaded input set. Given that the competitor's score is "sum of the point values for all of the input sets he or she correctly solves in that Round" (second sentence, Section 8), that does not matter for scoring.

(It should go without saying that my previous message is not contained verbatim in the rules. Only the portions inside quotes are.)

→ Ответить

jeal0uspengu1n

20 месяцев назад, # ^ |

+12

Yeah I do know the quoted text doesn't refer to the case, but I was referring to a general case, that they should make the Testcases stronger in place of bigger. As you can see the code failed on a very small case! So surely it is not the entirely correct solution. And maybe uphacking might be included or anything to counter these solutions!

→ Ответить

gultai4ukr

20 месяцев назад, # ^ |

Wow, how the hell this code passed?!

→ Ответить

gultai4ukr

20 месяцев назад, # ^ |

Ah, maybe he just accidentally submitted A1 code along with A2 output, because it looks like the correct solution to A1.

→ Ответить

gardusig

20 месяцев назад, # |

Were A2 tests weak?

Looks like there isn't any test with K = 1 where the deck is "mirrored". Example:

2
4 1
1 2 1 2
1 2 1 2
6 1
1 2 3 1 2 3
1 2 3 1 2 3

You can see that we can actually split it into the middle and achieve the answer. I think my code gives the wrong answer for cases like these, but it still passed the official test.

→ Ответить

XxDantexX

20 месяцев назад, # ^ |

I don't think the test cases are same for everyone.

→ Ответить

gardusig

20 месяцев назад, # ^ |

I'm just trying to understand if my code is fully correct. Looks like there could have been some tests capable of breaking my solution.

→ Ответить

collares

20 месяцев назад, # ^ |

← Rev. 2 →

If I understand correctly, you can download a file containing all of the testcases by clicking on the "Submit for Practice" button. That way you can check if you were lucky with your randomly-generated input file :)

Edit: I just checked against my own input file and it seems that there is more randomness involved. Never mind.

→ Ответить

vantaablackk

20 месяцев назад, # ^ |

← Rev. 2 →

I submitted the output for B2 3 times in practice mode. The input for contest was different but the input for practice is same I think. Atleast it's the same for the 3 times I downloaded and submitted in practice. I got WA during contest even with correct solution. The output file they have attached doesn't match the output my attached code produces. Acc. to them, it differs for 1 test case. I ran my code for the single test case and found it gives correct answer. Seems like there were lots of false positives (due to weak test cases) and false negatives also (like in my case).

→ Ответить

collares

20 месяцев назад, # ^ |

← Rev. 6 →

False negatives seem really unlikely. Maybe your code uses undefined behavior, or maybe you don't reset some variables between test cases. Compiling with -fsanitize=address,undefined -g will catch some problems at runtime.

In particular: Are you sure the output file you uploaded during the competition is well-formed? Or could some line of the file be truncated? You can download it from the website. The reason I ask is because you use sync_with_stdio(false), but you also use a stdio function (freopen). I am not sure this is guaranteed to work. If you want to read/write from/to a file while using C++ streams, you can use ifstream and ofstream. Or just run your program like ./b < in.txt > out.txt so you don't have to use freopen.

→ Ответить

gultai4ukr

20 месяцев назад, # ^ |

+11

If so — that's a shame. Most of the time on this problem I spent figuring out how to handle this particular case (my solution initially is very different from the ones given in the official editorial, where it's done quite simply).

BTW, better wording here is "periodical", not a "mirrored". Mirrored string is a palindrome :)

→ Ответить

nsqrtlog

20 месяцев назад, # |

My A2 "solution", which sorts the difference arrays and compares if they are equivalent, fails with the countertest

6
1 1 2 1 1 2

1 1 2 1 2 1

with any $$$k>1$$$. It still managed to pass pretests.

→ Ответить

catsareliquid

20 месяцев назад, # |

← Rev. 2 →

Edit: nvm, it is $$$O(n^2)$$$.
I did $$$O(n\sqrt{n})$$$ approach for A2: Fix an integer $$$B[j]$$$ in $$$B$$$ so that for each $$$i$$$ in $$$A$$$ with $$$A[i] = B[j]$$$ we can start a basic comparison of the arrays from their respective indices in $$$O(n)$$$. We check if the arrays are the same from the fixed indices and do some casework with $$$k$$$ and $$$n$$$ to determine the answer. We should always choose $$$B[j]$$$ to be the number with the least occurrences in $$$A$$$ since this guarantees we do at most $$$\sqrt{n}$$$ array equality checks.

→ Ответить

MZuenni

20 месяцев назад, # ^ |

← Rev. 5 →

+10

what is with a testcase like this:

$$$(1~2)^{n-1}~2~1$$$ i.e $$$1~2~1~2...1~2~2~1$$$

$$$(1~2)^{n}$$$ i.e $$$1~2~1~2...1~2~2~1$$$

If you choose the first $$$1$$$ in $$$B$$$ and match it with all $$$n$$$ ones in $$$B$$$ you get a runtime in $$$O(n^2)$$$. Since you need to go $$$O(n)$$$ steps on average before you get a missmatch

→ Ответить

catsareliquid

20 месяцев назад, # ^ |

Oh right, it is indeed $$$O(n^2)$$$. I guess I am just one of those who got lucky with A2.

→ Ответить

at_f

20 месяцев назад, # |

In A2 editorial:

One possible solution is to concatenate A with a copy of itself and search for whether B occurs as a substring using a linear time string-matching technique such as the Knuth-Morris-Pratt, Boyer-Moore, or Z algorithm.

I used python's str in s but that didn't finish in 6 minutes. Googling it, it seems like it's implemented as Boyer-Moore which has a worst case of O(M * N) (unless you upgrade to python 3.10, but I was using pypy). So it seems like the test cases were constructed to be mean to python and you should probably remove the mention of Boyer-Moore in the editorial.

→ Ответить

chromate00

20 месяцев назад, # ^ |

← Rev. 2 →

yes, in fact while Boyer-Moore does have a lower "best case" time complexity, it does not guarantee an $$$O(n+m)$$$ time complexity at worst. what you could have used though, is the strstr function in C, which uses Perrin and Crochemore's Two way algorithm (assuming GCC). this method does guarantee an $$$O(n+m)$$$ time complexity (even though some extra constant would be on the $$$n$$$ side). maybe you could mention this in the editorial?

→ Ответить

chromate00

20 месяцев назад, # ^ |

on an additional note, Python before 3.10 used a heuristic selection between multiple algorithms, namely Boyer-Moore-Horspool, Sunday, and the Two-way algorithm which I mentioned above. why it did not guarantee a $$$O(n+m)$$$ time complexity though, is that it only used the two-way algorithm when the pattern string is relatively shorter (as already mentioned above, its preprocessing step has some extra constants, making it kind of undesirable for use with big patterns).

→ Ответить

XxDantexX

20 месяцев назад, # |

+13

Hi, Since this is my first Hackercup, I was curious as to how hard is it get a below 2000 rank in round 2. If there is any relevance at all, what CF rank/rating does it correspond to? Thanks.

→ Ответить