Invitation to CodeChef July Cook-Off 2020

№	Пользователь	Рейтинг
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	165
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Greetings good people of Codeforces. I hope you're having a great week.

I invite you to participate in CodeChef’s July Cook-Off, this Sunday, 19th July, from 9:30 pm to 12:00 am IST.

Participants in each division will be given $$$6$$$ problems and $$$2.5$$$ hours to solve them.

We will also be hosting a live problem discussion sessions for Cook-Off problems with our panellist Rajarshi RestingRajarshi Basu on 20th July, 6 pm IST. You can register by clicking on the GOING button on the top right corner here. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Joining us on the problem setting panel are:

Setters: Shahjalal YouKn0wWho Shohag, Rahul amnesiac_dusk Dugar
Admin: Teja teja349 Vardhan Reddy
Tester: Ildar 300iq Gainullin
Editorialist: Rajarshi RestingRajarshi Basu
Post-Contest Streaming: Rajarshi RestingRajarshi Basu
Statement Verifier: Jakub Xellos Safin
Mandarin Translator: Qingchuan Zhang
Vietnamese Translator: Team VNOI
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Mohammad solaimanope Solaiman
Hindi Translator: Akash Shrivastava

Prizes: Top $$$10$$$ Indian and top $$$10$$$ Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good Luck! See you on the leaderboard!

#include<bits/stdc++.h> using namespace std; #include "spoj.h" const int N = 1e5 + 9; /* -> diff(v) = len(v) - len(link(v)) -> series link will lead from the vertex v to the vertex u corresponding to the maximum suffix palindrome of v which satisfies diff(v) != diff(u) -> path within series links to the root contains only O(log n) vertices -> cnt contains the number of palindromic suffixes of the node */ struct PalindromicTree { struct node { int nxt[26], len, st, en, link, diff, slink, cnt, oc; }; string s; vector<node> t; int sz, last; PalindromicTree() {} PalindromicTree(string _s) { s = _s; int n = s.size(); t.clear(); t.resize(n + 9); sz = 2, last = 2; t[1].len = -1, t[1].link = 1; t[2].len = 0, t[2].link = 1; t[1].diff = t[2].diff = 0; t[1].slink = 1; t[2].slink = 2; } int extend(int pos) { // returns 1 if it creates a new palindrome int cur = last, curlen = 0; int ch = s[pos] - 'a'; while (1) { curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break; cur = t[cur].link; } if (t[cur].nxt[ch]) { last = t[cur].nxt[ch]; t[last].oc++; return 0; } sz++; last = sz; t[sz].oc = 1; t[sz].len = t[cur].len + 2; t[cur].nxt[ch] = sz; t[sz].en = pos; t[sz].st = pos - t[sz].len + 1; if (t[sz].len == 1) { t[sz].link = 2; t[sz].cnt = 1; t[sz].diff = 1; t[sz].slink = 2; return 1; } while (1) { cur = t[cur].link; curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { t[sz].link = t[cur].nxt[ch]; break; } } t[sz].cnt = 1 + t[t[sz].link].cnt; t[sz].diff = t[sz].len - t[t[sz].link].len; if (t[sz].diff == t[t[sz].link].diff) t[sz].slink = t[t[sz].link].slink; else t[sz].slink = t[sz].link; return 1; } void calc_occurrences() { for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc; } }; // len -> largest string length of the corresponding endpos-equivalent class // link -> longest suffix that is another endpos-equivalent class. // firstpos -> 1 indexed end position of the first occurrence of the largest string of that node // minlen(v) -> smallest string of node v = len(link(v)) + 1 // terminal nodes -> store the suffixes struct SuffixAutomaton { struct node { int len, link, firstpos; map<char, int> nxt; }; int sz, last; vector<node> t; vector<int> terminal; vector<int> dp; vector<vector<int>> g; SuffixAutomaton() {} SuffixAutomaton(int n) { t.resize(2 * n); terminal.resize(2 * n, 0); dp.resize(2 * n, -1); sz = 1; last = 0; g.resize(2 * n); t[0].len = 0; t[0].link = -1; t[0].firstpos = 0; } void extend(char c) { int p = last; if (t[p].nxt.count(c)) { int q = t[p].nxt[c]; if (t[q].len == t[p].len + 1) { last = q; return; } int clone = sz++; t[clone] = t[q]; t[clone].len = t[p].len + 1; t[q].link = clone; last = clone; while (p != -1 && t[p].nxt[c] == q) { t[p].nxt[c] = clone; p = t[p].link; } return; } int cur = sz++; t[cur].len = t[last].len + 1; t[cur].firstpos = t[cur].len; p = last; while (p != -1 && !t[p].nxt.count(c)) { t[p].nxt[c] = cur; p = t[p].link; } if (p == -1) t[cur].link = 0; else { int q = t[p].nxt[c]; if (t[p].len + 1 == t[q].len) t[cur].link = q; else { int clone = sz++; t[clone] = t[q]; t[clone].len = t[p].len + 1; while (p != -1 && t[p].nxt[c] == q) { t[p].nxt[c] = clone; p = t[p].link; } t[q].link = t[cur].link = clone; } } last = cur; } void build(string &s) { for (auto x: s) { extend(x); terminal[last] = 1; } } }; long long distinct(string s) { SuffixAutomaton sa(s.size()); sa.build(s); long long ans = 0; for (int i = 1; i < sa.sz; i++) ans += sa.t[i].len - sa.t[sa.t[i].link].len; return ans; } long long palindromic(string s) { PalindromicTree t(s); for (int i = 0; i < s.size(); i++) t.extend(i); t.calc_occurrences(); long long ans = 0; for (int i = 3; i <= t.sz; i++) ans += t.t[i].cnt; return ans; } char s[N]; int main(){ int t, n; spoj_init(); fscanf(spoj_p_in, "%d", &t); for (int tt = 1; tt <= t; tt++) { fscanf(spoj_p_in, "%d", &n); int z; spoj_assert(fscanf(spoj_t_out, "%d", &z) == 1); spoj_assert(1 <= z && z <= 7 * n); spoj_assert(fscanf(spoj_t_out, "%s", s) == 1); string p = string(s); int sz = p.size(); spoj_assert(z == sz); for (char c: p) spoj_assert('a' <= c && c <= 'z'); long long tot = distinct(p) - palindromic(p); spoj_assert(tot == n); } char extra[100]; spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1); return 0; }

