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

Автор AK18, 5 лет назад, По-английски

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
  • Проголосовать: нравится
  • +77
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Looking forward to it.

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Hope this is as exciting as last year's.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is it from 9pm or 10pm?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    nope

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you briefly explain your solution ?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            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;
            			}
            		}
            	}
            
            }
            
            
            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :)