SnackDown 2018 ― Elimination Round

6 лет назад, # ^ |

Sigh. Rereading my questions about its original statement and the clarifications I received, I noticed that clarification was also unclear and could have been interpreted in either commented or uncommented way. I should have caught that.

→ Ответить

alex9801

6 лет назад, # ^ |

Turns out that description was overly specific, but in the exact wrong way..

→ Ответить

http://oeis.org/search?q=Number+of+strings+of+length+n+over+a&sort=&language=english&go=Search

6 лет назад, # ^ |

Not overly. It needed to be specified. (And in one of many wrong ways.)

→ Ответить

sevenkplus

6 лет назад, # |

← Rev. 2 →

+65

Looks like the data (or statement) for EBAIT is incorrect. In the statement it says for all bus except the last one in last convoy, A has more votes than B; however most solutions understand it as for all buses not in the last convoy, A has more votes than B. We stuck on this problem for more than 3 hrs.

→ Ответить

peter50216

6 лет назад, # ^ |

+57

Same here, I stuck on this problem for 2 hours...

→ Ответить

tourist

6 лет назад, # ^ |

+90

Yes, accepted solutions output 1 1 for the following test case:

1
2 1 1
1 2

Spent two hours due to this as well... luckily it was our only remaining problem during the last hour, but for other teams it might have been crucial.

→ Ответить

Um_nik

6 лет назад, # |

+59

Also I guess it's Radewoosh's time to joke about "notorious coincidence".

→ Ответить

Radewoosh

6 лет назад, # ^ |

+13

→ Ответить

adamant

6 лет назад, # |

+27

SFXPAL may be solved in linear time using $\text{[math]}$ . Did anyone use it? Can anyone prove it? :)

→ Ответить

Dalgerok

6 лет назад, # ^ |

My team used it.

→ Ответить

mkisic

6 лет назад, # ^ |

Our solution, also linear: https://www.codechef.com/viewsolution/21809749

https://oeis.org/A252700

→ Ответить

Alpha_Q

6 лет назад, # ^ |

+50

How to solve it in $\text{[math]}$ ?

→ Ответить

dai

6 лет назад, # ^ |

← Rev. 2 →

You can use inclusion-exclusion with dp[i] = ways that last [i, n] is that first suffix is a palindrome

→ Ответить

Vijaykrishna

6 лет назад, # ^ |

Does someone have a really rigorous proof of the above statement?

→ Ответить

Alpha_Q

6 лет назад, # ^ |

← Rev. 4 →

Call a string bad if it has a palindromic suffix of length > 1 and call a_n the number of bad strings of length n.

Now we can take a bad string of length n - 1 and put a character in front of it: gives us sa_n - 1 bad strings of length n.
We can also make the whole string a palindrome: s^{⌈ n / 2⌉} strings.
However, the bad palindromes that have a smaller palindromic suffix were already counted in 1. So we subtract a_{⌈ n / 2⌉} such palindromes.