#include<bits/stdc++.h> using namespace std; #include "spoj.h" const int N = 1e5 + 9; /* -> diff(v) = len(v) - len(link(v)) -> series link will lead from the vertex v to the vertex u corresponding to the maximum suffix palindrome of v which satisfies diff(v) != diff(u) -> path within series links to the root contains only O(log n) vertices -> cnt contains the number of palindromic suffixes of the node */ struct PalindromicTree { struct node { int nxt[26], len, st, en, link, diff, slink, cnt, oc; }; string s; vector<node> t; int sz, last; PalindromicTree() {} PalindromicTree(string _s) { s = _s; int n = s.size(); t.clear(); t.resize(n + 9); sz = 2, last = 2; t[1].len = -1, t[1].link = 1; t[2].len = 0, t[2].link = 1; t[1].diff = t[2].diff = 0; t[1].slink = 1; t[2].slink = 2; } int extend(int pos) { // returns 1 if it creates a new palindrome int cur = last, curlen = 0; int ch = s[pos] - 'a'; while (1) { curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break; cur = t[cur].link; } if (t[cur].nxt[ch]) { last = t[cur].nxt[ch]; t[last].oc++; return 0; } sz++; last = sz; t[sz].oc = 1; t[sz].len = t[cur].len + 2; t[cur].nxt[ch] = sz; t[sz].en = pos; t[sz].st = pos - t[sz].len + 1; if (t[sz].len == 1) { t[sz].link = 2; t[sz].cnt = 1; t[sz].diff = 1; t[sz].slink = 2; return 1; } while (1) { cur = t[cur].link; curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { t[sz].link = t[cur].nxt[ch]; break; } } t[sz].cnt = 1 + t[t[sz].link].cnt; t[sz].diff = t[sz].len - t[t[sz].link].len; if (t[sz].diff == t[t[sz].link].diff) t[sz].slink = t[t[sz].link].slink; else t[sz].slink = t[sz].link; return 1; } void calc_occurrences() { for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc; } }; // len -> largest string length of the corresponding endpos-equivalent class // link -> longest suffix that is another endpos-equivalent class. // firstpos -> 1 indexed end position of the first occurrence of the largest string of that node // minlen(v) -> smallest string of node v = len(link(v)) + 1 // terminal nodes -> store the suffixes struct SuffixAutomaton { struct node { int len, link, firstpos; map<char, int> nxt; }; int sz, last; vector<node> t; vector<int> terminal; vector<int> dp; vector<vector<int>> g; SuffixAutomaton() {} SuffixAutomaton(int n) { t.resize(2 * n); terminal.resize(2 * n, 0); dp.resize(2 * n, -1); sz = 1; last = 0; g.resize(2 * n); t[0].len = 0; t[0].link = -1; t[0].firstpos = 0; } void extend(char c) { int p = last; if (t[p].nxt.count(c)) { int q = t[p].nxt[c]; if (t[q].len == t[p].len + 1) { last = q; return; } int clone = sz++; t[clone] = t[q]; t[clone].len = t[p].len + 1; t[q].link = clone; last = clone; while (p != -1 && t[p].nxt[c] == q) { t[p].nxt[c] = clone; p = t[p].link; } return; } int cur = sz++; t[cur].len = t[last].len + 1; t[cur].firstpos = t[cur].len; p = last; while (p != -1 && !t[p].nxt.count(c)) { t[p].nxt[c] = cur; p = t[p].link; } if (p == -1) t[cur].link = 0; else { int q = t[p].nxt[c]; if (t[p].len + 1 == t[q].len) t[cur].link = q; else { int clone = sz++; t[clone] = t[q]; t[clone].len = t[p].len + 1; while (p != -1 && t[p].nxt[c] == q) { t[p].nxt[c] = clone; p = t[p].link; } t[q].link = t[cur].link = clone; } } last = cur; } void build(string &s) { for (auto x: s) { extend(x); terminal[last] = 1; } } }; long long distinct(string s) { SuffixAutomaton sa(s.size()); sa.build(s); long long ans = 0; for (int i = 1; i < sa.sz; i++) ans += sa.t[i].len - sa.t[sa.t[i].link].len; return ans; } long long palindromic(string s) { PalindromicTree t(s); for (int i = 0; i < s.size(); i++) t.extend(i); t.calc_occurrences(); long long ans = 0; for (int i = 3; i <= t.sz; i++) ans += t.t[i].oc; return ans; } char s[N]; int main(){ int t, n; spoj_init(); fscanf(spoj_p_in, "%d", &t); for (int tt = 1; tt <= t; tt++) { fscanf(spoj_p_in, "%d", &n); int z; spoj_assert(fscanf(spoj_t_out, "%d", &z) == 1); spoj_assert(1 <= z && z <= 7 * n); spoj_assert(fscanf(spoj_t_out, "%s", s) == 1); string p = string(s); int sz = p.size(); spoj_assert(z == sz); for (char c: p) spoj_assert('a' <= c && c <= 'z'); long long tot = distinct(p) - palindromic(p); spoj_assert(tot == n); } char extra[100]; spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1); return 0; }

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

