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

Автор chokudai, история, 4 года назад, По-английски

We will hold AtCoder Beginner Contest 170.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится

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

how to explain the first example of problem D?

thanks a lot.

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

omg, My code won't even give an o/p locally but when I submit, it got accepted in Q D. xD

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

How can i see judge test cases after a contest in atcoder ?

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

Problem F is the same as this

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

Editorial:

A
B
C
D
E
F
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thank you for editorials!

    i quite didn't get the heuristics you used in problem F: can you please write what happens when you move from dp[x][y] to dp[x + 1][y], how are your sets changing? how can your sets be defined? thanks.

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

      When moving from dp[x][y] to dp[x + 1][y] only if dp[x+1][y] hasn't been updated yet,you can use sets to find it.

      Then the cell->[x+1][y] is deleted from the set which represents column y as well as the one represent row x+1.Because [x+1][y] has been updated now!

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

    In problem E multiset can be used instead of segment tree, because u need to know min over all array and can keep all top values in multiset.

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

    In problem F, I don't understand how are you updating all possible [m][n] for state [i][j] which satisfies all three conditions, I tried it using loop from 1 to K resulting in complexity of O(H*W*K) :(

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

For the D problem- Let us sort the array first. Now, let's iterate through the array from the beginning. After that, the idea is to maintain a map that will store all the values that have a)appeared in the array itself b)or are multiples of those elements that have originally appeared so far, that are less than 1e6. Time Complexity-0(N*(log(1e6))), which is equivalent to an O(N) complexity Here's my submission- https://atcoder.jp/contests/abc170/submissions/14321810 Also, for the E problem, do we have to maintain a vector of priority queues?

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

How to solve F?

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

    It's shortest path with the following optimizations:

    1) You never want to go backwards

    2) You never want to try something in the same direction, you could have just computed that before.

    My submission for F

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

Are heuristics expected to pass for F?

submission

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

Was F bfs but I think time complexity will be more with BFS solution

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

In problem D , i tried to solve by marking all multiples of numbers in array . But it gave TLE . I guess it is O(nlogn) (because it corresponds to harmonic series). submission

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

I have solved all problems in a contest for the first time. Hurray!!! Here's my idea for F:

Spoiler

My submission: link

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

    Interesting idea. The reason this greedy modification works better than normal bfs is that every cell gets visited at max 4 times in your solution

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

E was a heavy implementation problem?

Upd : WA/RE teaches a lot.

Learned, why should we refactor our code. Make separate functions for the repeated tasks.

