As I didn't find any blog for this round discussion so posting this blog
Problems:
P1
P2
P3
P4
P5
P6
I was able to solve P1,P4,P5.
Please share your approaches for other problems.
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
10:05:42
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
10:05:42
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 09.11.2024 07:29:20 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Anyone above 3 solvers gang :sadge:
Feeling dissapointed about bricking P3 D:
I solved 4 problems: P1, P2, P4, P5. I faced some server issues while submitting P6 (not sure about the correctness). Has anyone faced the same?
Error message: Not able to establish connection to InterviewBit Servers. Please check internet connectivity.
I didn't participate in the round. For P1, do we have any solution other than using segment tree over euler tour ?
There is probably a pbds set + small to large merging solution but in my opinion euler tour would be better here.
2nd problem is harder version of this cses problem
I was able to solve 1, 4, 5 and 6. But I should have better gone to problem 3 before 6th as it seems like an easier once once you know how to implement centroid decomposition. I hope so because I had set a problem with similar solution structure, you can find it here. Also find the tutorial for the same. Sed, couldn't debug it at the last minute :(.
Pls share approaches for problem 2.
Read about staircase nim, it's just the modification of it. You will have to add range update range query data structures to handle updates.
Staircase Nim: https://mirror.codeforces.com/blog/entry/44651
Thanks, I'll give it a try.
How to optimise P6? I had a 3 ^ n dp solution which involved using subsets and updating the each subset using their submasks.
Is it me or N^2 passes for 1,2,3 and 3^N passed for 6. It only showed correct answer for me not TLE./
what 3 ^ N passed? that shouldn't happen
did you try to get partial using 3^N ? I did and for some reason it passed
well nope I was too late like 2 hours in when I thought of that and it felt sub optimal so I didn't try coding it. I t was the first I attempted sadly.
Actually, It was running only on trivial test cases. It is like pretests of CF. I solved the 5th problem without taking mod and I didn't get any WA and then I corrected it afterward So, I think there are some more test cases on which our solution will be judged after the contetst.
P5 Test Cases were wrong wasted one hour on that, later on they changed test cases.
Yes. I lost many hairs thinking how the answer for 6,3 could be 45.
Same bro :(
Yessssssss! who tf tests these rounds
How to solve P6.I was thinking like some sort of bitmask dp but couldn't go too much.
P6: Problem G of this.
Did you solve all problems?
I didn't participate.
Wow, its just a single leap of faith from $$$O(3^N)$$$ solution. All time, I was being conservative by using only submasks to account for all elements, and not missing out. But we can let go of some elements and collect them at the end, that's cool.
what are the prerequisites for each problem?
Rated cf account
Short summary of my solutions for P1 to P6 :
Perform a normal dfs, and maintain set of all the ancestors in some data structure. At each node,we can query for count of elements < node.
It'll be helpful to read Sprague-Grundy theorem. Odd indices have grundy value 0 and even indices have grundy value ,the element itself. So we have to maintain range xor of odd indexed elements and even indexed elements separately using lazy segment tree.
My solution is an overkill using centroid decomposition. Here, we only care about current root node, find all the products and store them in map, while iterating over other branch, increment answer by count of (inverse (current_product * D)) .
(Might be done using small-to-large,but It's not easy to think for me atleast).
Sort items by weight, use 2-pointer.
Print : ((N choose N/2))^M, for even N, otherwise print 0
Use bitmask dp, our goal is to find the maximum number of decompositions of a mask , each having the average $$$B$$$. It's easy to do in O(3^N), now to improve , have faith and use O(N*2^N) approach, where we drop one of the element and perform recursion for remaining. Given that, recursive answer will be true, our answer may differ by atmost one due to the element we dropped. If, average of current mask's element is $$$B$$$, we are sure that the element we just dropped for recursion and the others dropped subsequently will sum up to form another valid set, so increase answer by 1.
Hey, may you please let me know what will be the approach for P5 for large numbers.
For smaller values of N & M my code was passing the sample test cases.
I used Fermat's Little Theorem
What do you feel would be the cf rating of all these problems.
For P6 , umnik once explained this in one blog, as it was a GFG wrong solution we discussed.
you can read it if you want its pretty cool tho
https://mirror.codeforces.com/blog/entry/82163?#comment-690084
There is also only positive K solution to this.
Nvm,got it.
Video Solutions of all problems
Is there a place where I can get updates on such upcoming contests?
I have developed a Chrome Extension —
CP Calendarwhich keeps the users updated about most of the rated contests on all famous CP platforms and a few hiring challenges too. (I can't guarantee that it lists all unrated contests)ADD TO CHROME
Did anybody get a chance to interview. If yes what was your score.
Did anyone receive mail regarding codeagon prizes.