Показать архивные | Написать комментарий?

lucky_21

4 года назад, # |

← Rev. 2 →

-17

I have some exciting problem ideas and I am very interested to being used them in Codechef contests, but your site isn't working:(

→ Ответить

YouKn0wWho

4 года назад, # ^ |

sorry, fixed.

Auto comment: topic has been updated by YouKn0wWho (previous revision, new revision, compare).

darklight13

"6 Problems" well that's something new, I guess.

+35

Yeah. Maybe this is the first time in CodeChefs history(not sure). The intention is to make the contest balanced and more interesting.

SkySurfer

Could anyone have any reason regarding the timing of Codechef contest why can't they have timing similar to Codeforces contest if there is no clash ...

cmplx-xyttmt

+10

Please kindly update kotlin compiler on CodeChef to at least 1.3.70 (preferably 1.3.72).

solvemproblr

-18

Another July Long challenge?

jiteshrao

RIP ratings.

+49

Thanks for participating. Hope you guys liked the contest. I worked really hard as it was my first time preparing a cook-off contest.

It will be great if you guys provide me with some feedback about the contest i.e. what you liked, what you didn't like etc so that I can do my best next time.

Harshil_

Problem OR-thodox Distinction Was already available on Leetcode.

Extremely sorry for that. Actually we weren't aware of that problem.

