atcoder_official's blog

Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368） Announcement
By atcoder_official, history, 3 weeks ago, In English

We will hold Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）.

We are looking forward to your participation!

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

»
3 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

It really feels like A<B<C<D<F<<G<<<E

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

    Wasted all my time on E, F was so easy.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      That's why it's useful to look at the leadeaboard. At minute 30 I noticed that F was like 3 times more accepted than E.

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

Bring back 'Aoki' and 'Takahashi'.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got cooked in this contest.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Imagine if you replaced every element of the array by its prime factorization. Then, replacing a number by a divisor just means that you take away some prime factors. Now, replace every number of the input by the number of prime factors it has, and the game is basically just a nim-game.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Consider a sequence $$$( A_1, A_2, \dots, A_n )$$$. For each prime $$$( p )$$$, let $$$( v_p(A_i) )$$$ denote the $$$( p )$$$-adic valuation of $$$( A_i )$$$, which is the exponent of the highest power of $$$( p )$$$ dividing $$$( A_i )$$$.

    By calculating this $$$ \sum_{\text{prime } p} v_p(A_i)$$$ over all primes $$$( p )$$$ for every $$$( A_i )$$$, the problem becomes equivalent to the classic Nim game.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    Use Grundy Theorem ( short explanation ) :
    Consider a graph, in which from node x you can go to node y then, the grundy function for each node = MEX of the grundy function of child nodes. and the xor of all grundy values determines the winning or losing state.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain E problem?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I don't know if this is the intended solution, but it is how I upsolved it.

    For each station, you can store the trains ending there, sorted by their original end time.

    You can also have a max segment tree of the trains ending there in this sorted order. This segment tree will store new end time (end time + delay).

    You then delay the first train and process the trains in order of their start time. For each current train, check the other trains ending at the current train start station. Look up in the segment tree the max end time+delay of all trains that end before the current train starts. Use that to delay the current train and update the segment tree for its end station.

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

      By the way, you can replace a segtree with a monotonic map: code. This data structure is similar to monotonic stacks and queues but supports arbitrary insertions. It also can be used to construct and maintain convex hulls, for example in the line container.

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

        why we can't just sort trains by A and after that we do a recursive call for each train (by that order) and for each node that node is going to start from from, we keep an index of the last X trains used (that are in an indegree with that node) , and we get the maximum time that they ll reach that Node, and this way we will process each indeg train for a node just one! this is my idea but I don't know why it TLES (on two tests) ( my complexity I assume is O((n+m)*log(m)), this is my submission sumbission link

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

      A (multi)map is enough to store the arrival times. When looking at the arrival times, merge the entries into one, that have a scheduled arrival time lower than the departure time of the current train. Trains are processed in increasing order of departure time, so the merging is unproblematic for the future trains.

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In my opinion, the order of the problems shouble be ABCDFGE

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

first time i solved F in an atcoder contest, very nice contest!

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

Problem E is so impressive !

At first, I thought that it is based on some algorithm associated with graph, like Dijkstra or something else, but kept getting WA or TLE.

Then, I convinced myself that "solving it based on graph algorithm" is just my mindset, which in fact I didn't have any proof.

Finally, I came up with another solution, which almost has nothing to do with graph. Note that a train TR1 can only be affected by another train TR2, if TR2's T <= TR1's S, where S and T are the time mentioned in the problem. So, we can deal with the "time" in an increasing order. For each time, at first, we deal with the trains that arrive at this time, and then deal with the trains that leave at this time. For any train that arrives at some city at this time, we update the maximum "arriving time" of this city, and then for any train that leaves some city at this time, we update its minimum "delay time" according to the city's maximum "arriving time". Note that as we handle everything in an increasing order of the time, the solution is always correct.

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

    that makes so much sense actually, thank you.

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

    I think in theory it could be solved by Dijkstra, if you build a graph where the nodes are trains and there is an edge between two trains A, B if A ends where B starts, and before B starts. The weight of the edge is the waiting time between A and B.

    Then compute shortest paths from the first train node. The delay for train X_i is max(0, X_1 — d(i)).

    This is just too slow as the train graph can have too many edges.

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

      I did it using a similar graph method. You can reduce the number of edges by instead creating a new node for every $$$(a, s)$$$ and every $$$(b, t)$$$ pair, then add edges of weight $$$0$$$ from $$$(a, s)$$$ to $$$(b, t)$$$, and add edges from all $$$(i, x)$$$ to $$$(i, y)$$$ such that $$$y$$$ is the smallest time after $$$x$$$ for node $$$i$$$, with weight $$$y - x$$$. The number of nodes and edges is then $$$O(n + m)$$$ and you can run some kind of Dijkstra on that graph. The solution given above is a lot cleaner though.

      Accepted submission

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

    I think that I have the same solution as you but it tle!: submission link

    my calculated complexity is O((n+m)*log(m)) I don't know why it tles

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell why this code gives runtime error for two cases:

https://atcoder.jp/contests/abc368/submissions/57100147

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide counter case for my solution in D?

Simply Root the tree at $$$1$$$, We can see for any two nodes to be in minimal tree, we must keep the vertices along their path to their $$$LCA$$$, If we had to add another vertex we must find the Common $$$LCA$$$ of our previous $$$LCA$$$ with the new vertex.

So simply, Find The common $$$LCA$$$ of all $$$K$$$ vertices, then count nodes starting from each needed vertex to the common $$$LCA$$$ by iterating over the parents, and keeping $$$visited$$$ set to avoid double counting, and revisiting the same vertices.

The submission

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

    Simply Root the tree at 1, this is the issue, the final tree might not contain 1.

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

      where is the problem? this is just essential step to compute $$$LCA$$$. The rooting mustn't be an issue since it's not part of the solution.

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

    take this example

    10 5
1 2
1 3
2 4 
2 5
3 6
3 7
7 8
7 10
8 9
3 6 7 9 4

    LCA of all K vertices will be 1 and so the minimum tree will be of 8 Nodes 1,2,4,3,6,7,8,9 but your code is giving 7

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

      THANKS!

      It's because of the case when $$$1$$$ is the common $$$LCA$$$, I don't handle it correctly because of my way of initializing the $$$LCA$$$.

      I can't imagine how much time I wasted which made me solve no more than 3 problems.

      Really appreciate your effort <3

      → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it
    Simple Testcase
    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I really appreciate your concerning, Thanks for the test. I see my fault now.

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

    Simpler solution would be to keep removing the leaves which don't belong to the special vertices. The final tree should be the minimal.

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

      I also thought at first in that approach, but some cases were hard for handling. And the common $$$LCA$$$ approach seems more easier and intuitive (at least for me) and it should have been no error-prone

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        My submision with XGptw logic
        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's really much easier, Thanks for the submission

          → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, for a train from u to v first we need to have the x values for all the trains from some station to u. We have a directed graph without any cycles. Use bfs to solve this, add a train to queue only when all the other trains to u have been processed.

Dont know why it is giving TLE

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
Your code here...
bool dfs(int src,int dest,int sz[],vector<vector<int>>&adj){
     int x = sz[src];
     sz[src]=x+1;
     if(src==dest) return 1;
     for(auto i : adj[src]){ 
         if(!sz[i]&&dfs(i,dest,sz,adj)) return 1;
     }
     sz[src]=x;
     return 0;
}
signed main() { 
    init;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);  
    #endif
    ll _ = 1;
    // cin >> _;
    while (_--) {
     int n,k; cin>>n>>k;
     vector<vector<int>> adj(n+1);
     for(int i=1;i<n;i++){
         int x,y;cin>>x>>y;
         x--;
         y--;
         adj[x].push_back(y);
         adj[y].push_back(x);
     }
     int a[n];
     in(a,n);
     int sz[n]={0};
     for(int i=0;i<k;i++){
         dfs(a[0]-1,a[i]-1,sz,adj);     
     } 
     int cnt=0;
     for(int i=0;i<n;i++){
        cnt+=(sz[i]>0);
     }     
     cout<<cnt<<endl;
  }  
}

Solution for problem D [Minimum Steiner Tree] why this solution giving me WA

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

Does someone use Systems of Difference Constraints to solve Problem E?

My submission

→ Reply