Comments (13)
I would like to propose assigning invertible (2,2) matrices to vertices and edges.
Finding the inverse of all matrices can be done in
On the other hand, in competitive programming problems, I think groups are often commutative groups or sets of affine transformations in the form of
Furthermore, even if there are problems similar to those on AOJ, it would be fine to place useful problems all in the Library Checker.
from library-checker-problems.
How about
Unionfind with Potential
Unionfind with Potential (non-commutative group)
from library-checker-problems.
Thank you!
Since this data structure can handle groups (not limited to commutative groups), I want to deal with non-commutative groups.
Here are some examples of the types of problems we can consider:
Each vertex has values
[Query 1]
Given
This means the information
This information is valid if it does not contradict any previously valid information.
Output whether this information is valid or invalid.
[Query 2]
Given (u, v, x). Based on the previously valid information and assuming x[u] = x, determine x[v] or print -1 if it can't be determined.
from library-checker-problems.
Seems nice, but to compute the inverse of affine would require computation of modulo inverse, which would make the time complexity increase from
from library-checker-problems.
this problem already exists here https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B if you want to test your library on it
from library-checker-problems.
The problem I proposed was flawed. The fact that a cycle was formed where the composition is not the identity map only determines the values at the vertices of the cycle and does not necessarily indicate a contradiction.
It might be better to associate the group elements directly with the vertices. A (2,2) matrix might be easier for the general user to understand than an affine transformation.
from library-checker-problems.
So if I understand correctly, entry of matrix on vertices would be some variable while entry of matrix on edges would be some constant?
from library-checker-problems.
Yes
from library-checker-problems.
Problem 1
未知の整数列
0 u v x
:列
この情報が valid であるとは,これまでの valid な情報に矛盾しないことを意味する.
この情報が valid であるか否かを出力せよ.
1 u v
:これまでの valid な情報をもとに -1
を出力せよ.
Problem 2
0 u v x_{00} x_{01} x_{10} x_{11}
:列
この情報が valid であるとは,これまでの valid な情報に矛盾しないことを意味する.
この情報が valid であるか否かを出力せよ.
1 u v
:これまでの valid な情報をもとに -1
を出力せよ.
Problem 1
There is an unknown sequence of integers
0 u v x
: You are provided with information that
1 u v
: Based on the valid information provided so far, output the value of -1
.
Problem 2
There is an unknown sequence of
0 u v x_{00} x_{01} x_{10} x_{11}
: You are provided with information that
1 u v
: Based on the valid information provided so far, output the value of -1
.
from library-checker-problems.
I think I can prepare them
from library-checker-problems.
Thank you, and I appreciate your help. If you have any questions about the preparations, please feel free to ask.
from library-checker-problems.
how should we naming these two problem? I was thinking using
- Unionfind with Potential (commutative group)
- Unionfind with Potential (non-commutative group)
or maybe specify which group are used in (...)? In such case, what should it be? (I'm not very familiar with abstract algebra)
from library-checker-problems.
If you want to avoid calculating the inverse, you can include the constraint
from library-checker-problems.
Related Issues (20)
- [Problem proposal] All Farthest Neighbors in Convex Polygons HOT 6
- 問題案 Incremental SCC HOT 2
- testcase for RMQ: add test where there exists a subarray with multiple minimums HOT 4
- 【テストケース】Furthest Pair of Points HOT 1
- [テストケース案] Consecutive Terms of Linear Recurrent Sequence
- [テストケース] Closest/Furthest Pair of Points のケース near_grid が意図通りでないと思われる HOT 2
- [Problem proposal] Minimum Diameter Spanning Tree HOT 2
- [機能案] 提出頻度制限 HOT 1
- [テストケース] Suffix Array HOT 4
- [テストケース] Eulerian Trail HOT 1
- [問題案] partially retroactive priority queue HOT 3
- Assignment Problem: Make it n-by-m instead of n-by-n?
- Weak testcases in Link-Cut-Tree Problems.
- [機能案] unsolved枠の追加 HOT 3
- Migrate to C++17? HOT 1
- Weak testcases on static range LIS queries HOT 1
- Anti-Levit testcase in assignment problem HOT 1
- [Problem proposal] (Lexicographically smallest after removing at most `k` elements from list)
- GCC bug HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from library-checker-problems.