antontrygubO_o

+168

Woah, problems were extremely nice in my opinion. Hope Codechef can keep this level in future, kudos to problemsetters!

Kodieren

That's true. the problemset was amazing.....maybe you could try having problems of these types on CF as well. In my opinion, problems on CF are more constructive than algorithmic. Constructive is fine but i would request you to increase the percentage of DS algo based problems

Jaydeep999997

+22

My Solution for BOJACK.

Print a string with length 2*d as an output.

First d characters should be all 'a'.

Last d characters should be all 'b'.

This always works.

Proof:

Number of different unique sub strings of this string = d + d + d*d.
Number of palindromic sub strings = ncr(d+1,2) + ncr(d+1,2).
Difference = d.

+29

Here is mine:

Solution

How I came up with a solution

kitsune

Was Pathetic about painting tree but instead of painting we multiply. I tried so but getting WA.

shah_entrance

My approach to PATHETIC which gives WA, which I don't know why.
we store two values in all the nodes depending on the below condition.
first_val = product of (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71) which is less then 10¹⁸
second_val = product of all 25 prime numbers less than 100 — product of (53,59,61,67,71) such that overall product lies under 10¹⁸.
1. Start DFS from Node 1 (we can start with anyone rather than 1)
2. If the level of the current Node is less than 23:
then we store the values as first_val in the node.
3. Otherwise,
we store the second_val in the node.
can someone please tell me why this is wrong?
UPD: Found my fault.

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71 is not less than 10^18 I think

upd: It's 29 570 863 996 715 044 931 273 015 670

chemthan

Stupid PATHETIC: I thought there is a novel solution. But it turns out to divide primes into two subsets.

RobeZH

I did centroid decomposition...

Basically if the tree is chain, you can just number the nodes in increasing order. Then for a tree generally, you can choose the centroid and color paths through the centroid like that, and solve for the subtrees.

It is a overkill, though...

Bohun

Nah, just random.

_Enigma__

I used brute force. Found all pairs distances using bfs from each vertex, and stored end-points of all paths such that their distance is a prime. (Distance is number of nodes for this question.)

Then for each prime, for each pair of endpoints, again retraced the paths using another bfs, and multiplied that prime to the smallest value node I found in the path.

+61

Root tree from some node. In node of depth $$$d$$$, write $$$(2d+2)(2d+3)$$$.

Wow, can you explain why it works?

+31

Consider any path of length $$$k$$$, there will be part of it of length at least $$$k/2$$$ that's going down (or up), so we multiply $$$k$$$ consecutive numbers there.

_pastor_

orz

AGRU

-6

Why is this valid and how did you come up with this observation, can you please explain :(

It is novel :)

peoplePleaser

For PATHETIC, I was considering all paths starting from a vertex u and using dfs kept on updating the node values, depending on the fact that the current path has product divisible by the current path length or not. I was getting WA. Can anybody suggest why this approach is wrong? Thanks in advance.

Newton

3 magic number to solve PATHETIC.

6746328388800 525737919635921 19657257924641

just place this 3 number in the nodes evenly(make sure first number in every alternate node)

swapnil159