So a_n = sa_n - 1 + s^{⌈ n / 2⌉} - a_{⌈ n / 2⌉} (the operation is ceiling if it ain't clear).

→ Ответить

cerealguy

6 лет назад, # ^ |

+41

Why is the number of palindromes in 3. a_{⌈ n / 2⌉}?

In 3. we're counting the number of palindromes of length n which have a palindromic suffix of length ≤ n - 1.

a_{⌈ n / 2⌉} is the number of palindromes with a palindromic suffix of length ≤ ⌈ n / 2⌉, so we also need to prove that if a palindrome has a palindromic suffix, then it has a palindromic suffix of length ≤ ⌈ n / 2⌉ (*).

If that's left out as obvious, then we don't need bad strings:

Take a good string of length n - 1, put one character in front: $\text{[math]}$
Subtract palindromes that are created by taking a good string of length ⌈ n / 2⌉ and turning it into a palindrome of length n: $\text{[math]}$
All strings in 2. were counted in 1 because of (*)

$\text{[math]}$

I think adamant and Vijaykrishna were asking for a proof of (*). It's not hard: if $\text{[math]}$ is a palindrome and has a palindromic suffix of length k where k > ⌈ n / 2⌉ then for i ≤ 2k - n

$\text{[math]}$

and the suffix of length 2k - n is also a palindrome and shorter

→ Ответить

Vijaykrishna

6 лет назад, # ^ |

Yes, I figured this proof out later by myself, but thank you anyways for the elaborate explanation.

→ Ответить

nikolapesic2802

6 лет назад, # ^ |

+10

I just made a brute force, searched for the solutions on oeis and found this:

→ Ответить

cdkrot

6 лет назад, # ^ |

← Rev. 3 →

The straightforward dp is

$\text{[math]}$

I guess yours dp can be simply proven using dp above.

→ Ответить

desert97

6 лет назад, # |

+136

This is directed towards Codechef organizers: I am going to explain why team azneyes (with ksun48) and moofest (with me) have basically the same code on ADIMAT.

We were both on MIT ACM last year, and did GP of Poland. We both recognized that the problem was the same as there, so we both copy and pasted our AC code from there. That's why the code is the same.

→ Ответить

AIex_2oo8

6 лет назад, # ^ |

Can you give link of this GP of Poland's question ?

→ Ответить

awoo

6 лет назад, # ^ |

+15

Problem I

→ Ответить

mbrc

6 лет назад, # ^ |

Is there any judge where we can submit solutions to the problems of this GP of Poland ?

→ Ответить

awoo

6 лет назад, # ^ |

Here is the opencup contest, no idea if the problems are uploaded somewhere else.

→ Ответить

6 лет назад, # |

+16

Problems from OEIS, from e-maxx, from recent contest — well done Codechef, it was one of the worst contests ever.

Is the Codechef coordinator green or cyan?

→ Ответить

Swistakk

6 лет назад, # ^ |

+99

Worst contest ever? I agree that repeated problem from opencup sucks and wrong testdata in Elections sucks even more, but many problems were quite original and interesting. I surely enjoyed this contest (maybe my impression would be different if I would have been solving elections not as my last problem)

→ Ответить

RedNextCentury

6 лет назад, # ^ |

Opencup isn't really "open" so not many people have access to the contests, how would they know that it is repeated?

→ Ответить

6 лет назад, # ^ |

+11

I agree, problem from Opencup was a notorious coincidence, but still, there are two OEIS problems and one problem from e-maxx, and T-shirts were decided on them.

→ Ответить

RedNextCentury

6 лет назад, # ^ |

+10

Yeah I agree with others. BTW, which problem is from e-maxx?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

+18

A problem about tree.

There is no exact code, but it is explained how this problem is solved. So this problem is just "write standard algorithm, without any changes".

→ Ответить

ainta

6 лет назад, # ^ |

+23

Was there an OEIS problem? I solved all, but couldn't find it.

→ Ответить

6 лет назад, # ^ |

+20

People in Discord say that palindromes and binary matrix can be found on OEIS.

→ Ответить

Swistakk

6 лет назад, # ^ |

-39

Tbh, during my competitive career I have found some sequences on OEIS, but never managed to get a solution from there. Usually there are just 30 first elements with no useful info on how to compute it in the fastest way, but a lots of useless info about shitty generating functions or whatever.

→ Ответить

Endagorion

6 лет назад, # |

+37

So is something going to be done with Election Bait? In a situation when the statement is inconsitent with the test data, accepting all solutions that solve the problem correctly in at least one of the sensible settings seems like a fair thing to do.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

-53

Accepting all solutions that solve the problem according to the in-contest version of the problem statement (and changing either the statement or test data, whichever is more practical) seems like the best course of action, yes.

UPD: Should I take downvotes to mean nothing should be done? ( ͡° ͜ʖ ͡°)

→ Ответить

Gassa

6 лет назад, # ^ |

+24

Sorry, but this looks like wrong understanding. The way proposed by Endagorion was to accept solutions to both versions of the problem, not to pick one of them. So that the accepted solutions stay accepted, but additionally, the currently rejected solutions get rejudged with jury answers being answers to the other version of the problem. It requires some work on the organizers' side.

→ Ответить

6 лет назад, # ^ |

-18

The misunderstanding is on your part. I said accepting all solutions that X, not "and rejecting all solutions that not X".

There will be a rejudge accepting both versions.

→ Ответить

Gassa

6 лет назад, # ^ |

Sorry again, I just don't see how changing the statement helps rejudging with the other statement.

But anyway, looks like there's really no misunderstanding on your part, alright then :) .

→ Ответить

6 лет назад, # ^ |

-15

Changing the statement is just for the future. Problems are available for practice after all.

→ Ответить

mnbvmar

6 лет назад, # ^ |

+13

Thanks! When can we expect the rejudge to be done?

→ Ответить

Endagorion

6 лет назад, # ^ |

It gets even worse because some of the translations may be entirely different kinds of wrong. For instance, the Russian statement misses any kind of formal explanation of the process (it just basically says "the party A should be winning until the very last moment", sic).

→ Ответить

Errichto

6 лет назад, # ^ |

+20

It shows that there should be no translations for important international rounds, unless organizers can really ensure the quality.

→ Ответить

https://www.codechef.com/SNCKPE19/problems/ANGLE

6 лет назад, # ^ |

← Rev. 2 →

-44

Translations are sometimes made using early versions of statements (before I completely rewrite them). Long Challenge started yesterday, so I had 22 problems to work on and only edited EBAIT today. Still, translations are there just for convenience and if someone gets something wrong because of not reading the main problem statement, that's just too bad.

→ Ответить

cdkrot

6 лет назад, # ^ |

In the preelimination contest earlier this year there was a bug in russian statement. The numeration of sides of the triangle is clearly different

I prefer not to read translated statements since then :)

