csacademy's blog

By csacademy, 6 months ago, In English,

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.

Facebook event

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.

About the penalty system:

  • 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.

Don't forget to like us on Facebook, VK and follow us on Twitter.

 
 
 
 
  • Vote: I like it  
  • +53
  • Vote: I do not like it  

»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # |
  Vote: I like it +12 Vote: I do not like it

How people could solve E problem in 3 minutes?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    classic suffix array problem

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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, # |
  Vote: I like it +75 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yeah i solved C by copy the algorithm from a blog i read it yesterday. :D

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B using median ?
The only logic i can get is Ternary search.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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<string> 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 compare

    Code

    string getNodeCanoincalForm(int v, vector< vector<string> > &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<int> LeafNodes;
        vector<int> 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<string> > 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, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone explain how to solve D?