AK18's blog

Invitation to CodeRed — 2020 by IIIT Allahabad
By AK18, 5 years ago, In English

Hello everyone !!

After 3 successful editions, Aparoksha is back with flagship coding event — CodeRed.

CodeRed 2020 consists of 2 rounds, Online preliminary round and Onsite final round. The online preliminary round will be a 3-hour long team event with a maximum size of the team being 3 members. The participants need not be from the same college/institution/organization. Problem set has 6/7 problems of varying difficulty. CodeRed 2020 is scheduled at March 11, 2020 at 22:00 IST

Last year CodeRed 2019 had 1271 teams registered, we are expecting higher participation this year. You can register your team here — CodeRed 2020 online preliminary round.

CodeRed, Alkhwarizm (Rated for all CodeChef contest) and Humblefool cup (Which happened a few days ago on Topcoder) are all among flagship coding events of Aparoksha — Techincal fest of Indian Institute of Information Technology (IIIT), Allahabad.

The total prize money is worth INR 125,000. Also, top 3 teams in the online preliminary round will get INR 3000, 2500 and 1500 respectively. The best 40 Indian teams will make it to the onsite round (To be held in IIIT Allahabad). All teams making it to the onsite round will get Aparoksha T-shirts.

Please fill out this Registration form to avail prizes — Register here

Problems have been set and tested by Mridul Gupta — mridul1809, Shivam Garg — shivamg_isc, Vaibhav Srivastava — dbest077, Ravi Chandra — rc_4594 , Ashutosh Kaushik — AK18, Kumar Raju — Eunoia__1729, priyanshu kumar — priyanshupkm.

Editorial will be posted here after the contest.

PS: Please Ignore the timing on the poster.

Upd1: 250 laddus for each member of top 3 teams. 9 hours to go.

Upd2: 30 minutes to go

upd3: the contest has been extended by 30 minutes, filling the registration form is mandatory to qualify for the on-site final

Upd4: Thanks for the overwhelming response. :D

Congratulations to the top 3 winners :D
1. NTT — tempura0224, tatyam, noimi
2. fast_coders — acraider, nitixkrai, fsociety00
3. Minimum Spanking Tree — hitman623, Enigma27, _shanky

Hints for the problems, detailed editorials will be posted later.

Hints :

Kem Party : CORE2006
Bhaang Level Bam Bam Bole: CORE2005
Cancel Cancel Cancel: CORE2007
Bhand Goggi And GCD : CORE2002
GPL 69: CORE2001
Bhindi Master and Graph : CORE2004
Scinist issue : CORE2003
  • Vote: I like it
  • +77
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Looking forward to it.

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The participants need not be from the same college/institution/organization.

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hope this is as exciting as last year's.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is it from 9pm or 10pm?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    10 pm. Ignore the timing on the poster. sorry for the inconvenience.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Was $$${O(q*\sqrt{n}*log(n))}$$$ the intended complexity for Bhindi Master and Graph ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    nope

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Most likely there is $$$O(nlog(n))$$$ solution, however $$$O(nlog^2(n))$$$ passes easily.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Here is O(nlog(n)) solution. https://www.codechef.com/viewsolution/30325628

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you briefly explain your solution ?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          lets put all the vertices in the new array in order of distance from root. i.e. all vertices with distance 1 will come first, then all vertices with distance 2 and so on. now for finding minimum distance from root we need to query minimum index in the new array such that value at this index> value of query. We can do this with binary search + query on segtree in O(log^2(n)). we can also do this by doing binary search query on segtree. the rest part of the problem can be solved with just a set.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            I brute forced but it didn't gave me TLE but I was getting WA.

            Can you please explain what I was doing wrong.

            Approach : I listed nodes at each level in a array of vector.

            I made an array which contains the smallest element value at among the nodes at that level using the indexes.

            https://pastebin.com/ymNdB9Z3

            Here's the code

            vi adj[N], b(N, -1);

int bfs(int n){
	int visited[n +1] = {0}, lev = -1;
	b.resize(n +1);
	b[1] = 0;
	deque <int> q;
	q.push_back(1), visited[1] = 1;
	while(!q.empty()){
		int cur = q.front();
		q.pop_front();
		for(auto itr:adj[cur]){
			if(!visited[itr]){
				visited[itr] = 1;
				b[itr] = b[cur] +1;
				q.push_back(itr);
			}
		}
	}
	for(int i = 1; i <= n; ++i)
		lev = max(lev, b[i]);
	return lev;
}

int32_t main()
{
	int n, q, u, v, c;
	cin >> n;
	vi a(n +1);
	scnarr(a, n); // input array
	for (int i = 0; i < n -1; ++i){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int lev = bfs(n);
	vi level[lev +1];

	// at each index of Level array : elements at that level are pushed
	for(int i = 1; i <= n; ++i){
		level[b[i]].push_back(i);
	}

	vi  _min(lev +1, 1000000000000000005);

	//finding min elem in each level and save to the _min array
	for(int i = 0; i <= lev; ++i){
		for(auto itr:level[i]){
			b[itr] = i;
			_min[i] = min(_min[i], a[itr]);
		}
	}

	cin >> q;
	while(q--){
		cin >> c;
		if(c == 1){
			cin >> u >> v;
			a[u] = v;
			_min[b[u]] = 1000000000000000005;
			for(auto itr:level[b[u]]){
				_min[b[u]] = min(_min[b[u]], a[itr]);
			}
		}else{
			cin >> u;
			int i = 0, ans = 1000000000000000005;
			for(; i <= lev; ++i){
				if(_min[i] > u){ //found the level closest to root 
					for(auto itr:level[i]){
						if(a[itr] == _min[i]){ //if multiple answers exists take the one with lowest index
							ans = min(ans, itr);
						}
					}
					cout << ans << endl;
					break;
				}
			}
			if(i == lev +1){
				cout << -1 << endl;
			}
		}
	}

}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Why did you store min elem at each level? You should have stored max at each level.
              There may be a case as follows —
              Level 1 values — { 3 }
              Level 2 values — { 5, 11 }
              Level 3 values — { 6, 7, 8}

              If the query is 10, answer should be stored at level 2, but storing min as you have done will return -1.

              → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submitted using square root decomposition and it worked for me :)

    → Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve Kem Party problem fast? My solution complexity is $$$O(n * m * min(n, m) * log n)$$$ with dynamic convex hull trick, which seems to be overkill...

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +18 Vote: I do not like it

    I too used 2D-Fenwick Tree + Convex Hull Trick to solve in O(N*M*log^3n ). [Quite same in runtime i guess].

    With random weights, i don't think that the lines will follows some property allowing any offline processing.

    → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Great contest! Enjoyed the problems, even though I only solved 3. Can somebody explain the convex hull optimization trick used to solve Ken Party? Or show me a link that explains it? TIA

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain why I am getting WA in Bhindi Master And Graph, I store the nodes at each level and the max value at each level and then if max value of a level is greater than X, I print the smallest node with value>X.

Solution

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First of all, the complexity of your solution is Q*N which is not in the time limit :/

    now while you are updating the value of the node, you are changing the max if the current update is larger than max at that level, which is wrong, as there might be multiple nodes with same value at a certain level or maximum value at that level might decrease etc.

    keep values available at each level to update the maximum (to correct the logic of your code still it will exceed the time limit), to improve the complexity you may refer to hint posted above :)

    → Reply