→ Ответить

aid

6 лет назад, # ^ |

+57

What's the point of making them if you have to read english statement anyway?

→ Ответить

zeliboba

6 лет назад, # ^ |

Agree. These creepy translations should be deleted. Some things are just too bad to exist.

→ Ответить

6 лет назад, # ^ |

-47

You have to read the English statement if you want to be 100% sure what's going on. It might be simpler for people to speedread statements in their native languages. But idk, I don't decide that.

→ Ответить

traxex

6 лет назад, # ^ |

Since you brought up the long contest, in this month's challenge problem, the English statement does not explain how the input is generated but the Russian and Hindi translations do.

It seems that to be 100% sure you understand a CodeChef problem, you have to read the English statement and the translations.

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

-27

The input in the challenge problem is generated in a secret way. Thanks for telling me, it should be removed from the translations — it can lead you to optimising your program's performance on wrong test data without realising it. (Go ahead and give me an implementation of connect().)

→ Ответить

traxex

6 лет назад, # ^ |

+16

That's interesting, I heard the contest admin said the exact opposite: that the pseudocode will be added to the English statement as well, and to look at the translations in the meanwhile.

Glad this came up now when there's still plenty of time left in the contest to clarify things.

→ Ответить

https://www.codechef.com/viewsolution/21809280

6 лет назад, # ^ |

Of course, when I say something will be done, that's just what I think will/should be done. The translations are updated now.

If you think about this generator description, there isn't any area where it clearly tells you something. It doesn't let you reproduce tests with an identical distribution, since connect() is secret. It doesn't exclude any types of tests because the baseline is a random DAG and connect() is secret. OTOH, how tests are formed clearly affects the solution somehow (or it wouldn't be secret), which is something people might miss. It's better to avoid saying something misleading about test data.

The main problem with keeping translations accurate, especially when a small correction is made in a statement, is resources: time and people. Think about it, who will check the translations? Are translators supposed to monitor everything and triple-check for differences? I don't know any TL languages except Russian, so that's out. Problemsets are made late since there aren't enough setters, which means testing is often rushed, things change shortly before the contest, and sometimes something gets missed. Translations are the last part of the expected process "initial statement -> changes during testing -> final statement -> translations", and of course, when you parallelise, it's much easier to miss something. Plus consider that people who do everything have their own lives, for example I have a full-time job and usually fix statements in evenings when I have free time. If I'm on a trip somewhere with no net, you might get crap statements; this ties up to the "not enough time" problem.

In the end, the situation can't improve unless more good problems are proposed — that would push the whole workflow ahead. There are small improvements like more people checking everything, or not so many shitty non-statements where I have to divine what the setter wanted to write, but they don't affect so much.

→ Ответить

Endagorion

6 лет назад, # ^ |

+127

translations are there just for convenience

In most serious competitions I've seen translations are treated as formal documents with equal power as official statements. If that is not the case, there probably should be a notice of that (e.g. "there's no guarantee our translations have anything to do with actual problems, idk lol").

→ Ответить

TianyiQ

6 лет назад, # ^ |

+56

In Chinese statement for SFXPAL we're told to modulo the answer with 1e9+7 instead of M. Luckily I guess most participants have noticed the extra number M in the input.

→ Ответить

kessido

6 лет назад, # |

Problems were very interesting, enjoyed it quite a bit, even thought they were very difficult for me. If someone could elaborate on Adi and the Matrix it could be nice ^^

→ Ответить

jtnydv25

6 лет назад, # ^ |

← Rev. 6 →

+82

You have to use burnside lemma. THe group acting on the set of all binary matrices is (P, Q), where P and Q are permutations of length m and n respectively. Say the cycle lengths in the permutations are (l₁, l₂, ..., l_k) and (L₁, L₂, ... L_r) respectively.

