COCI 2017/2018 — Round 3

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

There is currently no feature that allows you to change your old password to a custom one, sorry.

→ Ответить

Suleyman.A

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

try to send clarification request

→ Ответить

nima10khodaveisi

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

duration ?

→ Ответить

giorgosgiapis

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

Three hours.

→ Ответить

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

Good luck to everyone!

→ Ответить

mraron

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

Weird. I don't see tasks.

→ Ответить

Daryusz

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

+22

Is there something with 0, (2^m)-1 and subsequence that xor of all elements == (2^m)-1 in E task?

→ Ответить

markysha

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

+31

How to solve C, E, F?
Is there smth faster than $\text{[math]}$ for C?

→ Ответить

chemthan

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

← Rev. 3 →

E: An interval can't win iff it contains exactly 2k pair (x, 2ⁿ - 1 - x).

→ Ответить

markysha

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

+19

Do you have any proof?

→ Ответить

chemthan

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

← Rev. 3 →

+16

Proof is easy. Let its xor sum be X. Then for each element a in that interval we must have a^(2ⁿ - 1)^X also is in that interval. So we have d pairs (a, a^(2ⁿ - 1)^X). Because its xor sum is X, so X must be 0.

→ Ответить

szawinis

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

How do you check if an interval meets the condition effectively?

→ Ответить

dpaleka

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

← Rev. 2 →

Denote N = 2^M - 1.

You can answer the queries of the type "maximum/minimum index i such that N - perm[i] exists in the target interval" in O(1) with O(NlogN) or even O(N) precomputation with RMQ. Then, if the answer to any of the queries doesn't belong to the target interval, the interval is winnable (as explained in chemthan's post).

Unfortunately, as the task is to count the winnable intervals rather than answer to queries, this method is only O(N²), which is enough only for 50% of the points.

→ Ответить

minimario

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

How to solve it after this? It seems now it reduces to: count the number of subarrays with exactly 0 or 2 instances of every element.

→ Ответить

RockyB

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

← Rev. 2 →

If my solution is correct, time complexity of my solution is O(R² * S)

Problem C

→ Ответить

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

Yeah, that was the intended solution.

→ Ответить

markysha

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

So can you explain it?

→ Ответить

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

← Rev. 2 →

Sure, let's first think about the game in a different light. Suppose that everything on the grid stays still and the main character can in one second move from (r, c) to (r - 1, c - 1), (r - 1, c) or (r - 1, c + 1). It is easy to see those games are equivalent.

Let dp[r][c][o] denote the longest valid expression you can acquire if you are currently on position (r, c) on the screen and the difference between the number of open parentheses and closed parentheses in the expression you have acquired thus far equals o. Computing all dp values takes O(R³) time. This solves the part of the problem that deals with the length of the sequence.

For the reconstruction, we'll keep around a set of dp states that can potentially lead us to the lexicographically smallest solution. At the beginning, that set contains only Mirko's initial position. We will now make transitions from those states (similar to transitions in dp) that lead to longest solutions and traverse only the empty cells of the grid (this is a standard bfs). Once we have exhausted the empty cells, we have obtained the set of cells that contain the next parenthesis in our sequence. At this point we will disregard all cells that have ')' written on them in case there exists a single cell with '(' written on it. Repeating this process yields the lexicographically smallest sequence in O(R²).

→ Ответить

bula

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

← Rev. 2 →

Since there is no test case with expression longer than 50, separate reconstruction part is actually not needed. We can define dp value as pair of (longest valid expression, lexicographic price of expression) and then just maximize this pair using dp.

If for some state longest valid expression is k then lexicographic price is k-bit number created from this expression with ( being 1 and ) being 0 — this k-bit number is solution itself.

EDIT: Actually I modified this approach a bit and it works for all possible cases i.e. with expressions up to 100, just replace k-bit number with solution string, add custom operator< and then just print that string at the end.

→ Ответить

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

What makes you think there is no test case with expression longer than 50?

→ Ответить

bula

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

Well, I meant in this specific contest there was not :). Of course there could be a test case with expression longer than 50.

→ Ответить

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

You made me a bit paranoid for a second because I generated the test data :)

Now I see that we uploaded the wrong .zip archive at hsin.hr/coci which contains the test data for our local version of the contest (honi). That version of the task had looser constraints and the solution you described was supposed to get accepted.

The correct archive should be up tomorrow.

→ Ответить

bula

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

As noted in the edit of my comment above, this approach is working for all possible test cases if the lexicographic price part is replaced by plain string, bitset could be used as well. Thus special reconstruction phase could be avoidable after all. Waiting for additional test cases.

→ Ответить

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

← Rev. 2 →

+25

Wasn't C was harder than other C's in COCI?

→ Ответить

linkret

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

Yes, considerably.

→ Ответить

KieranHorgan

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

D is pretty easy right? Unless I missed something that made it hard...

→ Ответить

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

Yeah.. Did you wrote simple BFS like me?

→ Ответить

szawinis

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

Same here. Honestly, C and D should be swapped.

→ Ответить

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

Im not sure simple bfs was the optimal way. My code was not that simple

→ Ответить

computerbox

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

← Rev. 2 →

-8

oh my god! I didn't read the D ,because i wanted to write c with recursion. #facepalm

→ Ответить

computerbox

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

-8

really ,it is a simple bfs.

→ Ответить

KieranHorgan

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

← Rev. 2 →

Yup. Well two BFS, but still very simple. I actually have a stupid typo in my last submission so it won't pass but it definitely seems too easy.

→ Ответить

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

I don't know, but it reminded me this problem: http://codeforces.com/contest/877/problem/D

→ Ответить

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

Do you know when can i see the results?

→ Ответить

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

← Rev. 2 →

Usually, after 40 min. we can see results, but there can be delay sometimes.

Results delayed :(

→ Ответить

computerbox

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

in messages i saw this " Results will be available tomorrow. Thank you for patience. "

→ Ответить

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

What is the optimal solution in problem B?

→ Ответить