maroonrk's blog

By maroonrk, history, 5 weeks ago, In English

We will hold ACL Contest 1.

The point values will be 300-600-600-800-900-1800.

As mentioned in this blog, you may use the library in the contest. However, it's not mandatory to install the library or learn C++; I've verified that all problems can be solved with python(pypy3).

I also tried hard to ensure the quality of the problems, and I believe that you can enjoy tasks as a usual AtCoder contest, rather than yet another practice contest. In addition to that, I would like to mention the last problem, which is unusually hard for ARC-rated contests, and we welcome >2800 coders to challenge it.

We are looking forward to your participation!

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for an amazing round!!

»
5 weeks ago, # |
  Vote: I like it +122 Vote: I do not like it

Our initial plan was to prepare tasks that require standard applications of the contents of the library, and make a practice contest for intermediate people while advertizing the library.

However, we changed the plan because we want to advertize it for strong people too, and improved the quality of the problems to make a contest that is worth participating for them too. maroonrk even refused to use some fine tasks that are acceptable for ARCs.

So, expect something between an AGC and an ARC!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    As a beginner-intermediate coder, i’m not sure the contest was beginner friendly, if it was intended to be fun for beginners.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Video on how to use Atcoder library. Looking forward for the contest!

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

Please also kindly update kotlin version to 1.4.0. Thanks in advance

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Kinda unrelated but do you have any plan to change the rating system so that we don't get 0.00000000001 delta for accounts with lots of rated contest participation?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Isn't atcoder's less shaky rating system better in some cases? For example, it prevents extreme positive delta from ABC. It also prevents extreme negative delta for one bad performance (can happen for network error, power loss etc.). As Atcoder has different time penalty from other OJs, contestants can easily submit at end of contest / when certain that their rating won't drop much. I think a less shaky rating system encourages participants to not worry about rating much.

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

      Yes it's better in those very specific cases I suppose..

      I don't see any reason to make participants not worry about their rating. All that they have to do for that is make a throwaway account and participate with it.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Yeah, the codeforces system where your rating is determined by last 5 rounds is better :sarcasm:

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      I don't think CF's system is better, but I think on AtCoder the effect is too strong. If I recall correctly, old contests from 2017 hold me back by about 100 points despite being mostly irrelevant.

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

      I think your current rating is supposed to represent how good you are now, not how good you were in the past (we have the rating graph for the latter). So I actually do think that determining your rating based on the last 5 rounds is better.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +34 Vote: I do not like it

        My rating was 3548 on 29.04.19, 3001 on 21.06.19 and 3494 on 23.09.19. What's more likely in your opinion: I went from one of the strongest CPers to almost-not-nutella and back in 5 month or CF rating is broken?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +25 Vote: I do not like it

          I'd say it's more weird for you to not lose bunch of rating from 3.5K when you had few 3K performances in a row.

          Like suppose if an orange coder starts participating with your account. In my opinion, a "decent" rating system should be able to detect it from recent few performances that the guy is orange-level and adjust the rating of your account accordingly, not get stuck at high rating just because that account has huge number of past rated contest participation.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +29 Vote: I do not like it

            I don't agree. Rating is a measure of your strength. Obviously everyone has stronger and weaker sides, and it can happen that there are several rounds in a row where one has bad performance, and it shouldn’t disturb the rating a lot. Of course, it should gradually become lower, but overall the rating should be stable against several bad or good contests in a row.

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

              I'm not sure why do you think that one's rating should be stable. One's strength (in CP) can fluctuates depending on his condition at the time he's taking the contest.

              It could be because of unfavorable contest time, or maybe he ate some food gone bad, or he could have some bad performances on one of recent contests and can't think straight because of it.

              In this regard, I'd argue that any rating system which tries to adjust this fluctuation artificially, does not reflect one's strength at that time well.

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

                Ok, we have different views on rating. I don't understand yours to be honest, but that's fine with me, I don't care.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the full form of ACL? Like we have ABC (Atcoder Beginner Contest). What does ACL stand for?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial plzz

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can I use DSU to solve A? Why it is wrong?