You can actually do it with just 2 numbers.

Can you please elaborate ?

Coding-Enthusiast

how did you come up with the 2 numbers and what are the numbers ?

There are 25 primes , I took 6 largest primes and 7 smallest primes to group together but the other 12 were having the product larger than 2e18 so I exchanged 2 and 23 and it worked.

zeliboba

Problem BOJACK. Could you explain why in the sample answer for 63 is peanutbutter? Looks like value for peanutbutter is 60

Yeah. It should be 60. We didn't notice it earlier. Sorry for the mistake.

+14

Could you also provide your checker code? I stressed my solution, but it got wa. My solution is different from the most popular. If you want look into my solution, then my nickname on codechef is argos.

nishant403

I also have the same problem. If you find checker or anything else please do tell me

My hope ... gone!

teja349

+16

The mistake in sample was due to mistake in checker to count the number of palindromic substrings. We noticed it towards the end of the contest.

Maybe we should have made an announcement in that momemt about the issue.At that time we did not know the exact issue with checker, but it was working most of them. Hence, we waited for end of contest to do analysis abt the number of affected participants and then take decision.

We are rejudging that problem and looking at the affect.I think you were affected by it. I am still waiting for the results. once they come, we will take a call on the contest. Sorry for the issue.

Alpha_Q

I think I was affected by it as well (handle: nirjhor). I stress-tested my solution before submitting.

We have checked it.

8 users from Div1 and 1 user from Div2 have been affected. We feel it is a small number for other contestants to feel its affect. So we are going ahead with rating changes in both divs. these 9 users will be contacted by the team to know if they want the contest to be made unrated for them.

+52

About the mistake

Previous Checker

Correct Checker

Differrence

VladaMG98

The MEX problem: the solution for $$$ n = m $$$ is $$$ n + 1 $$$, the solution for $$$n < m$$$ is $$$\max (m + 1, 2n + 1)$$$. Am I making a mistake somewhere as I've got a WA or there are some corner cases?

Jakube

min instead of max. Right? Otherwise the limits are correct.

Check your solution for the the case $$$n == m$$$. Both for a $$$n = 1$$$ and $$$n > 1$$$. I had to handle this case slightly differently than my general construction.

Yeah, I wanted to place min instead of max -- yet I still don't know what case my code fails on. Thanks for the help.

+13

Had a look at your submission.

Check $$$n = m = 1$$$. You output is $$$0$$$, which is wrong.

Oh. God. It got accepted now, thanks so much :)

keep__calm

← Rev. 4 →

Can you please share your checker of BOJACK?
How does it check if a given string is valid?
Even my brute force O(n^3) checker was wrong.

P.S. — Combined round would have been better. Separate divisions exist so that div1 users arent forced to solve easier problems not the other way round.

SarthakAjmera

Can anyone tell what is wrong with following logic for "OR-thodox Distinction".

For the answer to be YES, each and every element of array must have atleast one bit set (equal to one) in its binary representation such that, this particular bit is set only and only in this particular element.

Formally, every ith element of array, the element must have some jth bit set in it, such that jth bit is not set in any other element of array.

TIA. Link to my submission : https://www.codechef.com/viewsolution/35786565

border

Check with this input:

9 5 6

The answer should be "YES" but your code returns "NO".

+87

One interesting way of getting a wrong answer and spending 20ish minutes debugging the code)

aryanc403

← Rev. 3 →

Weak test cases in EVENTUAL.
https://www.codechef.com/viewsolution/35780417
He just printed NO if n>70. Didn't even read numbers of that particular test case. This should affect further test cases. But looks like there is no "YES" after n>70 test case.

Counter testcase

2
100
1e18 100 times
3
1 2 4

Answer is NO\nYES but it prints NO\nNO

_maverick

+41

Apart from the complaints and ruckus all are posting. Problems of this cook off were excellent and of nice quality. Keep up this great work for all upcoming contests 0p9o8i. Codeforces div2 and cook off yesterday were so full filling.

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

6746328388800 525737919635921 19657257924641