SnackDown 2019 — Online Pre-Elimination rules

https://www.codechef.com/SNCKPE19

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

+24

I think it is with high probability they will use ACM ICPC rules. I dont know if the penalty will be 20 mins or it will be changed.

Adding PraveenDhinwa. he should be capable of answering.

→ Ответить

noelnadal

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

The contest's page says 10 minutes per penalty.

→ Ответить

Jatana

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

Is it allowed to use 2 computers during the round?

→ Ответить

bazsi700

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

+23

As there is basically no way to supervise it, I'd guess it is.

→ Ответить

manujvashist

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

I think he meant parallel login to the same account using both PCs. It was allowed in all previous rounds so maybe it will be allowed in this also.

→ Ответить

JustInCase

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

← Rev. 2 →

+13

Isn't it enough to login with your personal profile and submit from there? I think it counts as a team submission then.

→ Ответить

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

Yes, it's enough.

→ Ответить

kingofnumbers

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

Yes, it's allowed.

→ Ответить

bazsi700

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

From the announcements section of the contest: "16:30 IST, 3 Nov: Teams will be ranked according to number of problems solved. Ties will be broken according to ACM Rules, but with a penalty of 10 minutes for each unsuccessful submission."

→ Ответить

Jatana

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

How to solve Strange Transform?

→ Ответить

the_art_of_war

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

← Rev. 2 →

+17

Solution of my teammate: use sqrt decomposition.

For K <= 2^9 calculate answer

For K <= 2^18: run recursion.

Total time ( n + q) * 2 ^ 9

Code

→ Ответить

adamant

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

My solution is $\text{[math]}$ . If k is small, use $\text{[math]}$ (precompute all such values with this formula). Otherwise use $\text{[math]}$ , where pw is the largest power of 2 which is not greater than k. Couldn't fix all bugs before the end of contest...

→ Ответить

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

← Rev. 5 →

+19

Note, that f^k(a)_x = xor over{j which is submask of k} a_{x+j}.

Note, that you can get k modulo 2¹⁸ (implied by first statement)

Precalculate all f^k(a) for k ≤ 2⁹.

Now you are given k = l + m, where l is divisible by 2⁹ (and therefore contains at most 9 bits) and m ≤ 2⁹. Find f^l(f^m(a))_x. f^m(a) is precalculated and finding the rest can be done by enumerating submasks in 2⁹.

Overall complexity $\text{[math]}$

→ Ответить

nhho

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

← Rev. 2 →

How to prove the first observation?

I only know that it is related to the parities in Pascal triangle.

edit: It is easy to be proved by M.I. but is there some more intuitive way to reach this conclusion, other than pattern observation?

→ Ответить

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

+19

First you should notice is each one has binomial coefficients. And later we need coefficients mod2 so whem we apply Lucas thoerem, we get that observation that r must be submask of n for nCr to be odd.

→ Ответить

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

First proof how f² works, then how f^{2^k} works (by induction). Then it's easier to see

→ Ответить

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

← Rev. 2 →

+18

When upsolving usually becomes available?

UPD: now it works

→ Ответить

the_art_of_war

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

How to solve Painting Tree ?

→ Ответить

300iq

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

At first let's calculate f_k — number of ways to choose k non-intersecting paths.

With this + some simple combinatorics you can get the answer.

→ Ответить

dragoon

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

Isn't trivial dp to compute fk is O(n^3)? Although it's not that trivial!

→ Ответить

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

I don't know whether we about the same dp, but there's is pretty straightfowrard one and it's O(n^2) because in each vertex it's not O(n^2) but O(left_size * right_size) which is O(n^2) in total.

→ Ответить

Alpha_Q

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

← Rev. 5 →

Same trick used in the Polish problem Barricades (see Looking For A Challenge) reduces it to O(n²).

→ Ответить

Mistra

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

-18

I think that a part of the statement of QUEENS was misleading:

Let's denote a unit square in row r and column c by (r,c). Chef lives at square (X,Y) of this chessboard.

Here y-coordinate is denoted by X and x-coordinate by Y. Yes, the statement is technically correct, but the choice of variables is against the common conventions. Was this an oversight or an intentional attempt to mislead contestants?

→ Ответить

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

+37

the only reasonable choice of order, imho.

→ Ответить

sikander_nsit

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

Matrix conventions are different from the 2D cartesian plane conventions. According to convention in a matrix, rows are numbered from 1 to n from top to bottom and columns from 1 to m from left to right.

→ Ответить

Mistra

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

Yes, the notation (row, column) was indeed correct. What I meant is that in the statement a variable called X was used to represent row (the "y-coordinate" in matrix) and Y to represent column ("x-coordinate"). In my opinion, the names of the variables X and Y should have been swapped.

→ Ответить

sikander_nsit

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

+28

