By csacademy, 6 months ago, ,

Hello, Codeforces!

We are going to host a new contest at csacademy.com. Round #73 will take place on Wednesday, March/14/2018 15:05 (UTC). This round will be a Div. 2, affecting users with a rating below 1800.

Recently, Facebook has reintroduced the possibility of recurring events. If you choose "Interested" here, you will be notified before each round we organise from now on.

#### Contest format:

• You will have to solve 5 tasks in 2 hours.
• There will be full feedback throughout the entire contest.
• Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
• Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
• Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

• Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
• Solutions that don't compile or don't pass the example test cases are ignored.
• Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

•
• +53
•

 » 6 months ago, # |   +23 Can you consider some timing variety while setting your contests? It's been like Wednesday every time for a long time with probably like one exception.I understand it's not possible for relatively new platforms to change their times, but perhaps alternate between two timings? (For example Wed-Wed-Mon-Wed). I really like your platform & problems but me, and probably many others miss your rounds because of that. I know no one time fits all, but if you somehow alternate, it's better.Hope you consider it, Thanks!
•  » » 6 months ago, # ^ |   +5 There is the 'Contest Preferences Survey' where you can set your preferred time (top right box on homepage). I wonder when they will publish/analyse results from it.
 » 6 months ago, # |   +12 How people could solve E problem in 3 minutes?
•  » » 6 months ago, # ^ |   0 classic suffix array problem
•  » » » 6 months ago, # ^ |   +13 Even if it is classis problem. I don't think that it is possible to code solution in such small amount of time.But I have read the chat after the contest and somebody has written that exactly the same problem was on some USACO contest not so long ago.So I think people just copy solution their or authors from there. I know that the rules didn't forbid it but it is kind of upset to see it is in the round.
•  » » » » 6 months ago, # ^ |   +16 Sorry! :P
 » 6 months ago, # |   +75 It was probably the first CSA round (that I participated) that was awful. If you don't have good problems for div.1 it doesn't mean that it's OK to host div.2 with generic problems like 'check if two rooted trees are isomorphic' and 'write suffix array'.
•  » » 6 months ago, # ^ |   +5 Yeah i solved C by copy the algorithm from a blog i read it yesterday. :D
 » 6 months ago, # |   0 How to solve B using median ?The only logic i can get is Ternary search.
•  » » 6 months ago, # ^ |   0 can u describe your idea of how to approach using Ternery search, Model solution proposed by author is too short if he also posted the proof of why both problems are equivalent that would be good.
 » 6 months ago, # |   0 is the definition of tree isomorphism defined here differs from ideal? how two tree are isomorphic if root are different? please clarify me. thanks.
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 i really didn't focus on the statement i got the answer from first and last testcase example its clearly appear a tree isomorphism algorithm there is two ways to solve it UPD : similar problem // Given 2 trees and roots for each one, are they isomorphism? // dfs(tree1, tree2) // General Method: compare(object1, object2) -> Canonical(object1) == Canonical(object2) /* * Graph (1-2, 1-3) and root 1 * 1 * 2 3 * 2 is () and 3 is () * 1 is ( () () ) * Graph (1-2, 1-3, 4-1, 4-5) and root 4 * 5 * 2 3 * 4 1 * 2, 3, and 5 are () * 1 is ( () () ) * 4 is ( ( () () ) () ) */ the code for that technique const int oo = (int) 10e5 + 1; vi adjLst[oo]; string treeCanoincalForm(int i, int par) { vector childern; for (int j : adjLst[i]) if (j != par) childern.push_back(treeCanoincalForm(j, i)); string nodeRep = "("; sort(all(childern)); rep(k,0, sz(childern)) nodeRep += childern[k]; return nodeRep + ")"; } The second one is more hard because What if no roots? Find roots! Tree has 1 or 2 centers maximum. so we may need maximum to 4 canonical form to compareCode string getNodeCanoincalForm(int v, vector< vector > &subCan) // we could use hashing for a better performance { string nodeRep = "("; sort( all(subCan[v]) ); rep(i, subCan[v]) nodeRep += subCan[v][i]; nodeRep += ")"; return nodeRep; } /* * Tree shrinking algorithm. Each time leaves shrink toward their parents. */ string treeCanoincalForm() // assumes tree not forest { int n = sz(adjLst); // Prepare level one nodes: the leaves queue LeafNodes; vector deg(n, -1); int remNodes = n; rep(i, adjLst) { if(sz(adjLst[i]) <= 1) LeafNodes.push(i); else deg[i] = sz(adjLst[i]); } vector< vector > subCan(n); while(remNodes > 2) // bfs-like { int sz = sz(LeafNodes); while(sz--) // level by level { int v = LeafNodes.front(); LeafNodes.pop(); string nodeRep = getNodeCanoincalForm(v, subCan); rep(j, adjLst[v]) { int to = adjLst[v][j]; subCan[to].push_back(nodeRep); if(--deg[to] == 1) LeafNodes.push(to); } --remNodes; } } // what remains are tree centers int v1 = LeafNodes.front(); LeafNodes.pop(); int v2 = LeafNodes.empty() ? -1 : LeafNodes.front(); string str1 = getNodeCanoincalForm(v1, subCan); string str2 = v2 == -1? "" : getNodeCanoincalForm(v2, subCan); if(v2 == -1) // only 1 node return str1; // 2 nodes. try 2nd as child of first and reverse subCan[v1].push_back(str2); subCan[v2].push_back(str1); return min(getNodeCanoincalForm(v1, subCan), getNodeCanoincalForm(v2, subCan)); } 
 » 6 months ago, # |   +8 Can anyone explain how to solve D?