COCI 2018/2019 Round 5

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
2	maomao90	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

COCI 2018/2019 Round 5

Автор Atreus, история, 6 лет назад, По-английски

Hello!

This blog is to let you know that tomorrow another round of Croatian contest, COCI will be held.

Feel free to discuss problems here after the contest ends.

Update: Result

coci, coci round #5, coci 2018/2019

Atreus
6 лет назад
32

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

Написать комментарий?

Kerim.K

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

+40

2017/2018?

→ Ответить

gax

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

← Rev. 2 →

+13

Does anyone know the duration of the contest?

Edit: Thanks!

→ Ответить

heon

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

3 hours

→ Ответить

M_H_H_7

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

+11

why there is no editorial for this year's contests?

→ Ответить

roll_no_1

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

+21

How to solve 4th and 5th problem ?

→ Ответить

allllekssssa

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

← Rev. 3 →

Great tasks, it was interesting to do it.

For the fourth task, I have one TLE, but generally it can be easily solved (on codeforces it was working enoguh fast).

I stored bitmasks for all strings: 0 if character is '?' othewise 1. For example, string ab??c? would be 110010. Each string save in group with all other strings with that bitmask. Now iterate over all possible pairs of bitmasks (from 0 to 2^m in double loop ), and find all 1 on same postions in both strings. That letters should be same, other letters are not important(at least one string contains '?' on other positions). So you have two arrays without ? and you need to count amount of same elements, one from first array one from second. It can be done with std::map.

The complexity of this solution is O(2^m * mn logn). Each group(mask) will be compared with 2^m other masks, and everytime in one comparation we go over whole group + mlogn for using maps.

Code

This complexity can be decreased a little bit if we are using hashing, even with sorting (not maps), it would be much faster.

→ Ответить

M_H_H_7

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

← Rev. 3 →

sorry i had a mistake

→ Ответить

roll_no_1

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

Nice idea. Thanks. :)

→ Ответить

imilki

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

D was also solvable with bitset in O(n * m * 26 + n ^ 2 * m / 32) which passed for all points

→ Ответить

tpoppo

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

Could you please share your solution that uses bitset?

→ Ответить

imilki

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

We have a bitset of size n (number of words) for each letter of the alphabet, set the i-th bit to 1 in the bitset corresponding to the letter ai. If the letter is '?' set i-th bit to 1 in all bitsets. We do this m times.

Now we can just start with a bitset where all bits are set to 1 and the number of matching strings with the i-th string is bitwise and (&) of bitsets corresponding to the letters in the string. Note that if the letter aij = '?' we don't need use bitwise and since it won't change anything. One more thing is before we find the solution for i-th word we need to turn all bits on positions less than i to 0 so we don't count some pair twice. My explanation wasn't very good but I think the code is rather clear.

Code

→ Ответить

tpoppo

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

Thanks :)

→ Ответить

szawinis

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

I haven't submitted yet, but the fifth problem should be solvable with centroid decomposition.

→ Ответить

roll_no_1

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

← Rev. 4 →

Was the idea anyhow similar to the one used in this problem. I mean something like merging positive length paths at every node in the centroid tree so that we don't care about the fuel being exhausted somewhere in the middle but only compute the sum of vertices in the path - sum of edges in the path and then take the positive paths found in this way and a concatenation of such path will be a valid path?

→ Ответить

szawinis

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

Well my idea was to compute prefix/suffix minimum of sum_v — sum_e in order to make sure that the fuel level never drops below 0, but you're probably on the right track.

→ Ответить

roll_no_1

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

Please do share your code if you manage to complete coding and testing your idea. It will be helpful.

→ Ответить

FLEA

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

Are we allowed to send submissions after the end of the contest?

→ Ответить

nader

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

← Rev. 3 →

No. Either wait until they publish the test cases and test locally or wait until https://oj.uz/ adds the new round.

→ Ответить

FLEA

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

Ok,thank you

→ Ответить

ojuz

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

+23

Uploaded here: https://oj.uz/problems/source/372

→ Ответить

mraron

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

Fourth task gives failed verdict.

→ Ответить

ojuz

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

+17

Sorry, the uploader behaved wrong specifically in this task :( Now the issue is fixed.

→ Ответить

crimsonred

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

Thanks! Can you please also add previous month's contest?

→ Ответить

ojuz

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

Problems except Slagalica are open: https://oj.uz/problems/source/371

→ Ответить

crimsonred

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

Thank you.

→ Ответить

allllekssssa

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

← Rev. 2 →

I am interested what is expected solution for the third task? Is it O(n³), or O(n² logn) ?

I have done it in second complexity with hashing and binary search. But it looks that both solutions are passing. If you planned O(n³) solution, then you shouldn't have put subtask n ≤ 200, otherwise you should put at least n ≤ 1000.

→ Ответить

mavd09

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

I did it in O(n^3) with execution time less than one second. The second task is very useless. Btw, can you explain your solution?

→ Ответить

allllekssssa

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

← Rev. 3 →

+11

Sure, it is not very hard.

Probably you did it on following way : Iterate over every pair of rows, check whether strings are angrams (have same number of occurrence of each letter) and then find with one extra loop longest common prefix/suffix. If n - prefix + sufix ≤ k we found one pair and finished job. Now this searching for longest common prefix/suffix can be done with hashing and binary search (try prefix [1... x] compare are hashes same and move left/right border as it needed, same I did for suffix).

→ Ответить

mavd09

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

Ohhh got it! It makes a lot of sense. My solution is a little bit complicated because of that I didn't see the way to reduce it to n^2 log n. Thanks for the explanation, very clear

→ Ответить

roll_no_1

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

I wrote a python script that can be used to locally test codes on the test cases being provided on the website. It runs the code on all input files one by one and then compares the output against the output file being provided in the test cases. I used diff command to compare files though it doesn't seem to work probably because of encoding or something, but I thought it may still be helpful for some people for later times maybe. You can find it here.

→ Ответить