Now we have to find the number of binary matrices unaffected by the pair (P, Q). We will choose some X_a, b and rest will be set through equality conditions. For example, say we choose some index a from a cycle of length l_i and index b from cycle of length L_j. Then setting X_a, b will set $\text{[math]}$ values. So overall, we have to set $\text{[math]}$ values to set all values for indices from the cartesian product of two cycles. Hence there are $\text{[math]}$ binary matrices fixed by the permutation pair.

Now, assume n < m and for each partition of n, do a dp on the other dimension. The overall complexity is O(m²p(n)) or O( $\text{[math]}$ where N is the constraint on nm and p(n) is the partition function. Link to solution

→ Ответить

WNG

6 лет назад, # |

How to solve ADITREE ?

→ Ответить

fruwajacybyk

6 лет назад, # ^ |

+18

Choose any root. Observation: We have to take an edge from v to its parent p in our optimal connection iff the number of light-on houses in subtree rooted at v is odd.

So you can keep in val[v] parity of light-on houses under v.

When you switch light in v you have to do val[w] ^= 1 for each vertex on the path from v to root.

The answer to the query is sum of val[v] for all vertices.

You can implement those operations efficient using HLD/centroid decomposition.

→ Ответить

hitesh_r

6 лет назад, # ^ |

+10

How to solve it using Centroid Decomposition?

→ Ответить

nikolapesic2802

6 лет назад, # ^ |

← Rev. 2 →

+10

I figured out that when we switch the values of vertexes a and b, we need to flip the state of every edge on the simple path from a to b either from needing it in our pair connecting to not needing it and vice versa and just count the number of edges we need after every flip. This can be done with heavy light decomposition.

Link to my solution:

→ Ответить

Swistakk

6 лет назад, # |

OK, so here's my turn to ask something about EBAIT. Not adressing issues connected to this problem, how did you manage to solve it? I see that many teams solved it, however it still seems to me like a really hard problem. I tried to solve it using pretty complicated black box that tells me number of lattice points in first quadrant below line with equation Ax+By=C. This black box is rally tough, but fortunately we had it prewritten, but I still didnt manage to fully solve the problem since I got lost in ocean of formulas. mnbvmar used some algorithm from Wikipedia about continued fractions, but this seems really weird to me and Errichto used some freaky Python function that solved it for him, both of these approaches look nothing at all how I would approach such problem (maybe that's why I didn't solve it?)

→ Ответить

6 лет назад, # ^ |

+10

well, continued fractions seems to be reasonable directions to start from because they give you best approximations of things (with small denominators) and you want to get a good approximation to the start of interval(which is less then end of an interval)

→ Ответить

pavel.savchenkov

6 лет назад, # ^ |

+37

A way how I see this problem:

You basically have the following inequalities:

$\text{[math]}$ for some integers $\text{[math]}$
$\text{[math]}$ for some integers $\text{[math]}$

After some hard math I managed to get this:

$\text{[math]}$
$\text{[math]}$

So you need to find $\text{[math]}$ between $\text{[math]}$ and $\text{[math]}$ . I used Stern–Brocot tree to find the closest to the root fraction that lies between L and R. You can also use this.

→ Ответить

ko_osaga

6 лет назад, # ^ |

← Rev. 3 →

It's called Stern-Brocot tree. If you google "Stern-Brocot tree site:codeforces.com", you can hopefully find this post where you can simply copypaste.

→ Ответить

6 лет назад, # ^ |

+34

How about this: Try all denominators up to min(C2, 10000), compute the minimum numerator for each. If you didn't find a solution, try 1000 random denominators. If you still didn't find a solution, declare that none exist. AC in 0.05s.

→ Ответить

6 лет назад, # ^ |

+24

→ Ответить

6 лет назад, # ^ |

So, there's no testcases where there's a single denominator which fits and is quite big (~1e9)? Sounds like bad test suite to me.

→ Ответить

6 лет назад, # ^ |

Can they be made? How about an extended version with trying numerators up to 10000 too?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

Well, I'm not sure, but something like this should work:
Let's get some fraction p/q, approximate it with all the denominators from 1 to c2 from the top and from the bottom. Get closest from both sides and set them as two borders.

Of course, you'll also need to construct testcase itself (didn't think whether it's trivial)

→ Ответить

6 лет назад, # ^ |

a b c d should give a range (b / a, (b + d) / (a + c)), so at least any range with max-fraction having the bigger numerator and denominator is doable. When we account for irreducible fractions, that gives even more.

When the range of allowed fractions is very tight, I'm thinking of some solution that discards ranges of numerators/denominators that clearly have no solution within the given range...

→ Ответить