That's my point. There isn't any concept of x-coordinate and y-coordinate in a matrix. As a row number is written first and when (X,Y) is being used to describe a pair, X is used to describe the first number, so it makes sense to denote row number by X and column number by Y. I am not saying you are wrong, just want you to see the other perspective.

→ Ответить

Xellos

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

As it usually goes, the first coordinate in an array is x, the second coordinate is y, the third is z and so on (or i, j, k and so on). Makes perfect sense unless you're programming in Befunge or Logo.

I remember a contest (Polish maybe?) where rows were y and columns were x. Boy, was that confusing.

→ Ответить

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

-44

Of course man, if you are referring to matrices coordinates by z and y you should do (y,x), not that freaking most confusing in world (x,y) for row and column. I don't care about whether x comes before y or not, I care about their meaning. x is left right and y is up down. If not necessary you should omit denoting matrices coordinates by x and y, but sometimes we think of our matrix as a map where some units are moving or whatever.

→ Ответить

Xellos

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

not that freaking most confusing in world (x,y) for row and column

But it isn't (x, y) for row and column. It's (r, c) for row and column, right there in the statement. It's just that specific coordinates aren't also named r and c, they're named X and Y. If they were named A and B or Bacon and Popper, that wouldn't change the fact that which coordinate is the row and which is the column is explicitly spelled out precisely to make sure the statement explains such misunderstandings.

Perhaps not the best choice, sure, but I don't know what's the best choice and am not going to bother when I'm sick.

→ Ответить

Errichto

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

-20

I agree that x and y shouldn't be used in grids, especially with x denoting row.

→ Ответить

jvmusin

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

How to solve Heap Pirates?

I only know how to solve it when we have a bamboo (it's just a line of length n that looks like 010101).
And the other case i know is the sun (graphs with edges like (1-2) (1-3) (1-4) ... (1-n)). For n=4 it looks like this:
10101
00000
Are there any other figures?

→ Ответить

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

← Rev. 4 →

+13

Spoiler, Read a comment below for a hint first

→ Ответить

zoomswk

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

+31

There is an answer for any tree. Root the tree and generalize your idea :)

→ Ответить

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

what is the complexity for activity selection O(n^6) with small constant. or can it be done in better complexity ?

→ Ответить

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

I did O(n^5), however it is pretty clumsy to describe :f. I would be disappointed if it turns out that O(n^6) was sufficient to solve this problem. Can somebody that tried to squeeze O(n^6) write here what was the outcome? My code is here: https://ideone.com/Qwtbse, but I am not sure whether it is of any help without some description :P

→ Ответить

Egor

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

I just wrote straightforward n^6 solution and it passed right away

→ Ответить

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

R u sure yours is n^6 because contraint on m was m <=50.

→ Ответить

Egor

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

Yes. My solution is n^2km^3

→ Ответить

Andrei1998

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

← Rev. 2 →

+12

Yes, unfortunately, some O(N⁶) solutions did pass, I apologize for this.

My solution was O(N⁴M) and it ran quite slow without any constant optimization, so I thought O(N⁶) solutions are not feasible. Lesson to learn from this is that a $\text{[math]}$ constant factor is actually quite achievable given the large variety of O(N⁶) solutions with small constant factors out there.

→ Ответить

kraskevich

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

O(n^5) is quite straightforward.

Let's use dynamic programming. We'll add intervals in an increasing order of their right border.

The state is (last_right_border, current_k, current_k_pos, current_intervals_count). The value of the state is the number of ways to pick exactly current_intervals_count intervals so that the current longest sequence of non-overlapping intervals has length current_k, the leftmost of such sequences ends in the current_k_pos position and we've considered all possible intervals that end in last_right_border or to the left from it.

To make a transition, we iterate over the number of the intervals that end in the last_right_border + 1 position. Once this value is fixed, we've got two options: 1. The new intervals will not change the current value of K (which means they start before the current_k_pos). 2. They will increase K by one. It means that at least one of them starts after the current_k_pos. Either way, the number of ways to choose the new intervals is some binomial coefficient.

By the way, this solution takes around half a second to complete in the worst case (I didn't do any constant optimization, though), so I don't think that an O(n^6) solution can pass.

→ Ответить

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

I have troubles understanding how that is n^5. I think currentintervalscount is up to n^2, so you have dp table of n^5 size and as I think of it you need to have linear number of transitions from every state where you add those binomial coefficients. What am I missing here? Are you doing last step in more clever way?

→ Ответить

kraskevich

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

← Rev. 2 →

The total number of intervals is up to 50 (according to the problem statement), so I counted it as n.

→ Ответить

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

Oh no, FML... My solution runs in n^5 for M<=(n choose 2) though (I don't have M in complexity at all)

→ Ответить

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

Lol, after this discussion I saw the question and realise its min(50,...). sad life :(

Anyways if possible give a brief description of your idea. no need of complete details

→ Ответить