code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I solved it via monotonic sets, I didn't try for any other approach though

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    If you think of it as a permutation, reverse it, now each connected component is an interval of both indices and values so a component ends every time the maximum of the first $$$i$$$ elements is equal to $$$i$$$.

    Code
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes! Thank you very much! My solution is realy close to the yours.But I don't know why I didn't realize this mistake during the contest!

      Problem A took me 2 hours:(,And after I solved B ,there is no time left!!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Instead of inserting the current secondary (which is not used in sorting) co-ordinate we have to insert the minimum secondary co-ordinate of the set in which the current index belongs. My Submission

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

    A has the same idea and solution basically as Moo Particle, a problem from a recent USACO contest here: link

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank You for the super fast editorial!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is "doubling" from problem D's editorial?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    like binary lifting, I guess

    but can somebody explain what is a and b? UPD: I got it — first and last chosing

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

    Binary lifting.

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

    The editorial has been fixed. (s/doubling/binary lifting/g)
    Thanks!

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

This is the tutorial for A

Unfortunatly I do only understand the $$$O(N^2a(n))$$$ solution. Can somebody explain the $$$O(Na(n))$$$? That loop looks like $$$N^2$$$ to me, I get something wrong.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I think there's something wrong with the Editorial, you can check my solution of dsu.

    code
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 7   Vote: I like it 0 Vote: I do not like it

      My algorithm for A (TLEs) is similar to the dsu editorial, and Id say use the same complexity.

      Here is my submission https://atcoder.jp/contests/acl1/submissions/16918995

      BTW for B we can do better than sqrt with bitmasks

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I think the $$$ O(N\alpha(N))$$$ solution in the editorial indeed should be more clear.

      Suppose I have $$$(1,N),(2,N-1),\cdots,(N,1)$$$, the algorithm must traverse every pair of points, which is $$$O(N^2)$$$ and would TLE.

      I actually feel bad because I found the $$$x_i=i$$$ idea but couldn't finish :(

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

    What do they even mean by a(n) ? Is that some fancy way to denote logarithm and slower functions?

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

    you can refer my code link- https://ide.geeksforgeeks.org/ZV03mZTlG2

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

can someone please explain me the solution of problem B

  • »
    »
    5 weeks ago, # ^ |
    Rev. 6   Vote: I like it +7 Vote: I do not like it

    (If you have any suggestions or corrections feel free to comment below, I'll fix)

    Notation: $$$A\backslash B=$$$ the set of elements contained in A that are NOT in B.

    I actually found the official solution quite unintuitive, so here is my (slightly faster) approach.

    Factorize $$$2N=\prod_{i=1}^n p_i^{e_i}$$$, where $$$p_1,\cdots,p_n$$$ are distinct prime factors of $$$2N$$$. For convenience, let $$$q_i=p_i^{e_i}$$$ for $$$1\le i\le n$$$.

    Let $$$[n]$$$ be the set of positive integers from $$$1$$$ to $$$n$$$

    We need $$$\prod_{i=1}^n q_i \mid k(k+1)$$$. Since $$$\gcd(k,k+1)=1$$$, suppose $$$S\in [n]$$$, $$$q_i\mid k$$$ if and only if $$$i\in S$$$, then since $$$\prod_{i\in [n]\backslash S} q_i\mid k(k+1), \gcd(\prod_{i\in [n]\backslash S} q_i,k)=1, \prod_{i\in [n]\backslash S} q_i \mid k+1$$$.

    Let $$$Q_S=\frac{2N}{P_S}$$$.

    We can now easily compute $$$k+1$$$ with modular inverses; let $$$P_S=\prod_{i\in [n]\backslash S} q_i$$$, then $$$\gcd(P_S, Q_S)=1$$$, suppose $$$x\equiv Q_S^{-1} (\bmod\; P_S)$$$, then $$$k+1=xQ_S$$$ works because $$$\frac{2N}{P_S}\mid k+1$$$ and $$$xQ_S\equiv 1(\bmod\; P_S)$$$ by the definition of modular inverse.

    There are less than fifteen distinct primes that can divide an integer $$$\le 2\cdot 10^{15}$$$, so this can be done in approximately $$$\omega(2N) \cdot 2^{\omega(2N)}\le 15\cdot 2^{15}$$$ operations, which is fast enough.

    Code
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You said

      We can now easily compute ... $$$k+1 = x \cdot \frac{2N}{P_s}$$$ works

      Why? How did you reach that conclusion? Also, what do you mean by the notation $$$i \in [n]$$$ \ $$$S$$$? All the elements in $$$[n]$$$ but not in $$$S$$$?

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Could someone kindly explain approach with $$$O(KNM log(NM))$$$ complexity mentioned in official tutorial? Thanks in advance!

btw, I built graph with $$$O(K+NM)$$$ vertices and $$$O(KNM)$$$ edges and run mincost-maxflow on it during contest, but it turns out to be TLE. :(

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    same graph — 50ms (used atcoder implementation)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +16 Vote: I do not like it

    From the source, add edges to pieces with capacity 1 and cost 0. From all the feasible final positions to destination, add edges with capacity 1 and cost 0. From a feasible position to another feasible position to the down or right, add an edge with capacity infinity and cost -1. (Feasible position is any a[i][j] != #).

    Find the minimum cost flow in this graph. I am unsure how to implement this with atcoder's min cost flow (I spent 15 mins thinking about why it isn't working, and the answer is because they require cost >= 0).

    Anywya, here's my in contest implementation: https://atcoder.jp/contests/acl1/submissions/16916600

    I would be grateful if someone would explain how to do this using atcoder's template.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Just add edge with cost T+cost, and after all mincost is mincost-T*maxflow

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

        But then the minimum cost would be when the pieces don't move from their initial position at all. It wouldn't flow through the edges as it doesn't reduce the cost

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

          i guess missunderstanding, I mean cost = -distance

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Is it possible for you to do a submit and send it here? Sorry, but I don't fully get your point, and the code is really short after using atcoder library.

            Unsure if you are referring to this idea: https://atcoder.jp/contests/acl1/submissions/16752194 which is a bit different, I guess

            Edit: rereading your comment, I guess you do mean the submission I referted above. Never mind then, that doesn't fully resolve my initial question :(

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              yes, different. for each o I calculate distance from o to cell that can be reached and add edge with flow=1 and cost=-distance

              flow graph is S -> L -> R -> T

              where L is start positions of 'o'

              R is possible finishes

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Screencast of barely missing out on 69th place :(

(also video solutions for A-D)

»
5 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

So, you made a maxflow problem for 600 points. Why?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    why not?

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

      If 600 point problem is supposed to 1900-2100 rated problem then why there should be maxflow? I was recommended to learn maxflow after reaching master

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Because you don't need to know how max flow works, only what it does(in this case finding max weight bipartite matching); the implementation is in the atcoder library.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        Well this contest is specifically named "ACL" which means anything in the atcoder library can appear.

        Also, I think the advices like "do not learn ~~ until you reach master" should be interpreted as "it's better to focus on 'thinking' side of problem solving rather than knowledge side to reach master", which is true. Do not interpret it as "learning is bad till master" because that's not true. I bet majority of the people who learns flow in this planet don't even have a cf account.

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

        Also, after you do the practice contest max flow problem, this one has almost the same idea anyway.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel like B is the easiest and the most straightforward, but A quite challenging.

BTW, can anyone hack the following "greedy" algorithm for C? It WAs but I can't find a counterexample.

The algorithm: scan points by rows from bottom to top, on a row I scan from right to left. Suppose I encounter a piece. I place it in the furthest place from it such that below and to the right are either an obstacle or a piece.

If this is not specific enough, see my code: https://atcoder.jp/contests/acl1/submissions/16920848

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

    As with most incorrect greedy solutions, some decisions you make greedily will lead to a greater loss in the future.

    Test:

    4 3
    ..o
    ..o
    o..
    .##
    
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ABC > ACL ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

rated range ?

»
5 weeks ago, # |
  Vote: I like it -51 Vote: I do not like it

Hey guys, I was trying to solve Problem A using DSU but i'm getting WA on 5 testcases.

I m following editorials O(N a(n)) approach..

#include <bits/stdc++.h>
using namespace std;

#define int long long

class DSU
{
	private:
	static bool verbose;
	int sz;
	vector<int> rank, parent, sizes;

	void printComponent(int id)
	{
		cout << "Component " << id << " size: " << getSize(id) << " | ";
		int p_id = Find(id);
		for(int i = 0; i < sz + 1; i++)
		{
			if(p_id == parent[i])
			{
				cout << i << " ";
			}
		}

		cout << endl;
	}

	void printMessage(string s)
	{
		cout << "================================" << endl;
		cout << s << endl;
		cout << "================================" << endl;
		cout << endl;
	}

	public:
	DSU(int n)
	{
		sz = n;
		rank.resize(n + 1, 0);
		parent.resize(n + 1);
		sizes.resize(n + 1, 1);

		for(int i = 0; i < n + 1; i++)
		{
			parent[i] = i;
		}

		if(verbose)
			printMessage("DSU Initialised.");
	}

	int Find(int i)
	{
		// use path compression
		if(i != parent[i])
		{
			parent[i] = Find(parent[i]);
		}

		return parent[i];
	}

	void Union(int i, int j)
	{
		int i_id = Find(i);
		int j_id = Find(j);

		if(i_id == j_id)
			return;
		
		if(rank[i_id] >= rank[j_id])
		{
			if(verbose)
				printMessage(to_string(i_id) + " size: " + to_string(sizes[i_id]) + " <-------------- " + to_string(j_id) + " size: " + to_string(sizes[j_id]) + " Final Size: " + to_string(sizes[i_id] + sizes[j_id]));
			sizes[i_id] += sizes[j_id];
			sizes[j_id] = 0;
			parent[j_id] = i_id;

			if(rank[i_id] == rank[j_id])
				rank[i_id] += 1;
		}
		else
		{
			if(verbose)
				printMessage(to_string(j_id) + " size: " + to_string(sizes[j_id]) + " <-------------- " + to_string(i_id) + " size: " + to_string(sizes[i_id]) + "Final Size: " + to_string(sizes[i_id] + sizes[j_id]));
			sizes[j_id] += sizes[i_id];
			sizes[i_id] = 0;
			parent[i_id] = j_id;
		}
	}

	void Print()
	{
		for(int i = 0; i < sz + 1; i++)
		{
			printComponent(i);
		}
	}

	int getSize(int i)
	{
		return sizes[Find(i)];
	}

	static void Verbose()
	{
		verbose = true;
	}
};

bool DSU :: verbose = false;

int32_t main(int32_t argc, char *argv[])
{
	if(argc == 2)
		DSU::Verbose();

	int n;
	cin >> n;

	vector< pair<int, int> > arr(n);
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i].first >> arr[i].second;
	}

	vector< pair<int, int> > temp = arr;

	sort(temp.begin(), temp.end());

	DSU dsu(n);

	// left pass
	int minm = temp[0].second;

	for(int i = 1; i < n; i++)
	{
		if(minm < temp[i].second)
		{
			dsu.Union(minm, temp[i].second);
		}
		else
		{
			minm = temp[i].second;
		}
	}

	// right pass
	int maxm = temp[n-1].second;
	for(int i = n-2; i >= 0; i--)
	{
		if(maxm > temp[i].second)
		{
			dsu.Union(maxm, temp[i].second);
		}
		else
		{
			maxm = temp[i].second;
		}
		
	}

	//dsu.Print();

	for(int i = 0; i < n; i++)
	{
		cout << dsu.getSize(arr[i].second) << endl;
	}
	return 0;
}

Can anyone tell where i am making mistake :(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain the O(N *a(n)) solution for problem A? I didn't understand the editorial.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have problems solving C with min cost flow? I used the code in the Atcoder Library and it gives wrong answer for even a simple test case like this:

1 3

o..

The answer should be 2 while the code gives me 1

I used the same logic but change the code to cp-algorithms.com and it gives the correct answer.

The code used Atcoder Library: https://atcoder.jp/contests/acl1/submissions/16973939

The code used another source and give correct answer: https://atcoder.jp/contests/acl1/submissions/16973807

Both of them use the same logic.

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

    I just explained above in this thread in detail the same issue.

    TL; DR: You can't add negative cost edges in atcoder library.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

please someone tell me why i am geeting wrong ans in my code in problem A. link--https://ide.geeksforgeeks.org/Pwzi10u0Y5

»
3 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

I think the ACL Round is useless.

You cannot use the ACL in big contests like IOI or some other websides like codeforces. If you use the ACL for a long time, you will forget the algorithms quickly.

So I think you shouldn't learn to use the ACL.