AC

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

    :( ,I think it's more like a basic data structure problem.

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

      I used sorted maps i.e (TreeMap in java ) for everything, maintained sorted lists for everything. But its just failing for 1 tc i.e random_case

      Submission

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

        I must have done many unnecessary things, cause it took me a hell lot of time code this.

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

        Here are 2 small cases where your submission fails:

        Test 1
        Test 2
»
4 года назад, # |
Rev. 3   Проголосовать: нравится -30 Проголосовать: не нравится

.

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

    This is not a way to ask doubt you should not spam discussion with full code just post link of your code and try to explain your logic a little bit.

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

I created lot of treemaps and hashmaps in E and I was shocked that my code worked on the 1st go, the code got unbelievably complex though. In F, the naive BFS solution gave TLE on 2 test cases only. How to solve it efficiently?

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

    Naive bfs complexity will be O(h*w*K), which will TLE. I have explained my O(h*w*4) solution in this comment.

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

    Keep sets for unvisited cells (for each row and for each column), and remove cells when you add them to the queue. Then you would only look at every cell once. This introduces a logarithmic factor, but also removes the dreadful factor of $$$k$$$ in the naive solution.

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

How to Solve F ?

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

I learnt after wasting 40 minutes in problem E that, multiset.erase() removes all occurrences of a given value from the multiset. To erase a single element, use this:

multiset<int> s;
s.erase(s.lower_bound(value));
//Make sure value is stored in the multiset!!
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    This is why I use map to store number of occurrences and erase the key once no. of occurrences becomes 0.

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

    An alternative, if you don't want to worry about whether or not the value is present in the multiset:

    multiset<int> s;
    auto it = s.find(value);
    if(it!=s.end())
       s.erase(it);
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yea I also learned this today in problem D

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

    or s.erase(s.find(value));

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

-->For d solution i came up with this solution

-->Created a map for count of given integers,for any number check whether its divisors present in map (or) when its count is >1 function returns false else increment count

-->solution :link

-->it passed 27 test cases and wa for 22 can any one tell what i have missed??? or corner test cases i have missed??

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

    Try this test case

    Test case

    the answer should be 0 but your code's output will be 1

    another test case where your code will fail

    Test case

    the answer should be 0 but your code's output will be 1

    Accepted code link

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

https://atcoder.jp/contests/abc170/submissions/14329950 https://atcoder.jp/contests/abc170/submissions/14331317

The first submission for problem D gives me TLE, but when I replaced at line 172, MAXN = 10^6 with the real maximum of the input, second submission got accepted and actually the difference in time is huge. Why is that? It seems really strange to me. I spent too much time on that and I was kinda lucky to come up with that replacement because I was sure that the complexity is sufficient.

Thank you !

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

How to solve problem E of todays contest ?

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

    Maintain a multiset for each kindergarden and one multiset for the maximums of the kindergardens. Now at every query you just need to insert/erase only from three multisets.

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

In problem d I thought checking all the factors will give TLE. but when 10 min was left I thought maybe I should submit the solution with TLE but rather it got accepted.

lesson learned : analysis of time complexity should be done carefully.

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

Did anyone solve D in O(n * sqrt(n))?

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

    I did

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

      can you give the link to the code/submission?

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

        Link

        Useful Code in case if you find hard to read my JAVA template,

        int n=ni();
        HashMap<Integer,Integer> hm = new HashMap<>();
        int[] arr = new int[n];
        for(int i=0;i<n;++i){
            arr[i] = ni();
            //hs.add(arr[i]);
            if(hm.containsKey(arr[i])){
                hm.put(arr[i],hm.get(arr[i])+1);
            }
            else{
                hm.put(arr[i],1);
            }
        }
        int ans = 0;
        for(int i=0;i<n;++i){
            if(hm.get(arr[i])==1){
                boolean pos = false ;
            for(int j=1;j*j<=arr[i];++j){
                if(arr[i]%j==0){
                    if(j*j==arr[i]){
                        if(j==arr[i]) continue ;
                        else{
                            if(hm.containsKey(j)){
                                pos =true ;
                                break ;
                            }
                        }
                    }
                    else{
                        if(j != arr[i]){
                            if(hm.containsKey(j)){
                                pos = true ;
                                break ;
                            }
                        }
                        if(arr[i]/j != arr[i]){
                            if(hm.containsKey(arr[i]/j)){
                                pos = true ;
                                break ;
                            }
                        }
                         
                    }
                }
            }
            if(!pos) ans++;
            }
        }
        pn(ans);
        
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You can check out the C++ implementation of the same here! Submission for D

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

Lesson learned from D:

std::unique does not change vector size! must change it by myself.

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

is memory limit exceeded will show as RE at atcoder ? PS. I am getting RE for the only 1tc in problem E i.e random_10, can someone give me some corner cases? But I feel as setter must have added those corner cases in test files,this RE must be because of Memory Limit.

Submission

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

Messed up big tym n now, messing up on atcoder has become a habit :-(

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

Approach for Problem D — create frequency array for all elements and then check for each element whether any of its divisor is present in the array or not

Gives tle in one case and few wrong test cases

Link : https://atcoder.jp/contests/abc170/submissions/14362767

Any Suggestions ?

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

In Problem F, I understand the solution where one can keep a set for every row and column, to prevent visiting a single cell multiple times.

But, after looking at some codes, I realised some solutions broke their loop if dist[cr][cc] + 1 > dist[r][c] where (cr, cc) is the current cell and (r, c) is the cell to be visited, from the current cell.

For, instance checkout this submission.

I understand the correctness of the solution, but I do not understand how this solution will pass the time limits.

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

when will they release the English editorial?

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

Can someone explain how the complexity of D is O(N*logN) (or O(N*sqrt(N)) from what I saw in other questions)? Shouldn't it be even bigger than N^2 (e.g. when I check for multiples of 1)?

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

Can Anyone explain me D Part pls?

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

    First try to solve it for distinct elements.Traverse the multiples of every element and check whether this multiple is present in your array or not. If it is present then mark in your visited array that this element will not contribute in my answer. Your answer will be the n — sum(visited, visited + 1e6)

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

Is it possible to find english editorials for ‌AtCoder contests? I want the editorial for E and F.

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

    Just copy the Japanese text, and google translate it! I did the same, I think it's manageable

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

    check the editorial now, they have added english editorial too

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

Can someone provide some test cases for problem F?

Here is my submission (though i don't think it will help), I've used a dijkstra-based approach here.

My solution passes all TCs except 3, so i suspect that it may be failing on a corner case.

Any Help is appreciated.

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

Where can I get editorials for the contest in English?? Specially for problems E and F!

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

Problem F is the same as 877D - Olya and Energy Drinks!

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

For Problem D:

It could be done so easily using dp and sieve method. Couldn’t realise on contest time :') Though dp is really <3 . Submission

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

Test cases of the contest are not seen on dropbox. It shows that the file extension is not correct. Please fix it chokudai.

I had faced a similar problem to open test case file on other contests too.

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

Here is my submission for problem E. I used the approach of having vector of multisets and erasing the maximum and inserting again for every kindergarden using the approach mentioned in the tutorial, but i am getting TLE. Can someone help me why i am getting TLE.

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

Why my solution is wrong for problem D?

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

What's wrong in my F submission?

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

    A small test for which your solution fails:

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

Can someone provide me the link to that AC code for problem E in today's beginner contest which has used ordered multiset ( i.e. they should have used policy based data structures ) ?

It would be of great help.

I have solved the question using STL's multiset....but it's just that I'm curious about using them.

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

My accepted solution for Olya and Energy Drinks gives wrong answer on 2 testcases of problem F while the one using std::set approach passes. Why? :/

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

    A small test where your solution fails:

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

    MikeMirzayanov It seems like the problem 877D - Olya and Energy Drinks has weak test cases.

    My AC submission on codeforces also gave WA on AtCoder. An example of a failed test case is the following one provided to me by dush1729:

    Input
    Expected Output

    The following submission of mine outputs 5: 47925337, but it still gets AC on codeforces. I request you to add the above test case to 877D - Olya and Energy Drinks

    EDIT: Here's another test case which ShafinKhadem has mentioned in the comment just above mine:

    Input
    Expected Output

    My AC code 47925337 outputs 11 on this.

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

Why my submission for F works corectly locally, but CE on atcoder ?

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

    Which compiler are you using to compile locally? Your code gives me compile error locally, when I use GCC 9.3.0.

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

      gcc 5.1.0, is my version too old ?

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

        I won't say too old, but I think it's better to use updated version.

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

        Hi, I just tried compiling your code using GCC 5.1.0 too in godbolt. It gives compile error there. But in codeforces custom test, it compiles successfully. Which operating system are you using? Maybe your code gives CE only in linux.

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

          I think you're right, my operating system is win7.

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

          I found the reason! There is a header file called mathcalls.h in Linux and it has a function declared as double y1(double), so we cannot use #include<bits/stdc++.h> and declare y1 as a global variable at the same time in Linux!

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

          Thanks a lot!

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

Can someone please tell what is wrong in my code for problem F? Link to my submission-->Link Any help will be highly appreciated.

Thanks!

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

Hey ! Please provide copy button (for sample test case in Tasks for printing).

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

If anyone need Problem D explanation with complexity analysis Here

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

Can someone help me with the code of problem F?

first second

I dont konw why the second code will get wrong answer.The only difference between them is the transfers about direction.I think it just needs more time to run but not to mislead the answer. Can someone help me plzzz?Thanks a lot.